### komendart's blog

By komendart, history, 3 years ago, translation,

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

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

• +85

 » 3 years ago, # |   +16 emmmm... where is 870F's solution?
 » 3 years ago, # |   0 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."
•  » » 3 years ago, # ^ |   +5 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.
 » 3 years ago, # | ← Rev. 2 →   0 "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?
•  » » 3 years ago, # ^ |   +5 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
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 Could you please explain how did you find this solution?
•  » » » 3 years ago, # ^ |   0 Just by observation. I couldn't really prove it.
•  » » » » 3 years ago, # ^ |   0 can you get a proof??
•  » » » » » 3 years ago, # ^ |   0 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 
•  » » » » » » 3 years ago, # ^ |   0 k2=(x/2)%2 for simplicity 
•  » » 3 years ago, # ^ |   +9 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/4if(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)
•  » » » 3 years ago, # ^ |   0 I now realize the author's solution is also O(1). Thank you for the proof.
•  » » » 9 months ago, # ^ |   0 Good Explanation
 » 3 years ago, # |   +8 in problem 870D ,when n is an odd number . the answer is unique, and we can obtain it by only n questions.
 » 3 years ago, # |   +4 How is a picture defined in div2-E?
 » 3 years ago, # | ← Rev. 8 →   -11 The following is a C++11 solution for problem 870A - Search for Pretty Integers using bitsets. 31363923The 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 ).
 » 3 years ago, # |   0 The solution of div-2 C can be made more easy.As we know that 4 is the minimum composite number soif 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 4else if (n-9) % 4 == 0 ans is (n-9) / 4 + 1 // using 1 "9" with 4else if (n-15) % 4 == 0 ans is (n-15) / 4 + 2 // using 1 "6" and 1 "9" with 4else ans is -1;my code : http://codeforces.com/contest/870/submission/31454655.Note : Be careful about negative mod.
 » 3 years ago, # | ← Rev. 2 →   0 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
 » 3 years ago, # |   0 What does picture mean in 870E?
 » 3 years ago, # |   0 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.com/contest/871/submission/33889909 and http://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?
 » 9 months ago, # |   0 I am not able to decide how good my solution is for 870.A problemMine takes: O(n logn + m logo) whereas editorial takes O(nm) . Now which is better ?BTW my solution(which got accepted) is here. Please correct me if I am wrong in any calculation void solve() { int f, s; cin >> f >> s; int a1[9]; for (int i=0; i> a1[i]; } int a2[9]; for (int i=0; i> a2[i]; } sort(a1, a1 + f); sort(a2, a2 + s); vector its(20); auto b = set_intersection(a1, a1 + f, a2, a2 + s, its.begin()); its.resize(b-its.begin()); if(its.size() != 0) { cout << *its.begin() << "\n"; return; } if(a1[0] < a2[0]) { cout << 10*a1[0] + a2[0] << "\n"; } else { cout << 10*a2[0] + a1[0] << "\n"; } } 
 » 8 months ago, # |   0 Can someone explain the following test case for problem A?9 1 5 4 2 3 6 1 7 9 8 9the 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.
•  » » 5 months ago, # ^ |   0 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.
 » 2 months ago, # | ← Rev. 3 →   0 --------------------- 870B Maximum of Maximums of Minimums --------------------If k = 1 then only the smallest element must be taken so there is no option to split the arrayIf k = 2, then only in this case it is possible to take the largest element in position 0 or n-1 And it is impossible to take the largest element if it were in the middle because it is only k = 2If k> = 3 then the largest element can be taken anywhereSolution : Acceptedint N , K; cin>>N>>K; vectorV; int Max = INT_MIN; int Min = INT_MAX; for(int i=0;i>X; Max = max(Max , X); Min = min(Min , X); V.push_back(X); } if(K==1)cout<
 » 7 hours ago, # |   0 Problem D can be solved by asking queries (0, i) and (i, i) also.