_Kuroni_'s blog

By _Kuroni_, history, 5 months ago, In English,

Hello everyone, this is the editorial for Codeforces Round #558 (Div. 2). I hope you enjoy the problem as well as I did!

1163A - Eating Soup

Author: _iloveNQ_

Tutorial
Implementation

1163B2 - Cat Party (Hard Edition)

Author: _Shirone_

Tutorial
Implementation

1163C2 - Power Transmission (Hard Edition)

Author: LunarStellarshot

Tutorial
Implementation

1163D - Mysterious Code

Author: _Kuroni_

Tutorial
Implementation

1163E - Magical Permutation

Author: _Kuroni_

Tutorial
Implementation
Implementation with DFS

1163F - Indecisive Taxi Fee

Author: _Kuroni_

Tutorial
Implementation
 
 
 
 
  • Vote: I like it
  • +75
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Auto comment: topic has been updated by _Kuroni_ (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Fast editorial :)

»
5 months ago, # |
  Vote: I like it +57 Vote: I do not like it

The way Grey code was included in E, so natural, I can only say it was extremely elegant. Another kudo for you guys. ;)

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

    can you please explain the solution for E a little bit more? I didn't get it :(

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I really liked problem B.

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Problem E is just beautiful.

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

    You can say it was magical :D

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

      in your if block of add function, no need to sort. again, great problem!

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    "such that the xor value of any two consecutive elements belongs to the basis; or in other words, the corresponding bitmask of any two consecutive elements in the magical permutation differs by exactly 1 bit." Can you explain this part?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Suppose the elements needed to create basis are $$$v_0, v_1, ... v_{x - 1}$$$.

      Suppose x = 2; Grey code is,

      00 01 11 10 Now you can create magical permutation by taking xor's of all $$$v_i$$$'s for all set bits i. In this case magical permutation is

      $$$0$$$, $$$v_0$$$, $$$v_1\oplus v_0$$$, $$$v_1$$$

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

really good problem set, I need more clarification about the counting techniques in problem B, any help would be appreciated

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

    Same Here

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

    It just finding maximum prefix that sustainable for this requirement. The requirement is you must removing one integer from this prefix and then the number from each integer(in the prefix) is same.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You use 2 counting arrays, one for counting the occurrence of colors, and one for counting the number of colors which have the same occurrences. You can have a look at the implementation for more details.

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

      About idea maintain a "max" variable: frequency that appears most often. I see this brilliant. Maintain count[] and freq[] are also very beautiful. How can you come up with this solution ? Do we have any similar problems using this technique ? Thanks so much.

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

      could you please explain in a bit more detail. Didnt understand how to implement the same, even after going through the implementation code

      Thanks

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the solution of the problem Cat Party in a little bit more Detail

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It just finding maximum prefix that sustainable for this requirement. The requirement is you must removing one integer from this prefix and then the number from each integer(in the prefix) is same.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why long double fails for C whereas double passes ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    When you use floating point numbers there are always rounding errors. Using double just happens to discard the rounding errors < $$$10^{15}$$$ so something actually wrong (like a == b) just happens to work.

    Do NOT use floating point numbers in problems like this. They'll catch you and knock down you, maybe in an important contest.

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

      Is there any possible test case that would fail for double as well?

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Rounding off of double leads to incorrect key for mappings.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        On 32-bit x86 machines (for example, Codeforces runners) map<double, ...> is essentially broken because x87 registers use 80-bit representation while the result stored into the memory is truncated into 64-bit. It only "works" because of blind luck.

        Maybe map<volatile double, int> will work (since volatile forces the value to be stored into the memory and eliminates the "existence" of 80-bit value).

        Even if SSE is used (for e.g on x86-64) or we somehow workaround this x87 problem, a1/b1 and a2/b2 may be different but truncated to the same value. I'm not sure if it could happen under the constraint of this problem.

»
5 months ago, # |
  Vote: I like it +19 Vote: I do not like it
My Solution of Problem B
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me how can you come up with this data structure ? Or we just need to practice more ? I see the idea of maintain a "max" variable: frequency that has maximum color. How can we come up with this idea ?

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

      No data structure needed, just using vectors. I just thought about the variables that we need to get the answer and maintained them.

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

Since am extremely smart when it comes to math problems I was able to solve problem A with a bruteforce approach. I feel ashamed with my code https://codeforces.com/contest/1163/submission/53912810

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

Problem C.

"that whenever two different electric wires intersect, they may interfere with each other and cause damage. So he wonders, how many pairs are intersecting?".

Maybe someone can explain when is the intersect wire counted.

Thank you.

»
5 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Can someone suggest similar problems to D since many people said it is standard?

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Are you sure about time complexity of D? should it not be c*|s|*|t|*26?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The exact complexity is indeed $$$O(26 * |c| * |s| * |t|)$$$, but I removed the constant to simplify it.

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

Any links to the tutorial for solving such problems using Gaussian elimination ? Also any links for learning general Gaussian elimination?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For C, is this really true...?

These are the pairs with the same slope (i.e. same value of a and b),

I wonder how about such cases like 4x + 6y = 5 and 2x + 3y = 4, which are parallel

(My code in the contest time had this same bug)

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

    Ah, now I understand Such a case like 4x + 6y = 5 does not occur, for this has no integer solutions: gcd(a, b) and gcd(a, b, c) always coincide

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My code got accepted for C1. But it is giving wrong answer in C2. Can someone please help

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

    Assuming your logic is correct throughout the code, the only thing that I think could cause this is if you are not using longs as you generate the final answer in C2.

»
5 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Problem F is almost the same as 《故乡的梦》 on bzoj(which is a Chinese OJ). Anyway,Problem E is very interesting.(Although some part of this problem appeared in Atcoder AGC 31 C) :D

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

can someone help me with my code for D?

I am getting RE on test 18.

»
5 months ago, # |
  Vote: I like it +19 Vote: I do not like it

We can optimize problem D even further. Suppose at a dp state, we have $$$ks \leq kt$$$, then we don't even need to save $$$ks$$$ as a state, because we can directly calculate $$$ks$$$ using $$$kt$$$. Hence, the number of dp states are now only $$$O(|c| \cdot \max(|s|, |t|))$$$.

»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem D can be solved in a better way.

We build an ACAM(Aho-Corasick Automaton) for $$$s$$$ and $$$t$$$ and then we do dynamic programming on the ACAM.

Let $$$dp_{i,j}$$$ be the largest answer we can get in a walk on the ACAM which consists of $$$j$$$ steps and ends at node $$$i$$$. Initially $$$dp_{rt,0}=0$$$ and the others are $$$-\infty$$$, where $$$rt$$$ denotes the root of the trie of the ACAM. Finally the answer is the maximum value of all those $$$dp_{i,|c|}$$$s where i denotes a node on the ACAM. Do not forget to add all $$$i$$$'s fail-nodes' value to $$$i$$$'s value.

The time complexity is $$$O(26\times |c|\times (|s|+|t|))$$$.

An ACAM can deal with similar problems with 2 strings or more. How nice! :D

Code: 53944139

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem A- I think the solution provided for 1163A-Eating soup is a little bit wrong between the statement "Otherwise, if m+1≥⌊n2⌋, each independent cat to leave decreases the number of groups so the answer is n−m", in this if m+1=lower(n/2) the solution concide with m-1<lower(n/2), which is not optimal,

so to improve it we have to remove inequality in provided solution.

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

can someone tell me what's wrong with my solution?

I am not sure why am I getting wrong answer for bigger values of N. https://codeforces.com/contest/1163/submission/53945287

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

    The precision of float is not enough, try double.

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

For D, What's the complexity that get the nxt array?

for (int i = 0; i <= n; i++)
        for (char c = 'a'; c <= 'z'; c++)
        {
            int cur = i;
            while (cur > 0 && s[cur + 1] != c)
                cur = kmp[cur];
            if (s[cur + 1] == c)
                ++cur;
            nxt[i][c - 'a'] = cur;
        }
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Use Aho-Corasick automation,Problem D's Complexity can be O(|c|⋅(|s|+|t|)).

»
5 months ago, # |
  Vote: I like it +44 Vote: I do not like it

I think the tests of the problem E is not strong enough.

Here is my solution: https://codeforces.com/contest/1163/submission/53950641

Here is the hacking test:

2
4 5

But my solution gets:

1
0 0

It is obviously wrong. Because my solution thinks if it is possible to get all $$$2^i\ (0 \leq i \leq x)$$$ from the basis, $$$x$$$ is going to be valid. Maybe not only me wrote like that.

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

In problem C2 tutorial, can anyone explain why c=y1x2−y2x1 ?

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

    Equation of a line is (y-y1)=m(x-x1) now m=(y2-y1)/(x2-x1) now try to change this formula in form of equation of line y=mx+c You will get c=y1x2-y2x1.

»
5 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

E can be solved in $$$O(n+MAX)$$$ by using counting sort and Gray code.53956574

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you explain "We now iterate over these "blocks" of parallel lines and count the number of pairs each block contributes — a block of size s gives s(s−1)2 pairs." ?? And in problem B, why cnt[mx — 1] * (mx — 1) == i — mx && cnt[mx] == 1 is one color has the occurence 1 more than any other color ?? I don't understand. Thank you very much <3 <3 <3

»
5 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Thanks for the round!

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain a bit more in detail solution for D? What exactly is the array nxt[N][26], and how it is constructed? I know about KMP as algorithm for finding pattern in text in O(N) time complexity.

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

    you can view nxt[i][c] as, i (before) matched length, c new char, nxt will be (after) matched length. similar in KMP search method, [26] just pre-process those possibility.

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

Need help for problem C2. Why my submission giving WA. Even it is working fine at IDE.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm having trouble understanding one detail for problem F. To handle the case that an edge $$$e$$$ on the main path increases in cost, we need a way to find the shortest path from $$$1$$$ to $$$N$$$ not using $$$e$$$. The proposed approach generates a set of candidate paths, each of which avoids some interval of edges on the main path, and finds the shortest among those avoiding $$$e$$$. How can we prove that for every $$$e$$$, the shortest possible distance will certainly appear within that set of candidates?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Now if for each $$$u$$$, $$$l_u$$$ is tightly bounded, i.e. every shortest path from $$$1$$$ to $$$u$$$ must uses the first $$$l_u$$$ edges of the main path (same analogy for tight $$$r_u$$$), then the the set shortest possible distance not using the edge $$$e$$$ is maximized.

    Now, what if $$$l_u$$$ and $$$r_u$$$ is not tightly bounded? I will call the tight bound of $$$l_u$$$ as $$$tl_u$$$, and tight bound of $$$r_u$$$ as $$$tr_u$$$. I will skip over this part a little fast, but basically take the shortest path using the tight bound $$$tl_u$$$ and $$$tr_v$$$ of a candidate edge $$$(u, v)$$$, and let's call the set of edges on this shortest path from $$$tl_u$$$ to $$$tr_v$$$ as $$$S_e$$$. Then I can prove that the union of the ranges $$$l_{u_e}$$$, $$$r_{v_e}$$$ of all the edges belong to this $$$S_e$$$ set to be exactly $$$tl_u$$$ to $$$tr_v$$$, without any interruption. So, in one way or another, the value of the shortest path that must pass through the candidate edge $$$(u, v)$$$ will appear in the range $$$tl_u$$$ to $$$tr_v$$$, regardless of the values of $$$l_u$$$ and $$$r_v$$$.

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

My way of solving B is maintaining a multiset of the counts of each color. At each step, it is possible if (1st element is 1 and 2nd element = greatest element) or (1st element = next-to-last element and next-to-last element = last element - 1).

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

Can anyone help me? I am unable to find where I am going wrong. This is my solution for problem C2(Power Transmission), I am getting wrong answer on test 10. link: https://codeforces.com/contest/1163/submission/53963521 Thank You.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    fil.size() return unsigned int (4bytes) on codeforces which will overflow when multiply.

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

In C2 code implementation , I didn't understand this part . please help me --- // simplify equation int d = gcd(a, b); a /= d, b /= d; if (a < 0 || (a == 0 && b < 0)) { a = -a; b = -b; }

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    When using gcd function with negative numbers, so whenever the numerator is negative, the result becomes negative. So after a and b are divided by their gcd i.e. a /= d, b /= d , their sign may get reversed. This happens only when if numerator 'a' is negative or if 'a' is zero and denominator 'b' is negative.

    try with an example it will be more clear.

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

I am getting wrong answer on test case 10 in Power transmission( Hard version ) Is there any corner case in problem?

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

Can someone please elaborate editorial's idea on solving D, in more detail?

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

    I will try explaining how i solved it :)

    lets start
    recursive part
    handling ks kt ...
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I discussed a solution here

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

I tried submitting problem D's solution in practice without precomputing the next arrays, which the Author's solution does and it passed in almost the same time as the solution with the next arrays precomputed. Here's the code: 53966779

The solution has a worst case complexity of $$$O(26*|c|*|s|*|t|*max(|s|,|t|))$$$. So how can it pass? Is it because of weak test cases or is there a reason for this?

»
5 months ago, # |
Rev. 6   Vote: I like it -9 Vote: I do not like it

Anyone has come across any similar questions like D? Plz put their link.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Could anyone provide a clear explanation for problem D pls ?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In the problem E, why does the dfs-solution (the second solution attached on the tutorial) works? Gray-Code works obviously, but I can not prove we can replace it with a simple dfs. (or am I misreading something?)

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    That's what I was surprised with to be honest, at the beginning I wrote this DFS to try and hack it, but it ended up as a completely viable solution :/

    Since when I DFS like in the implementation, the first usable bit is always used, the sequence of the bit changed is actually the same as the Gray code, i.e. the bit changed are $$$0$$$, $$$1$$$, $$$0$$$, $$$2$$$, $$$0$$$, $$$1$$$, $$$0$$$, $$$3$$$, $$$0$$$, $$$1$$$, ... So, the DFS will trace a straight path of $$$2^x - 1$$$ numbers right away, since it is the same as Gray code.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Wow, so we can construct gray-code simply by using succinct DFS. I didn't know that.

»
5 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Problem D : (Just Discussing a solution)

1. Given strings S and A , both contain lowercase English char only , we have to count how many occurrences of A in S. ...what we will do?..KMP right? so , we have LPS[] for string A.

( LPS[i] = length of " longest prefix which is also suffix " of sub-string A[0...i]) . Let's make an recursive implementation of KMP.

2. Now assume S can have some '*' which can be replaced by any char in between 'a'-'z' . How many occurrences now ?....KMP again..but we need LPS[i][c] now.

Where LPS[i][c] = length of " longest prefix which is also suffix " of string( A[0...i] + (char)(c+'a') ); what change will come in our above recursive solution?...

something like this, right?

3. Now come to our actual problem D. We need two different lps arrays LPS_A[][] and LPS_B[][] . how the func will change now?

Like this?

4. we're actually done!..just need to pre-calculate two LPS arrays using brute force and trivial dp memoization .Code

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

Hi, this solution: http://codeforces.com/contest/1163/submission/54373882 returns WA for both C1 and C2, but in my IDE it returns the correct answer. Is there a problem with the compiler? Thanks.

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

    I didn't watch your code carefully, but as someone earlier said — using floating point numbers in such problems is a big NO NO. Try to remake your algorithm so that you operate only on integers.

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

    db m = (a[i].second — a[j].second)/ ((a[i].first — a[j].first) * 1.0); The value of slope m lies in the range (-INF, +INF). db cannot store slope when it exceeds the capacity of db.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ok, thanks, but still I don't get why I get the correct answer on my computer. Could someone test it yourselves locally? Thanks a lot.

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

why does ceil function doesn't work in my solution??solution link-> https://codeforces.com/contest/1163/submission/54708474

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

what is wrong with my code for problem C1 Solution

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

for problem C what happen if two line are as given

2x — 3y = 4;

and

4x — 6y = 8;

because c is not divided by gcd of a and b.

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

Help in C: Giving WA for large test cases... My logic for C is: Calculate number of distinct lines . then find total number of intersections.

And then from total, subtract all the parallel lines which won't be intersecting. Suppose for slope m , then are k parallel lines. Then subtract k*(k-1)/2 from total.

Do this for all the slopes.

Its giving WA for large test cases. Submission link: Submission Link Question Link: Question Link

Thanks in advance:)