Endagorion's blog

By Endagorion, history, 7 weeks ago, In English,

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):

Problem D. Trading

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):

I'll be glad to hear all your opinions in the comments. Thanks for participating!

 
 
 
 
  • Vote: I like it  
  • +255
  • Vote: I do not like it  

»
7 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

D and (especially) F are great! Thanks.

»
7 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Thank you for the great round. I enjoyed to solve A, very interesting problem:D

my solution for the challenge of F

BTW, I was reminded of Euler Getter from F.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    About the solution
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I stupidly used map<vector, int> in C and it passed in less than a second))

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +4 Vote: I do not like it

    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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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 :)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope I didn't go too far on the postmodern side in spite of clearness. Would you like something to be explained better?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it
D's challenge
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Spoiler
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Spoiler
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Spoiler
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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:(

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the rank is calculated according to the aggregated table at your link.