Блог пользователя paula

Автор paula, история, 3 года назад, По-английски

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, dpaleka and me.

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

Hope to see you tomorrow!

  • Проголосовать: нравится
  • +104
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Reminder: the contest starts in one hour.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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! :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится
        Spoiler
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Will we be able to upsolve the problems?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

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

p3
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Question
    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

      Spoiler

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      answer
»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

how to solve Task "Po" ?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    Spoiler
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +20 Проголосовать: не нравится

    Spoiler

»
3 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 9   Проголосовать: нравится +36 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Hope you are doing well, Lior.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You again :p

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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