awoo's blog

By awoo, history, 23 months 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

| Write comment?
»
23 months 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

  • »
    »
    23 months 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.

»
23 months 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

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

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

How to come up with alternative solution of F?

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

Can someone explain the hashing solution for E?

»
23 months 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).

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

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

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

»
23 months 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

  • »
    »
    23 months 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.

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

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

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

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

      • »
        »
        »
        »
        23 months 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.

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

  • »
    »
    23 months 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.

    • »
      »
      »
      23 months 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)

      • »
        »
        »
        »
        23 months 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.

        • »
          »
          »
          »
          »
          23 months 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.

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

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

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

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

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

»
6 months ago, # |
Rev. 4   Vote: I like it +7 Vote: I do not like it

here's the solution to E (without hashing)