maomao90's blog

By maomao90, 3 years ago, In English

Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial

1672A - Log Chopping
Author: errorgorn

Hints
Tutorial
Solution

1672B - I love AAAB
Author: errorgorn

Hints
Tutorial
Solution

1672C - Unequal Array
Author: maomao90

Hints
Tutorial
Solution

1672D - Cyclic Rotation
Author: errorgorn

Hints
Tutorial 1
Tutorial 2
Solution 1
Solution 2

1672E - notepad.exe
Author: errorgorn, oolimry

Hints
Tutorial
Solution

1672F1 - Array Shuffling and 1672F2 - Checker for Array Shuffling
Author: errorgorn

Hints
Tutorial
Solution for F1
Solution for F2

1672G - Cross Xor
Author: maomao90, errorgorn

Hints
Tutorial
Solution

1672H - Zigu Zagu
Author: maomao90, errorgorn

Hints
Tutorial
Solution

1672I - PermutationForces
Author: errorgorn

Hints
Tutorial
Solution
  • Vote: I like it
  • +135
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

Testdata for E was somewhat a little weak, I passed with parrel binary search with some optimizations. In the actual testdata it took no more than $$$500$$$ queries to find the answer.

Can anyone hack me?

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

    Try this:

    6
    1990 1997 1992 1994 1995 1989
    

    In fact, there is a $$$20\%$$$ probability that your solution will use more than $$$n+30$$$ queries, when $$$n=6$$$ and $$$l_i=2001-i-d_i$$$, where $$$d_i$$$ is randomly chosen in $$$[0,10]$$$.

    P.S. I didn't do enough experiments so that maybe the probability is not exact at all.

»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Me Mister Bebra!

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

My solution for D failed pretest 3. What I did is I went from right to left in array b maintaining a set current that contains all the indices in a that are being used, and a map extra that stores a count of all the extra values I can use.

Case1 b[i] = b[i — 1]: I will consider b[i] and b[i — 1] together. I find the greatest element in the set, let's call if g. I then iterate from g decreasing. In the current index k, if it isn't in current I skip it. Otherwise if it's equal to b[i], I'll remove k from current and break out of the loop. If it's not equal to b[i], I check if I have an extra a[k] in my map. If not, the answer is NO. Otherwise, I decrease the count by 1, remove k from current, and continue; At the end, I add b[i — 1] to the map extra so that I can use it in the future.

Case2 b[i] != b[i — 1]: I'll consider b[i] by itself. Then I'll do the exact same proccess as in Case1. The only difference is that I won't add b[i — 1] to extra and I'll just move on to the next i.

At the very end, array a might have some leftover elements. I will iterate over all these elements and see if I have enough values in extra to match them all. If I do, then the answer is YES. Otherwise, the answer is NO.

Is my logic wrong? 154756012

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

    Input:

    1
    5
    4 4 1 1 4
    1 1 4 4 4
    

    Expected Output: YES

    Your Output: NO

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

      I'm a little puzzled myself. I'm doing more or less the same thing, and I pass your given test case.

      154775344

      Edit — ah I see the issue, nvm

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

I've spent 1 hour 30 minutes looking for a bug in my solution of D (got WA on the 3rd test)... After the round finished I updated the page every minute, waiting for testcases to be shown... And what I see now is only "wrong answer expected YES, found NO [515th token]", because the test data is truncated.

I'm begging to look at the full testdata for test case 3, this is my only dream now

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

    I'm in a similar situation.

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

      154781966

      test case 515

      20
      3 2 2 1 1 3 1 3 3 1 3 2 1 3 1 3 1 1 3 1
      3 2 1 1 3 1 1 3 2 2 3 3 1 1 3 1 3 3 1 1

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

    Input:

    1
    6
    5 2 3 2 3 2
    2 3 5 3 2 2
    

    Expected Output: NO

    Your Output: YES

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

I think that problem H was really misplaced. Reading it afterward, it seems pretty straightforward, but I didn't try it during the contest because I thought it would have been much harder.

Also, making 1 1 a system test rather than a pretest for E really screwed a lot of people (including me) over.

Overall, it was a good contest!

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

In Problem B, I couldn't understand how AABBABAAAABABABAABAB can be acheived(Output is YES) as they are two succesive B's and good strings are AB, AAB, AAAB,..., so there must be atleast one A between two succesive B's and 'B' is bad string. I believe deletion of one character or substring is not allowed. Sorry if it is too dumb, but could anyone can explain this to me Thanks

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

    The problem says "Choose any position of s1 and insert some good string in that position."

    So we can insert AB into the middle of another AB which results in AABB

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

    We can do string AABB like this. 1) empty -> AB 2) AB -> AABB (A+AB+B) So we got the string like AABB

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

    Ohh I got it now

    Thank you so much

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

// Super Idol的笑容 // 都没你的甜 // 八月正午的阳光 // 都没你耀眼 // 热爱105°C的你 // 滴滴清纯的蒸馏水 Now this is epic

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

    Where is that from? I mean why is everyone posting this in the comments

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

      It's in the solutions above? If you mean what does it mean then it's an epic beautiful song

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

I found a different, possibly simpler, solution to H (Zigu Zagu). As in the hints I always remove a maximal segment. There are four possibilities:

  1. The endpoints of the segment are the same (e.g. we have ..1|101|1..). If we remove this segment we remove two pairs of consecutive 0s or 1s, but create one new pair of consecutive 0s or 1s

  2. Its endpoints are different (e.g. ..0|01|1..). In this case we remove one pair of consecutive 0s and one pair of consecutive 1s, without creating any new pairs of consecutive 0s or 1s

  3. One of its end points is at the end of the substring. Removing the segment simply removes one pair of consecutive 0s or 1s.

  4. The segment is the whole remaining substring. We always finish like this.

This means that every segment of type 1 or 3 reduces either the numbers of pairs of 0s or the number of pairs of 1s by 1. This reduces the number of remaining maximal segments by 1. Every segment of type 2 reduces both the number of pairs of 0s and the number of pairs of 1s by one, hence reducing the number of maximal segments by 2. As such our sequence should be:

  • Remove all possible segments of type 2. As long as there are pairs of both 0s and 1s there will always be at least one segment of type 2; so this will take min(0 pairs, 1 pairs) steps

  • Remove all remaining type 1 and type 3 segments. This will take a number of steps equal to the number of remaining 0 or 1 pairs, which will be max(0 pairs, 1 pairs) - min(0 pairs, 1 pairs)

  • Remove the last segment.

This gives a total of max(0 pairs, 1 pairs) + 1 steps.

To implement this, do a pass through the string calculating the number of 0 pairs and 1 pairs before each element, and we can then trivially calculate the number 0 pairs and 1 pairs for each query, and hence the answer to each query.

See https://codeforces.net/contest/1672/submission/154753079 (Python)

»
3 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Anyone interested can check my code 154764444 for problem F1 (easier to understand than editorial).

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

    brrrrrrr

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

    Can you explain your solution?

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

      I took the next greater element for every element in A which will result in making the longest chain of substitutions which then results in the highest sadness. And for every cycle we have of length L, the number of swaps will be L-1.

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

    Naming the function "brrrr" was key. Editorial missed it totally.

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

    that's pretty cool

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

About A's tutorial, seems $$$\sum_{k=1}^na_i$$$ there is a mistake

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

Finally I got FST on problem E because I set the upperbound of binary search 4e9 but not 5e9, and I got WA on test 20. Anyway, it's a good contest with excellent problems.

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

I don't know why I get TLE on problem D 154740846. I think it's O(N). Can someone help me.Orz

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

I could have reached cm today if i didn't fail in (E) Main tests, (〒﹏〒)

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

Misprint In editorial of D, tutorial 1, case 3: "we delete an occurance of ai in S and decrement j", We should decrement i instead of j.

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

Does anyone has a segtree solution for H? I was stuck on how to correctly merge two segments together... And I guess there must be some smart way of doing so.

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

In editorial of D, tutorial 2, I can't understand what is this saying : "As such, we can consider mapping elements of b into elements of a. More specifically, consider a mapping f where f is non-decreasing, bi=afi and we increment cfi by 1 for all i". Can anyone elaborate please?

Thanks in advance.

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

Nice contest, although I did not perform well.

Problem A is amazing. I use SG function to solve it, even though I felt that there must be a simpler solution during the contest. It turns out that my guess is right when I read tutorials and notice that I have missed the observation mentioned there.

It does not take me too much time to find a solution to Problem B, but I forget a corner case which leads to a WA.

It also needs some observation for problem C. I use almost the same idea as in tutorials. It is lucky that my first try is correct.

I get stuck in problem D from the beginning, and, until the end of contest. I find that somehow I am quite bad at such kind of problems. During the whole contest, I have never got any chance to get close to the idea in the tutorials.

I really get depressed when I see the top ones in the first page of standings, solving D within 15 minutes. This problem is an almost impossible task for me, while it is just like a warm up practice for them.

But now, what I can do is only to work much harder and practice more. There is no time for depression.

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

    Permutation problems are irritating.

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

    Instead of taking sadness from this round, take this: Whenever there is a question of applying operations some number of number. Try to think of applying operations in reverse.

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

Last line of tutorial of problem H: shouldn't it be "if $$$a_{l-1}\neq a_l$$$" ?

»
3 years ago, # |
  Vote: I like it +24 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).

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

OperationForces xd

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

Is H too similar to this problem? 1329D - Dreamoon Likes Strings

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

An only *3000 problem I?? I think the difficulty is too underestimated for such a huge-amount-of-code data structure problem.

By the way, ♪♪Super Idol的笑容 都没你的甜♪♪ XD. Is that song also got popularized in Singapore?

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

wrong answer expected NO, found YES [32nd token] problem D (Test: #2) can i find this test case somehow?

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

I think there is a typo in editorial for D. For the line

Otherwise, we delete an occurance of ai in S and decrement j. If we cannot find ai in S, it is impossible to transform b to a.

Instead of decrement j, it should be decrement i.

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

In editorial of F1: "Proof: (⇒) There exists a cycle decomposition of the graph that uses at least cnt1+1 cycles. Since a single element of 1 can only go to a single cycle, there exists a cycle without 1."

We are basically decomposing such that each cycle has only one occurrence of element 1. Why don't we need to do for elements 2, 3,...

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

    Because we only want to prove that there exist a cycle without $$$1$$$? So we do not have to care about what happens to any other element

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

F1 the Checker comment said "wrong answer B does not have the minimum possible sadness (test case 33)"

7
7 2 5 4 7 4 2

I Print 4 7 2 5 2 7 4

Why I Wrong answer?

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

    Your array only has sadness $$$4$$$, while the maximum has sadness $$$5$$$.

    Construction of sadness 4
»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Dislike for referring to politics in task E

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

I am still confused about the graph representation of problem F1/F2. Why can we build the graph by rep(x,1,n+1) al[arr[x]].pub(brr[x]); in the sample solution of F2.

As far as I understand, a permutation has a cycle representation, for example, the permutation 1 2 3 4 5 -> 1 3 5 2 4 can be represented by circles $$$(1)(2,4,5,3)$$$. But it seems that the construction in the solution is different from this kind. So far I couldn't understand where the idea comes from. Can anyone post some detailed tutorials or other related resources or problems?

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

Edit: Deleted.

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

in problem F1 ,why the lower limit of number of swaps of every cycle of length x equal to (x-1)?

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

    For example, if $$$x=5$$$, we can turn 1 2 3 4 5 into 2 3 4 5 1. And that costs at least 4 swaps.

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

      ok but why the number of swaps can't be less than x-1 in this example?

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

        You can think that there is an edge from $$$a_i$$$ to $$$b_i$$$. If we let $$$b_i=a_{i+1}$$$, it will form a cycle. In each swap we can only let at most $$$1$$$ number to it's right place, so we should have at least $$$x-1$$$ swaps to turn $$$a_i$$$ into $$$b_i$$$.

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

          can you please explain the construction part in F1?

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

            consider the following example : 1 2 3 1 2 it contains two cycles :(1 2 3) and (1 2),

            find all of these cycles and shift them left by 1 , so the cycles after shift will be (2 3 1),(2 1) respectively.

            then put these cycles in their original positions in the array, so the array will become :2 3 1 2 1

            code
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    The proof by SpadeA261 isn't too correct

    In each swap we can only let at most 1 number to it's right place

    Take the cycle of size 2, in 1 swap we can move both numbers into its right place.

    A correct proof is as follows.

    There are $$$2$$$ types of swaps (pretend the trivial swap that swaps an element with itself doesn't exist):

    • swaps that swap elements in the same cycle
    • swaps that swap elements in different cycles

    In the first type, the number of cycles will always increase by $$$1$$$. In the second type, the number of cycles will always decrease by $$$1$$$.

    Anyways we can see that the number of cycles can only increase by at most $$$1$$$. So When there is a single cycle of length $$$x$$$, we need at least $$$x-1$$$ moves to break it into $$$x$$$ cycles, with all length $$$1$$$.