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.
Code (C++) 31365874
Code (Python) 31365844
Code 31366254
Code 31365909
Code 31366223
Code 31365959
Code 31366002
Code 31368704
emmmm... where is 870F's solution?
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."
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.
"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?
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
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
Could you please explain how did you find this solution?
Just by observation. I couldn't really prove 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)
I now realize the author's solution is also O(1). Thank you for the proof.
Good Explanation
in problem 870D ,
when n is an odd number . the answer is unique, and we can obtain it by only n questions.
How is a picture defined in div2-E?
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 ).
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.net/contest/870/submission/31454655.
Note : Be careful about negative mod.
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.net/contest/870/submission/31497042
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://codeforces.net/contest/871/submission/33889909 and http://codeforces.net/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)andcin.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?
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.
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.
Problem D can be solved by asking queries (0, i) and (i, i) also.