Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

HolkinPV's blog

By HolkinPV, 5 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  

»
5 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 !!

»
5 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?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

looking forward to problem E editorial

  • »
    »
    5 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.

»
5 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?

»
2 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?

»
19 months 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.

  • »
    »
    2 months 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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be very helpful If we get any proof of Problem C.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The Goldbach's Conjecture, which stated that a number can be partitioned into sum of 2 prime numbers. So, in this problem, if you want to swap i and j, choose t that that (t — i + 1) is prime and (j — t + 1) is prime, by partitioning (j — i + 2), then swap (i, j), swap(t, j), swap(i, t). It can be proven that you can use maximum n swaps to sort an array without any constraints, so you need maximum 3n swaps to solve this problem.

»
2 months 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 ?

  • »
    »
    2 months 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