ipaljak's blog

By ipaljak, history, 9 months 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

»
9 months 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).

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
9 months 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.

»
9 months 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)$$$.

  • »
    »
    9 months 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...

    • »
      »
      »
      9 months 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 .

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But if the hash is as I said, isn't easy to break it on function of $$$u$$$ and $$$v$$$

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here is my solution

»
9 months 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)

  • »
    »
    9 months 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.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        +1 I think this is the easiest and effective way to compensate this situation

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can submit all problems here: https://oj.uz/problems/source/444