Ahmet.K37's blog

About CROATIAN OPEN COMPETITION IN INFORMATICS (COCI)
By Ahmet.K37, history, 6 years ago, In English

Saturday there will be COCI exam in this link: http://hsin.hr/coci/ You can study for the old COCI's here: https://oj.uz/problems/source/122 Also this site has an online judge. The contest will begin at:17.11.2018.14:00 GMT/UTC and it will take three hours.

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

Good luck to everyone.

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

did the registeration begin?

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

Registrations began. you can go to the site with this link: http://hsin.hr/coci/ look at to contest 2

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

5.00 hours before the exam begins

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

Will it take five hours or three hours (same as the previous one)?

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

Last 1 hour to the contest

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

Is the site down ?

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

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

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

How to solve second? I solved the third but not that one.

Thank you, I got the idea.

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

    How to solve the third?

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

      Main idea: We find the answer by counting the number of the ranges for each bit. For that, root tree at one and calculate top to bottom xor's. Now, traverse the tree and you can count the number of the ranges by counting {(0,0) and (1,1)} or {(0,1) and (0,1)} pairs.

      Code: https://pastebin.com/Sr9EskiG

      UPD: I got AC.

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

    We keep 2 arrays, row[] and column[] which store 2 values; 1 if someone at some point has seen a square that was blocked and -1 if nobody saw it just yet. First we go from left side through all rows, if input at the current row is -1 we set row[current_row] to -1 and continue, otherwise we set both row[current_row] and column[input] to 1. Then we continue to other three sides and we will have 2 cases: 1. if input is -1 then we ask if someone before has seen a value in that row/column before (i.e if element in array row/column is 1), if someone did see it then we print "NE", otherwise continue 2. if input is 1 then we ask if someone before hasnt seen a value in that row/column before (i.e if element in array row/column is -1), if someone didnt see it then we print "NE", otherwise continue

    Code: https://pastebin.com/KNqzESdU

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

    See also Noam's notes below.

    We iterate over the row number/column number. Consider the i-th value in the L array, Li. Since the first Li fields in row i must be empty, we must have that Uj ≠ i - 1 and Dj ≠ N - i for all 1 ≤ j ≤ Li. Also the (Li + 1)th field in this row must be a blocked so ULi + 1 ≤ i - 1 and DLi + 1 ≤ N - i since otherwise this blocked area would have to be empty. Both of these conditions can be checked in O(1) by pre-constructing various arrays.

    Then just do this for U, R and D.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

When standings will be avaliable?

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Brief solutions/hints for the problems (except A because there's no reason to):

B
C
D
E

Edit: Looking at the results, I think my solution to D takes a little too much time. Can anybody else explain their solution? Also for E I'm not sure if my solution can pass in time, I didn't submit it, will check soon.

Edit2: This solution for E recieves TLE on the last 2 testcases when K is 1000, but it passes with 1500. Anyway, did anybody have a better solution?

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

    I spent last couple of hours trying to solve D.

    I'm not quite sure I understand some of your points.

    K should be at least (approximately) . If K is smaller than twice this limit, you solve by doing dp in .

    Do you mean that, if K < NM then we run the DP?

    If K is large enough, then at some point you will jump between 2 adjacent cells.

    I also thought about this, but don't know how to prove it. Do you have some insights?

    ...you solve upto the limit, and find the best pair of points you should jump between (It's probably one with the maximal sum but there's no need to solve further).

    This is the part I am most confused about. Let's say we pick some pair of adjacent cells (x1, y1) and (x2, y2). How do we choose the number of times we'll jump between them and the lengths of the paths from (A, B) to (x1, y1) and from (x2, y2) to (A, B)?

    I was thinking about choosing some lengths k1 and k2, then using DP to find f(k1, x1, y1) — maximum weight of the path from (A, B) to (x1, y1) using k1 steps, same with f(k2, x2, y2). So we are left with K - k1 - k2 jumps that we can do between (x1, y1) and (x2, y2). But what are the limits on k1 and k2 in this case? If we choose some L as the limit (i.e. k1, k2 ≤ L), then the complexity will be , so L cannot be very big. But choosing small L will lead to nonoptimal answer.

    Here's what finally worked for me:

    If we assume that when K is large, we'll be jumping between two cells at some point. Then after some k steps, where k < K, the weight of the optimal path will be increasing by the same amount each 2 steps. In other words for some large enough k, it should be true that

    So we can use this difference for the rest K - k steps and the result will look something like

    But how do we choose large enough k? I don't know :) Maybe someone can help with this?

    Here are some values that I tried:

    • k = NM and k = 2NM, was not enough, giving WA for some test cases.
    • k = 4NM, passes all test cases, but very close to time limit in some.
    • k = 15000, also passes all test cases with run-time <1s, but I think it might not always be optimal when N = M = 100, since for some smaller cases k = 2NM was not enough.
    → Reply