### Denisson's blog

By Denisson, history, 4 years ago, translation,

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.

### 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.

### 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.

### 887F - Row of Models

Author: Denisson.

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

• +491

 » 4 years ago, # |   +16 What about English ?
•  » » 4 years ago, # ^ |   +83 It will be soon
 » 4 years ago, # |   0 Can Someone Explain Problem B Div 2
•  » » 4 years ago, # ^ |   +5 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 int n; cin >> n; int x; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 6; j++) { cin >> x; cnt[i][x] = 1; } } int last = 0; for (int i = 1; i <= 999; i++) { if (i < 10) { if (cnt[1][i] || cnt[2][i] || cnt[3][i]) { last = i; continue; } else { break; } continue; } if (i < 100) { if (cnt[1][i % 10] && cnt[2][i / 10] || cnt[1][i / 10] && cnt[2][i % 10] || cnt[2][i % 10] && cnt[3][i / 10] || cnt[2][i / 10] && cnt[3][i % 10] || cnt[1][i % 10] && cnt[3][i / 10] || cnt[1][i / 10] && cnt[3][i % 10]) { last = i; continue; } else { break; } continue; } if (cnt[1][i % 10] && cnt[2][(i / 10) % 10] && cnt[3][i / 100] || cnt[1][i % 10] && cnt[3][(i / 10) % 10] && cnt[2][i / 100] || cnt[2][i % 10] && cnt[1][(i / 10) % 10] && cnt[3][i / 100] || cnt[2][i % 10] && cnt[3][(i / 10) % 10] && cnt[1][i / 100] || cnt[3][i % 10] && cnt[1][(i / 10) % 10] && cnt[2][i / 100] || cnt[3][i % 10] && cnt[2][(i / 10) % 10] && cnt[1][i / 100]) { last = i; continue; } else { break; } } cout << last << endl; 
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -7 Thanks
•  » » » 4 years ago, # ^ |   0 Can you please explain why it will never be greater than 98 ? I mean not by the code, logical reasons behind it.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 to form all the numbers having two same digits (11 22 33 .. 99), you need to have 18 digits (2 each from 1 to 9) which can be maximum digits you can have if n is 3. (6 digits of each cube) And even to form numbers ending with 0 (10, 20, ... 90) you can't have 2 9s
•  » » 14 months ago, # ^ |   0 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?
 » 4 years ago, # |   +1 Code checking all possible combinations.Is complexity O ( n! * 20^n ) ?
 » 4 years ago, # |   0 Can Someone Explain Problem A Div 2
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 I have to admit the contribution spike was pretty fun to watch while it lasted
 » 4 years ago, # |   0 How to solve DIV. 2 F
•  » » 4 years ago, # ^ |   0 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.
•  » » » 7 days ago, # ^ |   0 on step 9 the complexity is up to n ^ 2 / 4 so how can it pass ?
 » 4 years ago, # |   0 The following is a C++14 Depth-First Search solution for problem 887B - Cubes for Masha.32040746
•  » » 4 years ago, # ^ |   0 I wonder why I'm seeing the word "Knight" in quite a few handles.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Perhaps you'll see one day "The United Knights of Codeforces". :-)Best wishes
•  » » 4 months ago, # ^ |   0 fantastic
 » 4 years ago, # |   0 In problem D, how to understand “The answer is either 0 or the moment of time right after an event occured. ”
 » 4 years ago, # |   0 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?
•  » » 4 years ago, # ^ |   +3 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.
 » 4 years ago, # | ← Rev. 3 →   0 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. 32108240Best wishes
 » 4 years ago, # |   -33 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!
•  » » 4 years ago, # ^ | ← Rev. 3 →   -15 We will look forward good contests from Denisson. Good luck to all.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -17 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?
 » 4 years ago, # | ← Rev. 2 →   0 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
 » 4 years ago, # |   0 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 inputplz help me