### ipaljak's blog

By ipaljak, history, 6 weeks ago, ,

Hi all,

join us on the third round which will be held on Saturday, December 14th at 14:00 UTC.

If you are not familiar with the COCI contest format, we encourage you to read the announcement for the new season. You can also find the problems from the previous rounds here.

Feel free to discuss the problems in the comment section after the contest ends.

See you on Saturday!

• +74

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).
 » 6 weeks ago, # |   +14 A friendly reminder: the contest starts in about 3 hours.
 » 5 weeks ago, # | ← Rev. 3 →   +36 The round is over, we hope you had fun!You can find the unofficial results here.All contest materials (including the editorial) will soon be available. EDIT: tasks, test data and solutions are available here.
 » 5 weeks ago, # |   0 Can we solve problem C with hashes? Lets fix centroid R. We are going to find maximal palindrome that goes through $R$. Hash of string of path $u..R..v$ is $hash(u...R)+ hash(R...v) * base^{dist(R, v)}$ and hash of string of path $v..R..u$ is $hash(v...R)+ hash(R...u) * base^{dist(R, u)}$. This two values must be equal to get palindrome. After changing equality we have: $hash(u...R) - hash(R...u) * base^{dist(R, u)} = hash(v...R)-hash(R...v) * base^{dist(R, v)}$. Maintain map to keep values. Time complexity would be $O(Nlog^2N)$.
•  » » 5 weeks ago, # ^ |   0 The hash should be: Hash of string of path $u..R..v$ is $hash(u...R)+hash(R...v)∗base^{dist(R,u)}$ and hash of string of path $v..R..u$ is $hash(v...R)+hash(R...u)∗base^{dist(R,v)}$ ?Using your hash definition the letter on node $R$ is counted twice, this can be handled...
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you are right. Just maintain hash from one of the sons of $v$, from not $v$. Same for $u$. While updating answer start from $R$ and while your are adding to map start from a son .
•  » » » » 5 weeks ago, # ^ |   0 But if the hash is as I said, isn't easy to break it on function of $u$ and $v$
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Here is my solution
 » 5 weeks ago, # |   +31 Why do you not have any feedback? Looks like the system is capable of testing on samples, what's the problem?That was my first COCI contest and probably last, I don't know how to enjoy no-feedback contests with zero samples (problem C, looking at you)
•  » » 5 weeks ago, # ^ |   +47 It's a technical issue, our grading machines can't handle the load. Most of us are voicing that as a major issue in the last couple of years, but no luck so far.That being said, I really hope this will be the last season of COCI without feedback. We've scheduled some meetings and hopefully will get enough funds for additional hardware and some further development on the judge.