keko37's blog

Croatian Open Competition in Informatics (COCI) 2021/2022 — Round #5
By keko37, history, 3 years ago, In English

Hi everyone!

The fifth round of COCI will be held tomorrow, March 5th 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 ominikfistric, Bartol, pavkal5, and me.

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

Support for rust will be added either for the next round or for the next season.

Hope to see you tomorrow!

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

Comments Comments (21)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

wow

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

I left the contest when I read the first two problems, Sorry, But this is an Olympiad contest or heavy implementation contest? I didn't like the first two problems this time ...

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

    I agree that A was super toxic but imple for B is quite simple and short?

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

      What is your implementation for B? I rotated the table by 45 degrees and then it can be easily solved, but it wasn't short at all.

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

        https://pastebin.com/eP4wtRVr

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

          Thanks! That implementation was so elegant :orz:

          One small question tho, what do a, b, c, d do here:

              a=min(a,i-j),b=max(b,i-j);
    c=min(c,i+j),d=max(d,i+j);

          I know that they will help you to calculate the area of the diamond (if it is), but I don't know how does it relate to i+j and i-j.

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

            It's just to rotate $$$(i,j)$$$ by 45 degrees. You can read here.

            Here is a visualization.

            So the smallest rectangle that bounds the area after rotating 45 degrees is something like $$$[a,b] \times [c,d]$$$

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

Is there any simple solution for task Radio? My approach is really ugly and I don't think it's the intended one...

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +34 Vote: I do not like it

    GCD(x, y) != 1 iff exists some prime number that divides both x and y.

    Let's say A[1], A[3], A[4], A[10] are divisible by p, then segments [1, 3], [3, 4] and [4, 10] are "bad", i.e. answer is "DA" if the given segment contains some "bad" segment.

    It is clear that the number of bad segments doesn't exceed O(q*k), where k is the maximal number of prime divisors of some number (k <= 7).

    Let's update each l with the minimum r such that [l, r] is bad. The answer is "DA" if getmin(l, r) <= r.

    Complexity O(n + qklog(n)), where k<=7

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

      Great. I'm so stupid that I used 2D data structures for the last part of the solution. Thank you so much for sharing your solution.

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

      it would be GCD(x, y) != 1 iff there exists some prime number that divides both x and y. also, k <= 8

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

        Yes, you are right, that should be GCD(x, y) != 1.

        But k <= 7 as 2*3*5*7*11*13*17 = 510510 <= 1e6 and 2*3*5*7*11*13*17*19 > 1e6.

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

      Can you show me your code

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

How much does it take to post the tasks in the archive? I think I fixed my bug for Radio and I'm very eager to submit it.

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

How to solve Usmjeravanje(the last problem)?

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

    Here is my solution:

    The problem is essentially just directing the edges in a way to have the minimum possible number of total SCCs.

    Let's say that we directed all the edges from left to right initially. Some edges won't have an impact on the compressed SCC graph. An example of this is if you have the edges "4 1" and "2 3". If you include the edge "4 1", you can notice that adding the edge "2 3" doesn't do anything since node 2 on the left side is already connected to node 3 on the right side. Let's call edges like "2 3" in this example with the term "useless" and all other edges "useful". There are many ways to find the useful edges but I used a segment tree RMQ to do it. After finding all the useful edges, I direct the useful edges from left to right and I direct the useless edges from right to left. After, you can just build the graph and run any SCC algorithm to count the number of SCCs.

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

      The approach focusing on directing the edges from left to right is cool! thanks!

      I was stuck on directing both directions simultaneously and failed to get any points :(

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

      It's also possible to direct the edges without RMQ by using a simple greedy approach: Sort the edges decreasing by x and in case of equal x increasing by y. (call sort on (-x, y)). Now go through the edges in sorted order and maintain the minimum y seen so far (initially -inf). If y < minY, direct the edge right (from left to right), else direct it left.

      The reason why this works can be explained by "useful" and "useless" edges as well: If y >= minY, we could move to the left and increase our x until we reach the edge leading to minY. So directing the edge right would be useless. Otherwise we can reach a lower y and the edge is useful.

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

Can someone help me optimize my solution for problem B?

Let's define a function f(x,y,z) = number of '#' inside the diamond with its top cell being (x,y) and its size being z. We can calculate this function using prefix on diagonals and some observations using triangles.

Then, I binary searched the length of the smallest correct diamond for each cell(x,y). There is at most one correct diamond for each cell so if it exists then I add 1 to the total answer.

Complexity: O(n*m*log(n)), I got TLE on the second sub-problem.

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

Here is a brief description of the solution to task Fliper.

Spoiler
→ Reply