432A - Choosing Teams
In this problem you should count number of students who can participate in ACM, divide it by 3 and round down. It could be done like this:
int cnt = 0; for(int i = 0; i < n; i++) if (5 - a[i] >= k) cnt++; int ans = cnt / 3;
432B - Football Kit
Count for every team number of games in home kit. For team i it equals to sum of n - 1 games at home and some away games with such teams which home kit color equals away kit color of team i. To count number of such away games you could calc array cnt[j] — number of teams with home color kit j. The solution could be implemented in this wasy:
for(int i = 0; i < n; i++) cnt[ x[i] ]++; for(int i = 0; i < n; i++) { ans_home[i] = n - 1; ans_home[i] += cnt[ y[i] ]; ans_away[i] = 2 * (n - 1) - ans_home[i]; }
432C - Prime Swaps
The solution can be described by pseudo-code:
Consider elements of permutation from 1 to n
While current element i is not sutiated on position i
Let the position of element i equals pos
Find maximum prime integer p which is less or equal than $pos — i + 1
Swap element in positions pos and pos - p + 1
It could be proved that such algorithm makes less than 4n swaps (for example, by implementing the algorithm)
This algorithm should be implemented optimally. You should maintain positions of elements of permutation. Swap function in author's solution:
void doSwap(int i, int j){ int x = a[i], y = a[j]; a[j] = x, pos[x] = j; a[i] = y, pos[y] = i; result.push_back(make_pair(i, j)); }
432D - Prefixes and Suffixes
The problem could be solved using different algorithms with z and prefix functions. Let's describe the solution with prefix function p of string s.
Calc prefix function and create a tree where vertices — integers from 0 to |s|, edges — from p[i] to i for every i. The root of the tree is 0. For every vertex v calc the number of values p[i] = v — that is cnt[v]. Then for every v calc the sum all values cnt[u] for every u in to subtree of v.
The general answer to the problem is:
Find all lenghts of the prefixes which matches the suffixes — these values are |s|, p[|s|], p[p[|s|]], p[p[p[|s|]]]... For every such length L the answer to the problem is sum[L] + 1.
432E - Square Tiling
This is popular test 6 :)
13 5 AAAAA AAAAA AAAAA AAAAA AAAAA BBBBB BBBBB BBBBB BBBBB BBBBB AAACA AAABB AAABB
The problem could be solved in a standard way — try to fill the table from the first cell to the last and try to put the miminum letter.
Consider the first row. Obviously it begins from some letters A (to be exact min(n, m) letters A). When we put some letters A in the first row, we should put several letters A in some next rows to make a square. The next letter could be only B.
Describe the solution in general. Assume that we have already considered some rows. Consider row i. Some cells in this row could be already painted. Consider unpainted cells from left to the right. For every such cell consider its color from A to Z. Two cases should be considered:
Put in this cell the minimum possible letter (neighbours have no such letter)
If the previous cell in this row was not painted at the beginning of considering row i, now it is already painted. We should try to merge the current cell with the square of the previous cell.
Choose the best case from these cases. Try to get the answer on test n = 13 m = 5 to understand the algorithm better.
any proof for problem C ?? I think most of the users solve it without any proof !!
Are there solutions other than the one described in the editorial? Maybe use a shell sort with prime increments?
i tired shell sort,it was giving TLE
looking forward to problem E editorial
Here is the greedy algorithm to deal with problem E.
step 1: Start with an uncolored table.
step 2: Set the pointer to the first cell.
step 3: If the pointed cell is uncolored, run the greedy subroutine described below.
step 4: If the pointer hasn't reach the last cell, set the pointer to the next cell(from left to right and from top to bottom as the problem mentioned), then go to step 3.
step 5: end the algorithm
The greedy subroutine:
step 1: Mark an 1*1 square whose upperleft corner is the pointed cell.
step 2: Determine the color of the pointed cell by choosing the smallest possible letter without breaking the rules. This color(chosen color) will be used to color all the cells in the square.
step 3: Enlarge the square from n*n to (n+1)*(n+1) (the upperleft corner of the square is still the pointed cell)
step 4: If atleast one of the conditions below is true, cancel the last enlarge step(change back the size from (n+1)*(n+1) to n*n) and go to step 5. Else, go to step 3.
(1) Any of the cells in the square is already colored.
(2) Square go out of bound.
(3) the cell in upperright corner of the square can be colored with a smaller letter than the chosen color without connecting its neighbors outside the square. (connecting means two cells using same color and share a side, same as the definition in the problem)
(4) If color all the cells in the square with the chosen color, any of the cells in the square(only need to check the border cells) is connecting to some cell outside the square.
step 5: Color all the cells in the square using the chosen color in step 2.
step 6: end the subroutine.
thank you
I can't get the idea of problem A?? I thought of a much more difficult solution Any help?
for 492 C, why is backward swapping not optimal?
My code gets WA(23490486) when I consider the case when element at i'th position is <i.
The same code gets AC(23490566) when I ignore this case and let it get sorted out in the next pass through. Why?
someone please explain question D. I am not getting what is written in the editorial above.
you can check how many characters from position i matches with the prefix of the string with z-algo in O(N) and determine the suffixes that matches prefix.
After that construct a suffix array and compute lcp of all suffixes with the suffix of position 1(whole string). you can build suffix array in nLOGn^2 and get all LCP in nLOGn. It will work because you are literally comparing the prefix with all possible substring start points. Store the LCP values in a frequency array and do a cumulative sum in reverse order. It will give you frequency of each prefix substring. It will work because if you found a LCP of 5 between two string that means you can also get a common prefix of (1,2,3,4).
my submission
In problem D, I understand that we can use the prefix function to determine efficiently the prefixes which are also the suffixes for the whole string. But I don't understand how are we calculating the count of sub-strings present in the string for each of that. Can somebody help me understand this in easy way please ?
you can check how many characters from position i matches with the prefix of the string with z-algo in O(N) and determine the suffixes that matches prefix.
After that construct a suffix array and compute lcp of all suffixes with the suffix of position 1(whole string). you can build suffix array in nLOGn^2 and get all LCP in nLOGn. It will work because you are literally comparing the prefix with all possible substring start points. Store the LCP values in a frequency array and do a cumulative sum in reverse order. It will give you frequency of each prefix substring. It will work because if you found a LCP of 5 between two string that means you can also get a common prefix of (1,2,3,4).
my submission
In problem D, you can simply calculate Z function and get the answer. No need for calculating suffix array and LCP. for a given prefix of length l, check whether z[n-l+1]=l or not. if Yes, then simply count how many integers in Z are greater than l by lower bound.
Submission : https://codeforces.net/contest/432/submission/47315796
(In case you are stuck with this problem(D) and just saw this beautiful idea and want a C++ code for the same)
https://codeforces.net/contest/432/submission/51429362 (Thanks for this awesome idea)
Thanks
Thank you! Awesome solution. Got to learn Z function from it. Here is the submission (easier to understand, I think) if someone is interested.
wow it's a very short and nice idea thanks
The Z-function method is obviously simpler and more intuitive. here.
Now, let's understand how the prefix-function method works. here.
Checking which prefixes-suffixes match is pretty straightforward. $$$pi[N]$$$ stores the length of the longest proper prefix which is also a suffix. So, this is our first matching prefix-suffix. Now, $$$pi[pi[N]]$$$ stores the length of the longest matching prefix-suffix of length less than $$$pi[N]$$$. Similarly, $$$pi[pi[pi[N]]]$$$ stores the length of the longest matching prefix-suffix whose length is less than $$$pi[pi[N]]$$$, and so on, until finally the length of our prefix becomes $$$0$$$.
Now, how does the less intuitive tree method work, for counting the number of occurrences of each prefix. There are $$$N+1$$$ vertices from $$$0$$$ to $$$N$$$, each denoting a prefix of that length. There is at least once occurrence of each prefix. Also, $$$pi[v]$$$ denotes that there is an occurrence of the prefix of length $$$pi[v]$$$. Now, for each vertex $$$v$$$, we add an edge from vertex $$$pi[v]$$$ to $$$v$$$. Then, the number of occurrences of a vertex of length $$$v$$$ will be $$$1$$$ $$$+$$$ frequency of $$$v$$$ in the $$$pi$$$ array $$$+$$$ sum of all occurrences of its immediate children in the tree.
Why? $$$pi[v]$$$ signifies that the prefix of length $$$pi[v]$$$ is the immediate fallback for the prefix of length $$$v$$$, meaning: the prefix of length $$$pi[v]$$$ is the next longest prefix which will definitely be present in any string which contains the prefix of length $$$v$$$. So, a prefix of length $$$v$$$ will be contained in any prefix of length $$$u$$$, such that $$$pi[u]=v$$$. So, just adding the contributions of the immediate children in the tree gives us the contribution of all places where the prefix of length $$$v$$$ was inside another prefix of a longer length, and prevents over-counting.
432D can also be solving in O(nlogn) using hashing and binary search. Submission link
Although it is definitely not recommended as it is way more complicated than the LPS approach, and also is very easy to get wrong (too many modulo operations) or TLE (tight TL with nlogn complexity). But in any case, if someone else was also trying hashing and couldn't get it to work, this could help.
It can also be solve by using suffix array, here's my shitty code(no one can understand) 86931883
It should've give TLE but it didn't, idk why.
D can be solved in O(n) simply using the z function. Steps
I. Using the z vector, construct vector<bool> good such that good[L] == true iff the prefix of length L is also a suffix.
II. Using the z vector, construct vector<int> cnt such that cnt[L] = number of appearances of the prefix of length L as a substring of s.
III. Using cnt and good, print the answer.
My submission: 82358099
I tried to solve Problem D using KMP but I am getting WA on test case 11. I am able to calculate L values but there is some problem while calculating sum. My code
Is there a way to solve this problem using KMP
[submission:217162339 Aug/05/2023] Problem D solution using prefix function
if any ques please ask!
Is there a simple way to solve problem D without prefix function, kmp or z function?
z functions and ordered set for count