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
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.
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.
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^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
