paulica's blog

By paulica, history, 5 months ago, In English

Hi everyone!

The fifth round of COCI will be held tomorrow, February 13th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by bukefala, jklepec, mkisic, valkyrie and me.

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

Hope to see you tomorrow!

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

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Reminder: the contest starts in one hour.

»
5 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Can the task "Planine" be represented using line segments? My idea, was to find the leftmost point Li that can light valley i and the rightmost point Ri that can light valley i. This can be done using similar triangles by simple math. Then we have pairs [Li, Ri] for each valley and we sort them by Li increasing. Finally we find the least number of points such that each point belongs to at least one of the [Li, Ri] segments.

This solution, however, fails one of the 30 point tests and one of the 60 point tests (possibly because I compare doubles wrongly).

Other then that, a really nice contest — I enjoyed solving other problems very much! The last problem kept me entertained for quite some time, tho I managed to come up only with the 15 point DP solution.

Lastly, it felt like a balanced problemset, at least to me. Thanks to the authors again! :)

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

    That is how I solved it. However, you need to keep in mind that the points Li, Ri aren't necessarily determined by the slope of the edges of the valley. There might be a different peak that is so tall that it further restricts the range. This can't happen for the 20 point test case because the peaks are all at the same height.

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

      Oh, now that makes sense. Thanks for the explanation!

      UPD: Just one question. In that case how do you determine the range of point i efficiently? I can think of an N^2 solution, but not the N or N log N one.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it
        Spoiler
»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Will we be able to upsolve the problems?

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

    You can upsolve the problem in the tasks section of the evaluator [HONI 2020/21].

»
5 months ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Some people asked me p3 solution so I am putting it over here as well

p3
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Question
    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it +23 Vote: I do not like it

      Spoiler

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      answer
»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

how to solve Task "Po" ?

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

    Observe that for every sequence of contiguous elements ai, ai + 1, ai + 2, ..., ai + k it is optimal to increase them by ai if none of them are lower than ai. Now having that on our mind, it is easy to implement an algorithm that solves it.

    For every element of the array you should keep the index of its closest (on the right) element which is lower than it. This is a standard problem that can be solved in O(N) using stack.

    Next, you should keep difference arrays, e. g. diff[i] = a[i] — a[i — 1]. This helps us because we can reconstruct every element a[i] as a[i — 1] + diff[i].

    Now that you've got these two you traverse elements from left to right and represent current element of array as ar[i — 1] + diff[i]. In case it is greater than zero, than increase answer by 1 and increase diff[next_greater[i]] by current element's value (as we didn't decrease elements on its right by current value). Otherwise we just continue iterating over the array.

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

Really enjoyed contest, thanks a lot! By the way, how to solve E (got only 55 points)?

  • »
    »
    5 months ago, # ^ |
    Rev. 5   Vote: I like it +20 Vote: I do not like it

    Spoiler

»
5 months ago, # |
  Vote: I like it +36 Vote: I do not like it

You can solve all problems here: https://oj.uz/problems/source/541

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

Good quality round! I enjoyed the problem set.

My score was 285 — 17th place, Scores: 50 70 110 0 55

I wanted to share my approaches to some of the problems constructively,

Here are some of my solutions, guided with constructive hints.

  • The hints are to be read sequentially! Hint x for x > 1 assumes that you have read Hint x-1 before.
  • The final solution also assumes that you read all of the hints.

Problem 3: Magenta

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Final solution

Problem 5: Sjeckanje

TODO Tomorrow morning as it's midnight :(

Let me know if you have any comments or feedback on the provided editorials, FiveSixFiveFour.

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

    Loool I got mentioned here cuz you signed your name I think.

    Hope you are doing well, Lior.

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

      You again :p

      Yeah in the first revision I accidentaly mentioned you instead of myseld

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

    Is it just on my side or have the spoiler tags broken? All of a sudden all of the text escaped the hint blocks and everything is shown, weird issue :(

    I worked hard on this editorial, sad to see codeforces ruined the style...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What happened to the hints for Problem 5: Sjeckanje? Really needed a hint for that one :(