Gheal's blog

By Gheal, history, 2 years ago, In English

The original blog was deleted yesterday by one of the other authors. We are very sorry about this.

A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

Hints
Solution
Code (C++)
Rate Problem
Post Scriptum

B — Almost Ternary Matrix

Author: Gheal

Solution
Code (C++)
Rate Problem

C — The Third Problem

Author: Gheal

Hints
Solution
Code (C++)
Rate Problem

D — Almost Triple Deletions

Authors: Gheal

Hints
Solution
Code (C++)
Rate Problem

E — Three Days Grace

Author: tibinyte

Solution
Code (C++)
Rate Problem
  • Vote: I like it
  • +55
  • Vote: I do not like it

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

L

»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

So now I will tell why the editorial disappeared.

Basically I was writing the editorial for CodeTON round 3, and I accidentaly posted the editorial to this blog and then saved as draft. Because I thought I leaked the whole round ( but I did not bcs it was saved as draft ), I deleted the blog right away. I am stupid, I know right.

»
21 month(s) ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

In problem C : Let say we calculate for interval pos[0] , pos[1] and mex shouldn't be greater than 2. The above editorial says we calculate value for [l,r] — elements fixed . why should'nt we include range(or elements outside l , r) which are less than l or greater than r such that mex should not be greater than 2 ? Why should we consider elements only in between.

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

    My line of thought was similar to editorial but somewhat different. Hope this gives some insight.

    Suppose there is a subsegment in the permutation in which number x is the MEX. We can prove that because of this, you cannot move x. Why? If you moved it, the MEX of the subsegment that only includes numbers up to x would change. For example, consider:

    0 1 2 3 4

    The segment [1, 2] (1 indexing) has a MEX of 2. If we extend the right boundary until we reach two, we get that segment [1, 3] has a MEX of 3. You can see for yourself that if you move 2 to the left or right, you will inevitably change the MEX of some segment. We can extend this to any number, in that if there is a segment in which that number is the MEX, we cannot move it.

    It then remains to find the numbers in which there is no segment in which it is the MEX. This is quite simple, as the only constraint is that every number below it cannot be on one side. For example,

    0 2 1

    2 CANNOT be the MEX in any segment. Why? Any segment that has 2 as the MEX must also include 0, 1 and not 2. As you can see, this is an impossibility in this scenario. We can extend this further to say that any number can only be moved if it is between at least 2 numbers smaller than it. We can call any number than cannot be the MEX a "hotspot".

    Now we have borders where these numbers can be places. For example,

    0 2 3 1 4

    We cannot swap 2 with 4, since then 0 and 1 would be on the left side of 2, changing the MEX of that segment. We can only swap 2 with 3. We can generate borders of each number as the maximum left and right positions of the numbers below it.

    For each "hotspot", we then calculate the positions available for it to take, and then multiply that with the rest. Here's an example from one of the testcases:

    6 1 2 4 0 5 3

    As shown above, the only numbers that can be moved are numbers 2, 4, and 5 since they can never be the MEX. However, 2 must stay within 0 and 1, 4 must stay within 1 and 3, and 5 must stay within 1 and 3. Also, these three numbers can only swap with themselves. Thus, 2 can only take positions [2, 3], 4 can take positions [2, 3, 5], and 5 can take positions [2, 3, 5]. We can find these positions by binary searching on the locations of the hotspots. For example, in this case the locations of the hotspots are: [2, 3, 5]

    The borders of 2 are [1, 4], of 4 are [1, 6] and 5 are [1, 6]. Thus 2 can only swap with [2, 3], 4 can only swap with [2, 3, 5] and 5 can only swap with [2, 3, 5].

    If 2 takes a position, that leaves one less for 5, and two less for 4. Our answer becomes (2 — 0) * (3 — 1) * (3 — 2) = 4.

    You can try this for yourself in the last testcase. Here is my working code: https://codeforces.net/contest/1699/submission/196560441

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

In Problem D it is easy to check those are necessary conditions but checking they are sufficient conditions is hard one can take 2-3 examples but you will still have doubt that there might be any counter example