ipaljak's blog

Croatian Open Competition in Informatics (COCI) 2019/2020 — Round #4
By ipaljak, history, 5 years ago, In English

Hi all,

join us on the fourth round which will be held on Saturday, January 18th 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
  • +79
  • Vote: I do not like it

»
5 years 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).

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

A friendly reminder: the round starts in about 3.5 hours

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 9   Vote: I like it +21 Vote: I do not like it

    I am not entirely sure my solution is correct. (Edit: It's correct)

    I split the array in 2 sets, the one in the range [l, r] and what is left. In this sets we have the numbers sorted by indices in the initial array. We see that we only make swaps between numbers in different sets.

    I did dp[i][j][cost] = the biggest amount of debt you can save if you make swaps till the ith from the first set and jth from the second set and spend cost kunas.

    The Recurrence
    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When will the results be published?

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

    They should be up in a couple of minutes, I'll let you know,

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      The results should now be visible under the Results tab in the judge.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does top down 2500*n^2 DP pass on Holding or it TLEs? 2e7 in 2s is kinda tight.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Notice that n^2 is kinda (n / 2)^2, so it should pass (and 2e8 is kinda tight, 2e7 usually fits comfortably)

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

    It should pass, 2e7 in 2 seconds shouldn't be tight at all.

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I spent 1:30 on solving D for + instead of xor, oh

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Did you solve it for +? :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think yes, but it was about 200 or so lines of code (not including prewritten one)

      → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

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

    You can use euler tour + segment tree + trie or dsu + trie(with lazy and a function for merge two tries) over the final tree, in both keep for every node of the trie the most "old" node in the subtree(necessary for search the maximum xor only with the nodes added before the current query)

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

      I used segment trie and got TLE.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I implemented the solution with dsu but put stupidly(r instead r^x) bug and I couldn't submit it on time, so I don't know if my solution would pass

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        My solution passed in one second

        → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Tasks, full test data, and solutions (with editorials) are available here.

We hope you had a good time :)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When I can submit again ? It say "You're not allowed to submit at this time."

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I would say in an hour or so, but my hands are tied in that regard. I'll let you as soon as I hear the analysis mode is up.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the testcases in Holding weak. My slow solution passes all the subtasks. https://pastebin.com/hGzYAsXm

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Hi, I am coauthor of Holding and I was creating testcases for it. We have testcase on which your solution reaches the worst complexity, but running time of it is still low, 1.2sec, and time limit is 2sec. We couldn't put 1sec for time limit because some solutions with intended complexity were very close to 1sec.

    → Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Will the COCI tasks from this season be added on oj.uz?

ojuz

→ Reply