giorgosgiapis's blog

COCI 2017/2018 — Round 1
By giorgosgiapis, 7 years ago, In English

First round of this year's COCI will take place today at 14:00 UTC.
You can find the full schedule for this season here and register for the contest here.

Let's discuss the problems here after the contest.

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

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

Remainder: Contest starts in less than 15 minutes.

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

How to solve D (Hokej)?

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

    I guess the sufficient condition is that:

    t[i] is the time of i-th player plays.

    1.0 ≤ t[i] ≤ M.

    2.sum(t[i]) = 6 * M.

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

    I think the following greedy works, but I don't have proof: let's sort the players by quality. Then make a 6 × n table (so it has 6 rows and n columns) and from left to right fill it greedily with players not exhausting their endurance. From this matrix calculate the needed things.

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

How long until final results?

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

How to solve C for 100pts? I thought about trie or hashing but couldn't implement it.

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

    Insert all passwords into a trie and then use bruteforce to check every substring of every password.

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

    For storing strings use unordered_map which is basically hashing

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

    Simple std::map passes too. I stored count of strings in a map, checked every substring of every string, and multiplied by the counts. It results in O(NM2log(N)) complexity, where M is the length of the strings, so about 3 * 107 operations. My solution passed with 0.49 s on worst case.

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

Why doesn't Nlog^2 N solution pass in E? (binary search + segtree) Also, what's the intended solution?

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

    I coded such a solution and got full points (slowest time 0.46s). Code

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

    Seems is intended. Sort the events and queries offline by values of x (number of stops) and process the remaining dimension (children's age) with a segment tree.

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

      I did O(nlogn) with online queries.

      I use a segment tree, where the base nodes are the children, and the values are the currently assigned drop off (INF by default). The upper nodes are min of their children. Updates are simple segtree updates.

      When querying I move right, or right-up (i. e. from v either to v + 1 or to v / 2. When I can't move neither way, or I reach a node with at most Y value, I stop. If the stop node's value is bigger than Y, then the answer is -1. Otherwise, I move left, leftdown or rightdown, (i. e. from v either to v - 1, v * 2 or v * 2 + 1) in this preferency order, such the node I move to, got value at most Y. When we reach a base node, it will be the optimal answer.

      Here is my code.

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

Does anyone know what "Illegal substitute!" mean in D, because I can't find the error in my code.

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

    It probably means you bring down and up the same person at one moment, which is illegal. So instead of a -  > b you do c -  > a, a -  > b.

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

    Do you remember the rule "but a player cannot enter the game, and then exit in the same moment, or vice versa"?

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

      I don't think that this is the problem, I checked it with this checker (I hope it's correct :D): checker Also it shouldn't happen with my solution.

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

        The test cases are open to download, so if you have time, and luck, you can check manually for something illegal. Or just send source code.

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

        Oops the checker was buggy, my bad. It's really the problem :D Sorry.

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

        Maybe there are bugs on lines 25 and 26.

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

Can anyone explain F solution?

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

    I wasn’t able to participate, so this might get wrong

    As the rectangles form a tree structure, our task is simplified to

    • Building trees
    • Querying for a node that contains given points

    If we do these fast, other stuffs are fairly easy.

    We can use sweep line to do that. In a BST (std::set) we store rectangle as an interval, sorted in order of lower y coordinate. To build a tree, we just need to find a parent. This can be done by lower_bound operation in insertion phase (lower y coordinate slightly less than current interval). Query can be done in simillar way. So this is solvable in O((n+m)lgn)

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

    You build a tree of the rectangles (they are the vertices). By this I mean that the parent of rectangle X is the smallest rectangle Y, which contains X inside of it. This can be done with sweep line on the X-axis using a segment tree for the Y-axis in time.

    Now for every paintball ball we find the smallest rectangle containing it. After that we add that we have colored this rectangle with color of the given ball (we simply add it to a vector for this rectangle or something like that). This again can be done in with sweep line in time.

    Well now we have a tree and some vertices already have colors for them. Well if we have colored vertex X in some color, all of its ancestors also are colored with the same color. From this we see that a rectangle (vertex) is colored with all colors in it's sub tree. This is a well known problem which can be solved in with a segment tree and DFS order or with "dsu on tree" (I used this).

    So the whole solution has running time of . Here is my AC code from the competition.

    PS: In my code both sweep lines are merged into one.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I thought of the same thing, but I don't think you need to explicitly build a graph. You could create an array of sets std::set<int> S[MAXN] containing the colours in rectangle S[i], and iterate the rectangles in increasing order of size, merging the current rectangle's set with its parent's at every step.

      → Reply