HolkinPV's blog

Codeforces Round #246 (Div. 2) Editorial

By HolkinPV, 10 years ago, translation, In English

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:

  1. Consider elements of permutation from 1 to n

  2. While current element i is not sutiated on position i

  3. Let the position of element i equals pos

  4. Find maximum prime integer p which is less or equal than $pos — i + 1

  5. 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:

  1. Put in this cell the minimum possible letter (neighbours have no such letter)

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

  • Vote: I like it
  • +54
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

any proof for problem C ?? I think most of the users solve it without any proof !!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there solutions other than the one described in the editorial? Maybe use a shell sort with prime increments?

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

looking forward to problem E editorial

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't get the idea of problem A?? I thought of a much more difficult solution Any help?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please explain question D. I am not getting what is written in the editorial above.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[submission:217162339 Aug/05/2023] Problem D solution using prefix function

if any ques please ask!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a simple way to solve problem D without prefix function, kmp or z function?

→ Reply