Denisson's blog

Codeforces Round #444 (Div. 2) Editorial
By Denisson, history, 7 years ago, translation, In English

Once again we apologize for making mistakes during preparation.

887A - Div. 64

Author: .tx.

If the string contains no ones then the answer is "NO" as the remainig number must be positive. Otherwise we can find the leftmost one and check if it is followed by at least six zeroes.

Solution.

887B - Cubes for Masha

Author: .tx.

The answer is always less or equal to 98. We can go through numbers from 1 to 99 and find the first one which we cannot make using cubes.

Solution.

887C - Solution for Cube

Author: .tx.

The amount of variants of input data for which the answer is "YES" is not more than 12 without considering rearrangement of colours. They all could be written in an array.

The alternative solution is writing a function of rotating a specific edge of the cube and checking if it is solved.

Solution. Denisson

Solution. .tx

887D - Ratings and Reality Shows

Author: .tx.

We can create two arrays of prefix sums of events given in input. The first one on values (a, b) and the second one on values (c, d). The answer is either 0 or the moment of time right after an event occured. Let's use the method of two pointers. One pointer will indicate an event V after which we want to participate in the talk show and the other one at the moment of time right after its influence ends. Then we can participate in the talk show if the minimum of prefix sums on values (c, d) from elements between pointers is not less than the difference of prefix sums on values (a, b) and (c, d) from element V. Also we must check that Izabella's rating doesn't become negative before participating in the talk show or during its peroid of influence.

Solution. Denisson

Solution. .tx

887E - Little Brother

Authors: .tx, Denisson.

The center of required circle is on a perpendicular to the middle of the segment AB where A and B are two points from the input. If a circle with the center on the segment AB and the radius equal to half of its length satisfies the conditions then it is the answer. Otherwise we can find on which side relative to AB the center of the circle is. Every drawn circle blocks a continious interval of allowed values for the requierd circle. The limits of this interval can be found by using binary search. Now we have to find the least allowed value for the radius. It can be done, for example, by using method of scanning line.

Solution. Denisson

Solution. .tx

Solution. cdkrot

887F - Row of Models

Author: Denisson.

For every element of an array ai we can check x elements on its right. If there are no elements less than ai we will mark it as "-1" and call it "bad". If there is exactly one element then make an edge from ai to this element. Otherwise swapping elements of the array will never make ai "bad". If there are no "bad" elements in the array then the answer is "YES". Otherwise we should find the leftmost "bad" element in the array bad. X elements after it are not less than itself. All elements before it are also not less than itself because otherwise an element less than bad would be "bad" too. Swapping bad with an element in suffix also makes no sense because its place will be taken by lesser element and the position will remain "bad". Thus, swapping bad with other element of the array makes no sense. The only way to satisfy the conditions is to swap one of x elements after bad with other element in the remaining suffix without considering a segment with length x after bad. Let's try to do it obviously. Then the following conditions must be satisfied. Consider choosing an element y in the remaining suffix. Then the swap can be the answer if y < bad. Also suffix after y and the segment between y and the segment with length x after bad must not contain "bad" elements. An element, which we swap y with, from the segment with length x after bad must be less than any adress on y. Also we need to check that after the swap on the right side of y we can find an element less than itself no further than x.

Time: O(n) or O(nlogn).

Solution. Denisson

Solution. Denisson

  • Vote: I like it
  • +491
  • Vote: I do not like it

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

What about English ?

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

Can Someone Explain Problem B Div 2

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

    Here is longer, but more understandable code. Approach is iterating numbers from 1 to 999 and checking if we have all digits in cubes.

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

    I seem to be misunderstanding something. How can we make 1 in test case 1? The way I understood the problem, we have to pick one digit from each die to form a number. To form 1 we need two 0s and one 1, right? 0s are available only in the 1st and 2nd die, and the third one doesn't have 1. Can someone please help?

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

Code checking all possible combinations.

Is complexity O ( n! * 20^n ) ?

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

Can Someone Explain Problem A Div 2

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

    In problem A, its enough to check if there are at least 6 zeroes after the first one. Since you can only delete the numbers, in order to make a positive number divisible by 64 in binary notation, you need to have 6 trailing zeroes at the end, and this is only possible to achieve if you have 6 or more zeroes after the first one.

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

I have to admit the contribution spike was pretty fun to watch while it lasted

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

How to solve DIV. 2 F

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

    Accepted solution 32144259:

    1) Place 0 (designer) to the end for simplicity.

    2) Build min segment tree (MST).

    3) Find first error position F on [0; n-k] using MST. Go forward. {n-k is because designer excludes errors for bigger indeces.}

    4) Find last error position L on [F+1; n-k] using MST. Go backward. If there is no error, L=F.

    5) Intersection of all error scopes is [L+1; F+k]. It is the only segment where one can put a value to fix errors. {It's obvious when all variants are pictured.} If this segment doesn't exist, answer is NO. {In other words, one can't fix all errors using one swap.}

    6) Donor segment is [L+k+1; n-1]. There may be values which are (a) less than all errors and (b) can be swapped. If this segment doesn't exist, answer is NO.

    7) Check dependencies for every i-th value on [L+1; n-k-1]: if i-th value is bigger than only one j-th value on scope [i+1; i+k], store i to j-th dependency list.

    8) For every i-th position on intersection [L+1; F+k] store min in scope [i+1; i+k].

    9) For every pair i:j (i on [L+k+1; n-1] and j on [L+1; F+k]) check whether their swap is correct:

    a) Fix errors: i-th value is less than F-th (the least error).

    b) Don't add error to j-th position: min (from step 8) for j-th position is less than i-th value.

    c) Don't add errors to positions dependent on i-th: i-th value has no dependecies (from step 7) or dependencies are not broken when value is moved to j-th position (last dependency index is less than j).

    First correct swap gives YES.

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

      on step 9 the complexity is up to n ^ 2 / 4 so how can it pass ?

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

        I can't compose a case where searching for the first correct swap requires checking all i-th values and all j-th values for every i-th value. (Perhaps the authors can't either.) And I can't prove that such case can't exist. (Perhaps the authors can.)

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

The following is a C++14 Depth-First Search solution for problem 887B - Cubes for Masha.

32040746

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

In problem D, how to understand “The answer is either 0 or the moment of time right after an event occured. ”

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
The answer is either 0 or the moment of time right after an event occured

-- Why? I think that it could be when we need to use "blue" len. 

Then we can participate in the talk show if the minimum of prefix sums on values (c, d) from elements between pointers is not less than the difference of prefix sums on values (a, b) and (c, d) from element V

Not obviously for me. Why?

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

    I have understood both cases. It seems to me that there is a mistake in editorial. It says that 

     min(cd[i]) >= ab[v-1] - cd[v-1]

    It doesn't true.

    How can I prove it? We need that:

    ab[v - 1] + (min(cd[i]) - cd[v - 1]) >= 0

    Then we can get such thing:

    min(cd[i]) >= cd[v-1] - ab[v-1]

    Denisson, fix it if I am right.

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

The following is a C++14 solution for problem 887C - Solution for Cube without rotation.

The solution introduces a face_t C++ structure that holds the colors of the four squares in the face. The data input is stored in a 6-item array of the face_t structure.

Since three bits only are sufficient to store any of the six color numbers, the face_t C++ structure stores the colors of the four squares in four 3-bit width bit-fields.

A one-move solution must satisfy that two opposing faces are ordered, and the colors of the four squares in the other four faces are ordered in pairs such that exactly one more either clockwise or anticlockwise causes all four faces to be ordered.

32108240

Best wishes

→ Reply
»
7 years ago, # |
  Vote: I like it -33 Vote: I do not like it

What is this? why do you all upvote this? this should not be upvoted! by doing this you have made Denisson's Contribution positive! I am really disappointed in the Codeforces community! shame on you all!

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

    We will look forward good contests from Denisson. Good luck to all.

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

      Shame on you too! double shame on you! people should realize that when they make a contest they should think for one second that their problems should be good and before the contest even read the problem statements and as i have seen they even messed up the Announcements to! they messed up but they could have fixed it faster not 1 hour in to the contest! but to speak the truth i am a little heart broken from what you said, apologize for what you said please.

      P.S: how do you know that i haven't made a contest before or i don't have one proposed?

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

the wording of problem A is a bit weird (in light of tests): it says "if it's possible to remove some digits", and for test case 1000000 you cannot remove anything to keep number positive and divisible by 64 EDIT: i missed that it was clarified later, sorry for the noise

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

for 887B if input is :- 2 0 2 9 8 1 7 6 7 4 3 2 5 why output is 9? as 1 and 0 is in input

plz help me

→ Reply