std::next_permutation(arr.begin(),arr.end());

What is next_permutation(a.begin(),a.end()) ?

Next permutation is like what its name says, finds the next permutation of a and assigns this permutation to a.

next_permutation is often used in brute force solutions.

So here's how to use it :

do{

   // do something

} while(next_permutation(a.begin(),a.end()));

The complexity of this code is O(number of elements in a !).

(Note : ! = factorial)

Extra : prev_permutation

prev_permutation(a.begin(),a.end()) has very similar functionalities. In fact, the only difference is that prev_permutation takes the previous permutation of a and assignes this permutation to a.

Thanks for reading and Happy New Year !

C++ Tutorial - Variables

So what is a variable ?

In computer science (not only in C++) a variable is a storage location. In C++, every variable has a data type, a name and a value.

Exemple :

int val = 100;

double a;

Here we have :

- data type :      int ; double

- name :            val ; a

- value :           100 ; 0

By default values are set to 0.

What can the name of the variable be ?

First of all, the name need to respect some conventions or else your program will recieve a Compilation Error verdict.

Here are the conventions :

- Your variables must begin with a lowercase or uppercase letter.

- Each character except the first character must be either a number, a character (lowercase or uppercase) or a underscore.

The name of your variables should be meaningful because you need to know what is assigned to the variable.

It is recommended to put a uppercase letter in front of each word except the first one, for exemple :

int maxWeight = 42;

Your variables shouldn't be to long and shouldn't be too short. (about 3 - 11 characters)

Why do we need variables ?

Variables are extremely important because you can store a value and reuse this value afterwards. Without variables, you can basically do almost nothing.

What are the possible data types ?

The possible data types for decimal numbers are : bool, char, unsigned char, short, int, unsigned int, long long, unsigned long long,  __int128_t, __m128d.

Data types for floating numbers are : float, double, long double and __float128.

Please note that unsigned integers do not support negative numbers (you'll get a random number if you use unsigned integers with negative numbers) ! So, be careful when you use them !

Here you can find the limits of these data types for decimal numbers except the last two :

name	expresses	value*
CHAR_BIT	Number of bits in a char object (byte)	8 or greater*
SCHAR_MIN	Minimum value for an object of type signed char	-127 (-27+1) or less*
SCHAR_MAX	Maximum value for an object of type signed char	127 (27-1) or greater*
UCHAR_MAX	Maximum value for an object of type unsigned char	255 (28-1) or greater*
CHAR_MIN	Minimum value for an object of type char	either SCHAR_MIN or 0
CHAR_MAX	Maximum value for an object of type char	either SCHAR_MAX or UCHAR_MAX
MB_LEN_MAX	Maximum number of bytes in a multibyte character, for any locale	1 or greater*
SHRT_MIN	Minimum value for an object of type short int	-32767 (-215+1) or less*
SHRT_MAX	Maximum value for an object of type short int	32767 (215-1) or greater*
USHRT_MAX	Maximum value for an object of type unsigned short int	65535 (216-1) or greater*
INT_MIN	Minimum value for an object of type int	-32767 (-215+1) or less*
INT_MAX	Maximum value for an object of type int	32767 (215-1) or greater*
UINT_MAX	Maximum value for an object of type unsigned int	65535 (216-1) or greater*
LONG_MIN	Minimum value for an object of type long int	-2147483647 (-231+1) or less*
LONG_MAX	Maximum value for an object of type long int	2147483647 (231-1) or greater*
ULONG_MAX	Maximum value for an object of type unsigned long int	4294967295 (232-1) or greater*
LLONG_MIN	Minimum value for an object of type long long int	-9223372036854775807 (-263+1) or less*
LLONG_MAX	Maximum value for an object of type long long int	9223372036854775807 (263-1) or greater*
ULLONG_MAX	Maximum value for an object of type unsigned long long int	18446744073709551615 (264-1) or greater*

Source : cplusplus.com

These values can vary depending on your compiler and its version.

The main differences between these data types are precision and overflow limits.

Note that __int128_t, __float128 and __m128d are somehow a little special because they are GNU extensions. If you want to know more about their up and downs please consider looking at this article.

What is a global variable and a local variable ?

A global variable is a variable that is declared outside the main() function and a local variable is declared inside the main() function.

Thanks for reading !

Extensions of GNU

Here are some extensions that I have found. Some of them are more useful than others.

1. indexed set
2. power(x,y)
3. rope

indexed set is just like a set. You can do lower bound (find the index) and find the index of the kth biggest element. With STL set, you cannot find the index. All functionalities of indexed set is in log(the size of container). To use it, you need to include the following lines :

#include <ext/pb_ds/assoc_container.hpp> // includes some countainers
using namespace __gnu_pbds;

Exercises :

ORDERSET

Little Artem and Time Machine

DNA Evolution

2 ) power(x.y)

This is a precise log(n) complexity function to do powers. To use it, include these lines :

#include <ext/numerics>

3 ) rope

This is a data structure that can handle concatenations in O(1) and can extract very fast a substring, insert and delete a substring quickly. You can use operator [] on rope. Reverse function of rope is very slow. How to use it :

#include <ext/rope>

using namespace __gnu_cxx;

// how to use

string s = "AABB";

rope<char> r = c_str(s); // add string to r

r += r.substr(1,3); // from pos 1 with length 3

r.erase(1,3);  // from pos 1 with length 3 erase

Exercises for rope :

AROPE

AROPE2

AROPE3

Thank You for reading and please comment below if you have other extensions to share : )

Unofficial Editorial - August Challenge 2019 Div 2 - CodeChef

I really enjoyed this contest ! The questions were nice and I had a lot of time to do them. So here I want to share my approaches to the problems (that I solved or almost solved).

1 ) Football

Link to the problem : https://www.codechef.com/AUG19B/problems/MSNSADM1

To get 100 pts : for each player, the score of the player is max(0, NumberOfGoals*20 - NumberOfFouls*10), so now we can use a variable to know the maximum of all the scores.

Time Complexity is O(n) per test case.
Here is the C++ code :

#include <bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> q;
while (q--){
int n;
cin >> n;
vector<int> v(n);
for (int i=0; i<n; ++i){
cin >> v[i];
v[i] *= 20;
}
int maxi=0;
for (int i=0; i<n; ++i){
int a;
cin >> a;
v[i] -= a*10;
v[i] = max(0,v[i]);
maxi = max(maxi,v[i]);
}
cout << maxi << '\n';
}
return 0;
}

2 ) Distribute Apples

Link to the problem : https://www.codechef.com/AUG19B/problems/DSTAPLS

To get 30 pts : for this subtask, you can do a simple simulation of the two candidates. Time Complexity is O(n) per test case.

To get 100 pts : we can see that there is no difference between the two candidates if n/k is a multiple of k. Time Complexity is O(1) per test case.
Here's the c++ code :

#include <bits/stdc++.h>
using namespace std;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> q;
while (q--){
long long n,k,a=0;
cin >> n >> k;
long long n2 = n,k2 =k;
if ((n/k)%k == 0 and k2*k2 <= n2) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}

3 ) Dilemma

Link to the problem : https://www.codechef.com/AUG19B/problems/CHEFDIL

For this question there are 2 ways to get 100 pts :

The first method is to count the number of ones (let's denote nbOnes), and if nbOnes is a odd number then Chef will always win. Time complexity is O(n) per test case. Here's the c++ code :

#include <bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> q;
while (q--){
string s;
cin >> s;
int cnt=0;
for (char c:s){
if (c == '1') ++cnt;
}
if (cnt%2 == 1) cout << "WIN\n";
else cout << "LOSE\n";
}
return 0;
}

The second method is to do some kind of simulation but I don't think that it is interesting to discuss.

4 ) Zombie and the Caves

Link to the problem : https://www.codechef.com/AUG19B/problems/ZOMCAV

To get 100 pts : for each Ci, just add 1 to the position i - Ci and decrease by one the position i+Ci+1. And now we can just do a prefix sum on this array. So now, to kill all zombies, we need to have the same numbers in H (contains health of N zombies) array and prefix sum array. To do that, we just sort the 2 arrays and see if the ith number of H is equal to the ith element of our prefix sum array.

Time Complexity : O(n log n) per test case. We can optimise to O(n) time by doing radix sort, but it wasn't needed to get 100 pts.

C++ code : https://www.codechef.com/viewsolution/25523124

5 ) Guddu and his Mother

Link to the problem : https://www.codechef.com/AUG19B/problems/KS1

To get 20 pts : You can have a O(n^3) algorithm per test case. Idea of algorithm : for all pairs (i, k), maintain a array (denote v) and a variable (denote var) and loop from j = i+1 to j = k, and xor the number v[j] with var, then add var to v, after that you can do the same thing from j = k to j = i+1 (decreasing).

C++ code for 20 pts : https://www.codechef.com/viewsolution/25525613

To get 50 pts : You can have a O(n^2) algorithm per test case. Idea of algorithm : firstly, let's do some kind of prefix sum but instead doing + operations, we do xor operations. So then for each pair of
(i, k), if just need to check if prefixXor[k] xor prefixXor[i] = 0 then we have k-i-1 new solutions.

C++ code for 50 pts : https://www.codechef.com/viewsolution/25533289

To get 100 pts : You can have at most O(n log n) algorithm per test case. Idea of algorithm : just like before, we create a prefix xor (explained in 50 pts solution), then we can create a adjacent list (for each value in prefixXor, we add the index of that value). Then we can easily calculate the answer for each index array in our adjacent list by using a formula on each pair (Ai,Bi) where Ai is equal to the ith number of our index array and Bi is equal to the element at (size_of_index_array - i - 1).

C++ code for 100 pts : https://www.codechef.com/viewsolution/25559727

6 ) Encoding

For 10 pts, you can do a simulation : for all the numbers between L and R, put all the digits in a vector, then calculate.

I think 100 pts is dynamic programming + some math. But I wan't able to code it.

7 ) Chef and Gorden Ramsay

Link to the problem : https://www.codechef.com/AUG19B/problems/CHGORAM

There are 2 solutions (at least), one of them is binary tree + dfs. The other one is indexed_set + dfs. The logic is the same. So, for the star solution, you just need to come up with a formula and find the center of the star. The O(n^3) solution : for all pairs(a,c), find all potential b such that (a,b,c) is a solution. The O(n^2) solution : for all centers b, find all potential a and c such that (a,b,c) is a solution. This can be done with a dfs. Here, we can make an observation : the adjacent list of b should be bigger or equal to 2, to have at least one additional solution.

The O(n log n) solution : the idea is to maintain a indexed_set in the dfs to know the number of numbers bigger than the current node and the number of numbers smaller than the current node. We can now easily use these informations, to come up with a formula and calculate the result.

Let’s take the exemple of the question :

1

4

2 1 3

1 2

2 3

2 4

My algorithm for this exemple :

Take a node (let’s say 2). Add 2 to the indexed set.

Then, I will go through all of the unvisited neighbours of 2. Add them (node 1,3 and 4) to the indexed set and calculate* the number of answers for them. After this we can calculate* the number of answers for 2.

(*) We can see that we can calculate the number of solutions for a current node (taking it as the middle), knowing the number of nodes bigger than the current node and smaller than the current node.

More explanation for the formula and calculation :

Suppose tot_small, the total number of nodes smaller than the current node and tot_big the number of nodes bigger than the current node. tot_small and tot_big are trivial to calculate because the statement says that all nodes are numbered from 1 to N.

Now for each subtree of the current node, we will calculate the number of nodes bigger and smaller than the current node. Let’s call them big and small. Here, we will have 3 cases to do, p2 = 1, p2 = 2, p2 =3.

If p2 == 1, than we will add (tot_big - big) * big to the current answer.
If p2 == 2 than we will add (tot_big - big) * small + (tot_small - small) * big to the current answer.
If p2 == 3 than we will add (tot_small - small) * small to the current answer.

Now we need to add to the answer : current answer / 2.

Star solution O(n) + O(n^3) normal case : https://www.codechef.com/viewsolution/25592978
Star solution O(n) + O(n^2) normal case : https://www.codechef.com/viewsolution/25672640
Star solution O(n) + O(n log n) normal case : https://www.codechef.com/viewsolution/25691825

8 ) (Challenge) Bacteria Synthesis

Link to the problem : https://www.codechef.com/AUG19B/problems/SYNBAC

Firstly, we can see that there are not much difference between a reverse operation (cost is ~2^13) and a mutate operation (cost is ~2^13) because if you buy a protein , it will cost you 2^28, which is way more than 2^13.

Greedy method is to put all our proteins in a vector called "greedy" and then concatenate all the shortest proteins (which are the first ones in my vector greedy because vector greedy is initially sorted) in a string (let's denote comp) and compare this string with the initial string :
https://www.codechef.com/viewsolution/25810054

We can optimise this by checking if there are other proteins (that we missed), in our string comp. I then randomised some procedure of my algorithm.

My best solution uses this greedy approach but I use KMP to erase the commun intersections, for exemple :

ABBA
     BAAB

We see that BA are in commun, so we can directly transform this to ABBAAB. Don't forget that you can also optimise :

     ABBA
BAAB

So now, we can try to find the best order (the one with maximum intersection) for our greedy algorithm.

Another method, is to use a trie.

Useful links for challenge question :

https://faculty.ucr.edu/~mmaduro/random.htm
https://en.wikipedia.org/wiki/Bioinformatics
https://www.geeksforgeeks.org/longest-prefix-also-suffix/
https://codeforces.com/contest/1200/problem/E
http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/SortRevPres.pdf

__int128_t and __float128 in GNU

Usage of __int128_t:

• supports really big intermediate numbers, from -2^128 + 1 to 2^128 - 1
• it has 128 bits

Usage of __float128 :

• can go up to 20 (or 30, if I remember correctly) decimal places
• it has 128 bits

Problems of __int128_t and __float128:

• can not print a integer of __int128_t
• can not read a integer of __int128_t

Comparing __int128_t and long long

• __int128_t consumes 3 - 5 times more memory and time then long long
• __int128_t consumes 3 - 5 times more time and time then long long

Comparing __float128 and long double :

• __float128 consumes 3 - 5 times more memory and time then long double
• __float128 consumes 3 - 5 times more time and time then long double

A little exercice before the end :

What is the difference __m128d and __int128 ?

Comment below and thanks for reading !

Fastest way to read input from stdin C++

Method 1 :

A noob's way :

#include <iostream> using namespace std; int main(){    int nb,a;    cin >> nb;    for (int i=0; i < nb; ++i){       cin >> a;       // do some stuff    }    return 0; }

Method 2 :

A classic way :

#include <iostream> using namespace std; int main(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int nb,a;    cin >> nb;    for (int i=0; i < nb; ++i){       cin >> a;       // do some stuff    }    return 0; }

Method 3 :

The C way :

#include <cstdio> int main(){    int nb,a;    scanf("%d",&nb);    for (int i=0; i < nb; ++i){       scanf("%d",&a);       // do something    }    return 0; }

Method 4 :

The getchar way :

#include <stdio.h> #include <stdlib.h> int fastscan(){    int c;    bool negative = false;    int a = 0;    c = getchar();    if (c=='-'){       negative = true;       c = getchar();    }    while(c>47 and c<58){       a = a*10 + c - 48;       c = getchar();    }    if(negative){       a = -a;    }    return a; } int main(){    int nb;    scanf("%d",&nb);    for (int i=nb; ~i; --i){       fastscan();       // do something    }    return 0; }

Method 5 :

The optimised getchar_unlocked method :

#include <stdio.h> #include <stdlib.h> inline int fastscan(){    int c;    bool negative = false;    int a = 0;    c = getchar_unlocked();    if (c=='-'){       negative = true;       c = getchar_unlocked();    }    while(c>47 and c<58){       a = (a<<1) + (a<<3) + (c - 48);       c = getchar_unlocked();    }    if(negative){       a = -a;    }    return a; } int main(){    int nb;    scanf("%d",&nb);    for (int i=nb; ~i; --i){       fastscan();       // do some stuff    }    return 0; }

Method 6 :

The inserter's way :

#include <iostream> #include <vector> #include <iterator> #pragma GCC optimize ("O3") using namespace std; int main(){    setvbuf(stdin, (char*)NULL, _IOFBF, 0);    ios::sync_with_stdio(false);    cout.tie(nullptr);    cin.tie(nullptr);    int nb;    cin >> nb;    vector<int> v;    copy(istream_iterator<int>(cin), istream_iterator<int>(),back_inserter(v));    for (auto& i:v) // do some operations    return 0; }

Method 7 :

The bufferer's way :

#include <iostream> #define BUFSIZE 1024*900*64 int main(){    int n, number=0,numbers;    scanf("%d",&n);    char buf[BUFSIZE+1] = {0};    while ((numbers = fread(buf, 1, BUFSIZE, stdin)) > 0){      bool neg=false;       for (int i=0; i < numbers; i++){       if (buf[i] == '-') neg=true;       else if (buf[i] != '\n'){          number = buf[i] - '0' + 10*number;       }        else{          n--;          if (neg) number = -number;          // do something          number = 0;          neg = false;        }            }      if (!n)  break;    } }

Method 8 :

The ultimate way :

#include <cstdint> #include <cstdlib> #include <cstdio> #include <unistd.h> #include <sys/mman.h> #include <sys/stat.h> inline char* stdin_ptr(){     struct stat sb;     (void)fstat( STDIN_FILENO, &sb );     return (char*)mmap (0, sb.st_size, PROT_READ, MAP_SHARED | MAP_POPULATE, STDIN_FILENO, 0); } inline int atoi(char*& data){     int val = 0;     bool neg=false;     if (*data == '-'){        neg = true;        data++;     }     do{         val = val*10 + *data++ - '0';     } while(*data & (1<<4));     if (neg) val = -val;     ++data;     return val; } int main(){     char* ptr = stdin_ptr();     int n = atoi(ptr);     while (*ptr) // do something }

If you have a better method please share !