As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

komendart's blog

By komendart, history, 6 weeks 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, gritukan, 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  

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
5 weeks 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."

  • »
    »
    5 weeks 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.

»
5 weeks 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?

  • »
    »
    5 weeks 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

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how did you find this solution?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you get a proof??

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          for each X >= 15 X=4*k1+6*k2+9*k3
          where k3=x%2 k2=((x-9*k1)/2)%2 k1=(x-6*k2-9*k3)/4
          k(x)=k1+k2+k3
          but 
             if x%2==0 x=4*k1+6*k2 and 
                if x%4=0 k=k1=x/4 else 
                if x%4=2 k=k1+k2=(x-6)/4+1=(x-2)/4=x/4 (because(x-2)%4=0) 
             now if x%2==1 x=4*k1+6*k2+9 so 
                if x%4==1 x=4*k1+9 k=k1+k3=(x-9)/4+1=(x-5)/4=(x-1)/4-1=x/4-1 
                if x%4==3 x=4*k1+6+9 k=k1+k2+k3=(x-15)/4+1+1=(x-3)/4-1=x/4-1
          in end => for each x>=15 k(x)=x/4-x%2
          
          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            k2=(x/2)%2 for simplicity
            
  • »
    »
    5 weeks 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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I now realize the author's solution is also O(1). Thank you for the proof.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How is a picture defined in div2-E?

»
5 weeks 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 ).

»
5 weeks 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://codeforces.com/contest/870/submission/31454655.
Note : Be careful about negative mod.

»
5 weeks 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://codeforces.com/contest/870/submission/31497042

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does picture mean in 870E?