awoo's blog

Educational Codeforces Round 127 Editorial
By awoo, history, 3 years ago, translation, In English

1671A - String Building

Idea: BledDest

Tutorial
Solution (BledDest)

1671B - Consecutive Points Segment

Idea: vovuh

Tutorial
Solution (vovuh)

1671C - Dolce Vita

Idea: vovuh and BledDest

Tutorial
Solution (adedalic)

1671D - Insert a Progression

Idea: vovuh and BledDest

Tutorial
Solution (awoo)

1671E - Preorder

Idea: BledDest

Tutorial
Solution (BledDest)

1671F - Permutation Counting

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +70
  • Vote: I do not like it

Comments Comments (33)
| Write comment?
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I've known that F needed precalc,but I didn't solve it.qwq

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

    In fact, when $$$n > k^2$$$ holds, the answer is a $$$O(k)$$$-degree polynomial. So you can use lagrange interpolation to solve this problem without precalc.

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

An interesting thing about problem b I found, the difference between the first element and the last element cannot exceed $$$n + 1$$$. as long as the difference is less than or equal to $$$n + 1$$$ the answer is always yes. I'm not the best at proofs, but I think this is because the greatest difference between a series of $$$n$$$ consecutive integers is always $$$n - 1$$$, and our operations can increase the first element by one and decrease the last element by one, thereby shrinking the maximum difference between elements by two at most. So if the maximum difference is greater than $$$n - 1 + 2$$$ then the answer is no. What I can't figure out is why the ones in the middle can always seem to fix themselves if this is true. Still, this solution works in $$$O(1)$$$.

my code

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

    Basically you are describing the same equation as the one in the solution: x[n-1]-x[0]-n+1 <= 2 <=> x[n-1]-x[0] <= n+1

    I actually solved this like a dumb person by shifting x[0] to the right or keeping it where it is and checking if everyone of the next elements can be shifted to the proper position according to where x[0] is fixed. So my complexity is O(2n) = O(n). Still works since reading the input is also O(n), but my solution is roughly 3 times slower than necessary.

    From my understanding, the solution described by the creator of the problem refers only to how many gaps there are between the first and last elements. If there are 0 gaps we're done, if there's one we can just shift one side and connect it with the other and if there are 2 gaps we shift 2 "chunks" so that everything is connected. On the other hand, if there are 3 or more gaps (which will make the inequality you referred to become false), then if one thinks about it, he will realize that there is no way to shift those 3 or more "chunks" in a way that they can be consecutive.

    The O(1) solution blew my mind on how simple it was. This problem caused me to overthink :D

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

How to come up with alternative solution of F?

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

Can someone explain the hashing solution for E?

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

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

Can someone send code for precalculation in 1671F - Permutation Counting ?

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

It seems that problem F can be solves with dp, but without precalc. But how to do that?

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

Can someone help me see where my B problem is going wrong，This caused my crash and lower rate my code

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

    This happens because if the answer is NO your code goes to end and doesn't input remaining numbers. So they will be in the next test case and all numeration of the input numbers breaks so your code gots WA. To fix it your need to input ALL numbers even if the answer is NO now.

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

      Thank you very much! ! ！ It was a stupid mistake T_T

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

      I modified it, but it still seems to have a problem code

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

        This happens because your solution can print two NO instead one. You must append the word continue; after the first check in cycle to not run the second check if the first check is already NO. And you will get AC then.

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

So, I have managed to create a test that hacks the hashes in the model solution for problem E. Now, my curiosity is: when hacking a solution, what does the checker use to find out what the correct answer to that given test is? Since if it would use the model solution, using a test like this, on which the model solution gives a wrong answer, could hack every solution, even the correct ones, and also make the problem impossible to solve if added to the testcases.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I've changed the model solution so that it is deterministic now, so the checker will compare the answer to the deterministic solution. Most likely the outcome will be something like "unexpected verdict" on hack since one of presumably correct solutions in Polygon is challenged.

    By the way, how do you hack the model solution? I thought this way of hashing subtrees worked well.

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

      What I have done is:

      1. try random trees with n=5 until two give the same first hash (takes about 60k tries on average)

      2. try trees with n=11 constructed as follows: first 6 layers are all 'A', and each of the subtrees under the 7th layer is a random one between the 2 found in step 1, this guarantees that the first hash will still give the same value to all the trees generated like so. And try until two trees give the same second hash (about 60k tries as well).

      3. same as step 2, but this time with n=17, and the subtrees under the 7th layer being a random one out of the 2 found before, until two trees give the same third hash (also around 60k tries)

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

        Do you mean that you've hacked the hashes with seed $$$42$$$? awoo always replaces generator seeds to $$$42$$$ when posting randomized solutions in editorials. You can try uphacking the solution, but most likely it won't work since the random generator seed in the actual solution is not $$$42$$$. Instead, it's time-dependent.

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

          oh, yeah, I have hacked the one with seed 42, it makes sense for the actual solution to be time dependent.

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

Can someone explain why https://codeforces.net/contest/1671/submission/155171162 is failing on test case 5? Cannot find the bug...

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

Can someone explain the part of editorial on problem D which says "you can insert 1 somewhere, then insert x somewhere. The rest of insertions will be free." Why will be the rest of the insertions be free?

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

    If you have 1, x somewhere or x, 1 somewhere than you can insert arbitrarily any element between 1 to x in between them for 0 cost , I will discuss 1, x case you can do x, 1 similarly , Now suppose you insert 1<c<x between 1 and x , cost will be (x — c) + (c — 1) = x — 1, so it's free now we know if 2 are adjacent it holds true imagine there are some elements already in between 1 and x

    1 C1 C2 x, it won't matter what order C1, C2 are in you can insert 1 < c < x between 1, C1 or C1, C2 or C2, x depending on which range it lies in, it will definitely be between more than one of the 3 ranges So cost of insertion will again be 0

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

In problem E, can anyone explain how are we checking the equality of equivalence classes using just the lexicographically smallest string in preorder?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
we can get the best insertion of 1 and x in o(1) by doing  this:

(ans) variable is the sum of the differences of the initial value, and (mn) refers to min element of the initial array and (mx) refer to max element of initial array

if(mn>1) ans+=min(2*(mn-1), min(v[0]-1, v[n-1]-1));
if(mx<x) ans+=min(2*abs(mx-x), min(abs(v[0]-x), abs(v[n-1]-x)));

My Submission

→ Reply
»
15 months ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

here's the solution to E (without hashing)

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

can somebody please tell what is the problem with my sumission https://codeforces.net/contest/1671/submission/281132373 its passing test case 3 but failing in 4 and i cannot understand why or if somebody can just tell what is test case 4 checking so i can work on that aspect of my code

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D has very Poor Editorial :)

→ Reply