Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Endagorion's blog

By Endagorion, history, 3 years ago, ,

This time I've decided to play with spoilers to faciliate the presentation as some of the guys here did before. Tell me what you think about this write-up!

Problem A. Shifts

Topics: dynamic programming.

Summary: the first "hard" problem of the contest. Knowing your basic DP problems helps a lot, but coming up with the precisely correct solution may take a lot of persistence.

Solution: Suppose that we are allowed to make left circular shifts as well as right ones.

Can you solve the problem in this case?
What is the difference when we have only right shifts?
Challenge (hard/research):

Problem B. Number as a gift

Topics: greedy.

Summary: a gatekeeper for inexperienced and/or impatient contestants. Many details to take into account, but otherwise tractable.

Solution: Since we aim to maximize the number, let us look what is the largest first digit we can possibly place. Let d denote the first digit of n.

There are several cases...
In some of these cases the rest is easy to find...
While in others we have to involve further...
How to proceed?
The complexity is...
Still WA?
Challenge (easy):

Problem C. Recursive Generator

Topics: hashing/string algorithms.

Summary: while this is a simple problem, some approaches are better than others in terms of complexity, memory, and implementation tediousness. Pick your poison!

Solution: As a start, how can we prove why the Fibonacci sequence as described in the statement is not 1-recursive?

Assume that it is...
Can we make this into a criterion for k = 1?
What about extending this to any k?
How to check is the sequence has no k-contradictions?
Finally...
Challenge (easy/exercise):

Topics: greedy, sorting, implementation.

Summary: while the solution is not exactly evident from the start, one has to jumps a lot of hoops and dodge a lot of spikes to avoid all possible mistakes with precision, query limit and whatnot.

Solution:

Can we solve the problem if we know the vendor's values of d?
What to do if we do not know d_i's?

This pretty much concludes the idea description.

Still, there are many nasty details...
Challenge (medium):

Problem E. Manhattan Walk

Topics: maths, shortest paths in graphs.

Summary: even if you don't come up with a simple mathematical solution, graph algorithms save the day. Easy!

Solution:

Looks standard, right?
I'm lazy, can I do better?
Challenge (easy, I gueess):

Problem F. Tree Game

Topics: game theory, graphs, math.

Summary: frankly, I anticipated a lot more solutions on this problem. All ideas seemed basic to me, and the code is very easy. Still, it seems that cracking the whole thing was not that simple. Did you enjoy solving it? =)

Solution:

Phase 1!
Phase 2!
Phase 3!
Assemble?
Challenge (nasty):

• +255

 » 3 years ago, # |   +34 D and (especially) F are great! Thanks.
 » 3 years ago, # |   +43 Thank you for the great round. I enjoyed to solve A, very interesting problem:D my solution for the challenge of FLet's define . Then the strategy "choose vertex with the lowest value of Dv among remaining vertices" is optimal. Is this correct?And I'll be surprised if the complexity is less than O(POLY·3V) in a general graph.BTW, I was reminded of Euler Getter from F.
•  » » 3 years ago, # ^ |   +10 About the solutionYeah, looks good to me! I had something complex (and probably wrong), but now I see that this should work. I will probably leave the proof out for now though. =)
 » 3 years ago, # |   0 I stupidly used map in C and it passed in less than a second))
•  » » 3 years ago, # ^ |   0 I also did it, but I don't consider it stupid ;p. However that's why I didn't submit it blindly because I was a little scared about getting TLE.
 » 3 years ago, # |   +3 Why is binary search possible in problem C? Suppose it is true for a certain length L that all different consecutive L-length tuples have different neighbours to their right(if they exist). I was not able to find any condition mathematically which could show for any length k (k>L), the given sequence is definitely k-recursive. PS: I tried singe hashing first. It failed. Then I tried hashing with two primes and two big primes. It failed then too. The anti-hash tests were too strong. Can any one tell me which primes did they use for hashing? (in general also).
•  » » 3 years ago, # ^ | ← Rev. 4 →   +4 I think different consecutive L-length tuples arent necessary to have different neighbours to their right. Like a function having different parameter can give out the same value.It is K-recursive if for every i, j that a[i — k... i — 1] = a[j — k... j — 1], a[i] = a[j]. Now assume It is K-recursive, then it is L-recursive (L >= k). Because first if a[i — k... i — 1] != a[j — k... j — 1], a[i — L... i — 1] != a[j — L... j — 1], so we dont have to consider them. If a[i — k... i — 1] = a[j — k... j — 1], now a[i] must equal a[j], so no matter a[i — L... i — 1] is equal to a[j — L... j — 1] or not, it is still valid.
 » 3 years ago, # | ← Rev. 2 →   +14 This editorial is like Christopher Nolan movie. I keep peeling it and new layers keep coming up. At the end I am not sure if I understand the intended story :)
•  » » 3 years ago, # ^ |   0 I hope I didn't go too far on the postmodern side in spite of clearness. Would you like something to be explained better?
•  » » » 3 years ago, # ^ |   0 It's nicely formatted editorial. I had some difficulty following the description for C. I don't understand the transition from Fibonacci series to "if there are two consecutive k-tuples of elements followed by different numbers, then the sequence is not k-recursive". e.g. 1,1,2,3,5,8 seems to match the given condition (1,1 and 2,3 is followed by 5,8) however it is 2-recursive. Source code accompanying the explanation would have been clearer for me.
 » 3 years ago, # |   +5 D's challengeTake random element, compare it with others and recurse to only one half instead of both (after determining which one). If elements less than this element already contribute at least x than we do not care about order of bigger elements.
•  » » 3 years ago, # ^ |   +5 SpoilerBasically it's randomized k-th element algorithm.
•  » » » 3 years ago, # ^ |   +5 SpoilerAbsolutely correct!
•  » » » 3 years ago, # ^ |   +10 SpoilerIn fact it is also possible to adapt standard algorithm searching for median in deterministic way, that works the same way and ensures pessimistic linear complexity, however it would be more complicated to code (but we can make use of nth_element with custom comparator).
 » 3 years ago, # |   0 Pretty good problems and solutions both. Upvote without any hesitation. Problem A is very instructive to me to think more about LCS. However, I have some confusions about the contest rank. In the rules, it only tells that "Top 512 participants according to the cumulative result of all four elimination stage rounds will receive a contest T-shirt." But, what does the "cumulative results" mean? Does elimination stage show final rank? Sorry for disturbs:(
•  » » 3 years ago, # ^ |   0 Yes, the rank is calculated according to the aggregated table at your link.