1775D - Дружелюбные пауки broken checker. My submission 367916049 passed the sample while I output values instead of indices. For input n=7 I printed bi=15 (it should be between 1 and 7) and got OK.

[problem:802A] in Russian statement: "уже есть книга нужная книга"

1158A - Праздник и конфеты

"g_j is equal exactly to the maximum among values b_1j, b_2j, ... " — seems should be a_ij instead of b_ij

Also in Russian statement used capital "И" right before this part

Damirca anotherworld Axire Northern Eurasia, Russia, Nizhny Novgorod State University

Is there a way for unofficial (without prizes) participation for Huawei employees?

When you got 299.97 of 300 points trying to reconstruct the minor haplotype in Problem 4:

Trying to implement something "smart" in F I accidentally got Accepted with "stupid" $$$O(n*n)$$$ (or even $$$O(n*n*m)$$$) solution. After removing all unnecessary trash it has only several lines of code: 118716718

In particular it uses the following code:

	rep(i, n) rep(j, i)
		ans += ...;

where $$$n$$$ — the size of a current equivalence class.

It seems C++ is too fast :) and, probably, the tests do not cover the worst case for this solution. Also please note, that all string are different, so the maximum size of an equivalence class is $$$200000/8 = 25000$$$.

Yes, you are correct. Thank you!

A small suggestion for improvement such type of problems.

Since your solution is tested only on 30 tests of 50 during the round, there is no guarantee that this solution will work correctly on the other 20 tests. So you have to create more "careful" solutions. In particular I "asked" my program to run only 4 seconds (while 5 or even 5.5 seems to be OK too) and have removed some optimizations. But I was not sure that my solution works properly till end of the system test, because code is very large and complex. Also the time measurement is a bit unstable, so you have to be very very careful.

From the other hand, I enjoy the CodeChef challenging problems system:

Once you may test you solution fully, you may focus on new optimizations/ideas. May be it will be good to implement something like this here.

BTW, thanks for the great competition!

Many years ago I added a purple (or even blue) user SoMuchDrama to the friends just because of his funny nickname — I believe that people often dramatize too much. For a long time this user was the only in my friends list didn't know in the real life. It seems that one day I deleted him from the friends list accidentally, but I always remembered him and told about him to my students when they complain instead of training.

When the VK Cup elimination round finished I have found SoMuchDrama in the final standings — several positions above me. Now he has red color and have advanced to the finals! SoMuchDrama, I'm proud of you!

Since the competition is finished I can share some outstanding results from C3:

(a^b)mod M == (a^(b%(M-1)))%M for prime M, see Fermat's little theorem and Euler's theorem for general case.

You should satisfy condition d <= t.

At Kharkiv Winter Programming School 2014 my contest problems were mostly related to Dota2. Just see gyms 100374 (junior league) and 100375 (high league). I hope you enjoy samples for problem H :)

However problem L has buggy tests still...

According to regional rules: "Each team consists of three contestants and may have at most one official reserve. Teams with fewer than three are ineligible."

The same question about T-shirts.

Actually I have a Messi t-shirt :)

We multiply the number of candies by 0.9 every day, so it decreases fast — it will be enough about log(n) / log(1 / 0.9) days, 378 days in the worst case.

While 0.9³⁶⁵ is about 2e-17 :)

In the solution c0[i] — amount of digits i in the original (input) number. ''contains all digits'' — a meant ''contains all digits which the input number contains'' i.e. if c0[i] > 0, c[i] should be > 0 too.

Now it is published, in several hours, as promised :)

It seems that problem is in float type which handles big integers poorly. Probably exact precision is compiler-dependent; anyway I recommend you to avoid non-integer operations in such problems.

Just replace

if (k * days + m >= ceil((float)n / 2))

To

if (k * days + m >= (n + 1) / 2) 

and you will have the correct answer.

1067311732=6^4*7^7+4

387426044=5555+9^9

Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).

2 lines, 100 randomly generated 0 and X each

39259424579862572

It can be proved that the greedy approach is correct. Of course, it can be solved by DP too.

1000000000000000000

2846161151=7*9^9+8^9

Yes, it is not very difficult, so it is only 1500 points comparing to standard 2000.

987654320023456789

Yes, you are right!

Fixed, thanks!

Corrected, thank you!

Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).

Probably, you have to flush your standard output. Use

cout << endl;

or

cout << flush;

or

fflush(stdout);

when you want to see your output data immediately.

As mentioned in the editorial, it is not necessary to delete the vertex explicitly — we may just assume that the corresponding edge has length 0. So, we may use a significantly simpler dfs — just calculating heights, without the tree rebuilding.

Code mk.II

Sure: code

Let vertex W = LCA(U, V) so X (a deleted vertex) is a part of the path U-V if and only if X is an ancestor of U or V, but not W (i.e. X is ancestor of exactly one of the path ends).

I used sqrt-decomposition: new DFS+LCA every 400 queries.

"We have wrong checker. This picture submissions will be reevaluated."

Yes, despite of the time of the issue (1:47) it has a big influence to results. You would have been able to check/debug your code, challenge somebody or even solve another problem. I got WA#1 (now Pretests Passed) at 1:47:30 and wasted 12 minutes, while rng_58 solved E at 0:09... (however, unfortunately I'm not rng :D )

I think, jury should system test all WA#1 submissions and select the first passed (if there are such submits :D) as the final result.

What about sdya and Seyaua? Probably "sd"=="Sobolev Dmitriy" and "Se"=="Sobolev Eugeniy", but have no idea about "ya" and "yaua"...

Regarding problem D. I'm surprised that even tourist used "manual" if-if-if-if approach. My "algorithmic" solution is similar to yours one, but without brute force for Gabriel. So,

1. Generate all the possbile figures
2. Iterate through all the figures
3. To check, whether it is possible to use selected figure — iterate through all possible positions for this figure on the grid
4. If for some position the grid is divided to connected components with sizes X*K, the figure is "solvable". Do not try to split the grid using brute force — just believe, that it is possible :)
5. If there is an "unsolvable" figure, Richards wins, otherwise — Gabriel wins

I didn't strictly prove statement 4 (I didn't even try, since didn't have paper and pen :D ), but it seems that it may be incorrect only for significantly larger sizes than 6 (I expect problems starting from sizes about 14-16)

So the solution is O(number_of_figures * (R*C)^2)

Information from the main page of the competition:
"Due to organizing difficulties probably we postpone the finals to end of June. We try to do our best."

I recommend to wait for an update before buying tickets to the finals :)

We used a simple greedy approach in problem C: find a position+orientation for pair house+garden which gives the most points, fix these house+garden at the position; then find the best position for another pair house+garden (including that we have already pasted previous pairs) and so on while the bonus from new house is positive. It gave 3rd-5th places for most test before the frozing. A way to improve it: try to remove one pair house+garden and place another pair (with probably better result) on the field and repeat such operations while possible. This increases result only by 2-5% but it was enough to be placed 1st-2nd on the big tests (5-10) at the final scoreboard, 997 points in total.

How to spend time solving D:

1. Submit d1
2. Receive "Internal Error"
3. Wait 20 minutes
4. "Now talking in #d
   NIN: When will our d1 be re-evaluated?
   @Igor2_not_org: hmm, did i miss something, why should it be reeval'd?
   NIN: our submit had status "Internal Error, will be reevaluated
   ...
   @Csirke: NIN: Checking
   @Csirke: NIN: eval should be fixed now"
5. ????
6. PROFIT!!!

There is a similar problem at Timus Online Judge: Fat Hobbits

We received an official invitation several minutes ago. So, try to check your e-mail)

I'm not sure about problem "Beads", but other problems were really nice! The only exception: as for me, problem "Passing" was tiring a bit. Sometimes it was hard to deal with output like "Wrong Answer: switch with a car, line 69" or "Wrong Answer: Trains intersection, line 52111" :) Anyway, it was very interesting!

Also, I enjoy limit s >= q/10 to accept solution in problem "Rainfall". Due to some bug we have only about 700 correct answers of 6663 in output for test 7 submitted in last 5 minutes.

Thanks a lot for the contest!

BTW, what is the reason for such delay in publishing the final results?

Editorial is published. Sorry for the delay.

Editorial for problems A-E.

Yes, he did.