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!
Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).
A friendly reminder: the contest starts in about 3 hours.
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.
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)$$$.
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...
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 .
But if the hash is as I said, isn't easy to break it on function of $$$u$$$ and $$$v$$$
Here is my solution
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)
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.
Give an extra strong sample then. Atcoder has feedback and does this often. It's not everything, but it would significantly change the situation from no feedback.
+1 I think this is the easiest and effective way to compensate this situation
I agree and have considered a similar idea when all hopes of full feedback went down the drain before the beginning of the season. I was thinking about providing the contestants with a batch of "pretests" they can try out locally and have a better feeling about the correctness and performance implications of their solutions.
The idea was rejected, but I would rather not go into the details. In short, this was not easy to achieve in the given timeframe on our local version of the contest.
On the other hand, this could easily be done for COCI since you guys have access to the judge and can simply download an archive with the pretests. We could also automatically grade a small subset of them. To be honest, I don't know why we didn't do this for COCI. I'll try to pitch this idea for the last two rounds.
Now for some good news...
We managed to get the funds and already bought the necessary hardware. The whole thing will most likely be migrated to a new judge and, unless something goes terribly wrong, we should have full feedback on COCI next year. Fingers crossed...