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 !