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

"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?

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

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 4 is the minimum composite number so if n % 4 == 0 then ans will be 4. In the other case, we know that for a number there we can use 1 "6" or 1 "9" or both ,and other numbers are 4 or 0. So we should check:

if n-6 % 4 == 0 ans is (n-6) / 4 + 1. // use 1 "6" and others are 4 or 0 else if n-9 % 4 == 0 ans is (n-9) / 4 + 1. // use 1 "9" and others are 4 or 0 else if n-15 % 4 == 0 ans is (n-15) / 4 + 2. // use 1 "6", 1 "9" and others are 4 or 0 else ans is -1 This is my code :http://codeforces.me/contest/870/submission/31454655

Hellow

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.me/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.me/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.me/contest/871/submission/33889909 and http://codeforces.me/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?

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.

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