ipaljak's blog

By ipaljak, history, 6 weeks ago, In English,

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!

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

A friendly reminder: the contest starts in about 3 hours.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +36 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +31 Vote: I do not like it

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, # ^ |
      Vote: I like it +47 Vote: I do not like it

    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.