komendart's blog

Editorial Codeforces Round 440 Div.1+Div.2 (and Technocup 2018 — Elimination Round 2)
By komendart, history, 7 years ago, translation, In English

870A - Search for Pretty Integers Idea, preparation, editorial komendart

870B - Maximum of Maximums of Minimums Idea DPR-pavlin, preparation, editorial mHuman

870C - Maximum splitting Idea, preparation, editorial komendart

870D - Something with XOR Queries Idea, preparation, editorial mHuman

870E - Points, Lines and Ready-made Titles Idea, preparation, editorial komendart

870F - Paths Idea, preparation, editorial komendart

871E - Restore the Tree Idea MikeMirzayanov, preparation fcspartakm, editorial mHuman

Also many thanks to coordinator KAN, testers ifsmirnov, vintage_Vlad_Makeev, AlexFetisov and any other people who participates in preparation of contest.

Tutorial is loading...

Code (C++) 31365874

Code (Python) 31365844

Tutorial is loading...

Code 31366254

Tutorial is loading...

Code 31365909

Tutorial is loading...

Code 31366223

Tutorial is loading...

Code 31365959

Tutorial is loading...

Code 31366002

Tutorial is loading...

Code 31368704

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

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

emmmm... where is 870F's solution?

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

I want to know how to proved the conclusion of B "*Also it can be proved that for k = 2 the answer is the maximum of the first and last element."

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

    Consider an array of length n. You know that 2 candidates for the answer are arr[1] and arr[n]. You can get arr[1] as the answer by using the partition {[1,1], [2,n]} and you can get the value arr[n] as the answer by using the partition {[1,n-1], [n,n]}.

    Let the actual answer be some value at index i in the array, so arr[i] > arr[1] and arr[i] > arr[n]. Now, arr[i] has to be minimum possible value in its own subsegment. But, any subsegment containing arr[i] has to contain either arr[1] or arr[n]. In either of those cases, arr[i] is no longer the minimum in its subsegment and can never be the answer.

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

"If minimal number in splitting is neither 4 nor 6 nor 9 than this number will have some non-trivial splitting by induction."

"If this number either 6 or 9...."

Why aren't we considering the supposed non-trivial splitting in Problem C?

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

    If there is some number in splitting is neither 4 nor 6 nor 9 and not any other prime number (to mantain validity of splitting), we will always be able to split it down further. For example, suppose in your splitting you have 26, you can break it down further to 4+4+4+4+4+6, if you have 19, you can break it down to 4+6+9 and so forth. You can even prove this formally with strong induction, with extra care for numbers that don't have a valid splitting

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

There is an O(1) solution for problem C Div2. I couldn't find concrete proof for it other than very weak induction. The solution arises from a pattern. All numbers besides 1,2,3,5,7,11 have answers. You can get this answer by dividing the number by 4 and subtracting 1 if the original number is odd. The pattern can be seen in the DP table.

Here is my implementation: 31373891

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

    Could you please explain how did you find this solution?

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

      Just by observation. I couldn't really prove it.

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

    Actually, authors solution is also O(1). Let me prove your solution:

    Since 4 in smallest composite number, we have to use 4 as much as we can, so, lets see some cases with mod 4:

    if(n%4==0) then answer is obviously n/4

    if(n%4==1) we have to find smallest number which is composite and have 1 mod 4, so it is 9 and if we subtract 9 from n result is divisible by 4, then answer is 1+(n-9)/4 (here if n<9 then answer is -1)

    if(n%4==2) we do same thing with n%4==1, so smallest composite number which have 2 mod 4 is 6 and answer is 1+(n-6)/4 (here if n<6 then answer is -1)

    if(n%4==3) smallest composite which have 3 mod 4 is 15, also, we can express 15 with sum of 2 composites, 6 and 9, so answer is 2+(n-15)/4 (here if n<15 then answer is -1)

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

in problem 870D ,

when n is an odd number . the answer is unique, and we can obtain it by only n questions.

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

How is a picture defined in div2-E?

→ Reply
»
7 years ago, # |
← Rev. 8   Vote: I like it -11 Vote: I do not like it

The following is a C++11 solution for problem 870A - Search for Pretty Integers using bitsets.

31363923

The idea is to have one bit for each digit between 1 and 9 in a bitset< 10 > representation of each sequence to indicate whether or not the corresponding digit exists in the sequence.

Then, the digits between 1 and 9 are checked iteratively in an increasing order for a digit (x) that exists in both sequences. If this digit is found, then it is the one-digit solution.

Otherwise, compute x and y, the minimum digits in the n-digit and m-digit sequences. It is guaranteed in this case that x and y are not equal. The solution is then the two-digit number expressed as max( x, y ) + 10 * min( x, y ).

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

The solution of div-2 C can be made more easy.
As we know that 4 is the minimum composite number so
if n % 4 == 0 ans will be n / 4;
In other cases, as we know that we can use 1 "6" or 1 "9" or both, with 0 or 4 to split a number in maximum possible number of Summands. So we should check:
if (n-6) % 4 == 0 ans is (n-6) / 4 + 1 // using 1 "6" with 4
else if (n-9) % 4 == 0 ans is (n-9) / 4 + 1 // using 1 "9" with 4
else if (n-15) % 4 == 0 ans is (n-15) / 4 + 2 // using 1 "6" and 1 "9" with 4
else ans is -1;
my code : http://mirror.codeforces.com/contest/870/submission/31454655.
Note : Be careful about negative mod.

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

I coded the solution of Problem Div-2 E. But getting TLE on test 23. Could anyone help me figure out why? My Submission: http://mirror.codeforces.com/contest/870/submission/31497042

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

Today I learnt not to use the C++11/GCC 5.1 submission option. I takes basically all of the 3s to read the input data, leaving no time for the solution to run! The C++14/GCC 6.4 option is about 3 times faster. Compare http://mirror.codeforces.com/contest/871/submission/33889909 and http://mirror.codeforces.com/contest/871/submission/33889988 — same code (apart from a debug comment) which exits right after reading the input data on a maximal dataset, totally different runtimes.

I am using ios::sync_with_stdio(false) and cin.tie(NULL).

GCC 6.4 is still about twice as slow as GCC 5.4 on my 7 year old machine — how old are the CF machines?

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

Can someone explain the following test case for problem A?

9 1 5 4 2 3 6 1 7 9 8 9

the smallest number from both the lists are 1,9. And hence the pretty integer should be 19, right? then why the answer is 9? Plz correct me where I'm wrong.

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

    You should look at the case that 9 is present in both the arrays. So using just 9 and forming a single digit number would be accurate as it will become the smallest positive integer.

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

Problem D can be solved by asking queries (0, i) and (i, i) also.

→ Reply