pllk's blog

By pllk, history, 7 months ago, In English,

The final round of the Finnish Olympiad in Informatics (Datatähti) will take place tomorrow, and after the official contest, there will be an international online contest.

The online contest will be available at CSES:

https://cses.fi/

The length of the contest will be 5 hours, and there will be 6-8 tasks of varying difficulty. The contest will follow the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

The online contest will be a virtual contest, which means that you can start the contest at any time between 18 Jan 2018, 20:00 and 21 Jan 2018, 15:00 (UTC).

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

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there an estimation of how difficult the problems will be?

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

The contest has now started!

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there going to be an international scoreboard like in last year's contest?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Results: https://cses.fi/162/scores/

    Congratulations to ainta for winning the contest with 629 points!

    The best score in the official contest was 517 (by Kuha and siiri).

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Lol rank 2 again like last year.

      What's the intended solution for P7?

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

        Here is one way to find a 100-point solution with a program. I have used three representations of the system in my code:

        • A graph: A node represents a square, and an edge represents a pair of squares that are known to be adjacent.

        • A collection of pieces: Each piece represents some known fragment of the map, but we do not know how they are rotated or mirrored with respect to each other.

        • A board: 50x50 grid that represents the map; some cells may be empty.

        A high-level idea is this:

        1. The input directly defines the graph.

        2. From the graph, we extract a large collection of small pieces.

        3. We keep merging pieces whenever there is only one way to combine them.

        4. Finally we have one very large piece of size 50x50 plus some small pieces. The large piece is used as the board.

        5. We then use backtracking search to find a way to fill the remaining cells of the board.

        Some more details about these steps:

        1. Constructing the graph: If a robot visits …, a, b, …, then we know that squares a and b are adjacent.

        2. Constructing small pieces: Find all 4-cycles in the graph; each of them forms a 2×2 piece. Also each edge forms a 1×2 piece. This is enough for now.

        3. Merging pieces: We say that pieces A and B are "adjacent" if they share some common squares. First merge recursively all pairs A–B of adjacent pieces that fit together in a unique manner (e.g. two 2×2 pieces that have 2 squares in common). Then consider triples A–B–C such that if we consider all rotations of A, B, and C, there is only one way to merge A–B–C without any conflicts. Then also consider 4-cycles A–B–C–D–A with a similar property and merge whenever the solution is unique. Keep in mind that all pieces have to fit inside a 50×50 board; when trying to merge large pieces this will help to eliminate some candidate solutions.

        4. At this point we will have one large piece, with dimensions 50×50 (so we know precisely how it is aligned with the board) and approx. 2000 known cells, and roughly 250 small pieces, most of which have dimensions 2×1.

        5. Filling remaining cells: Now we could be much more clever but it turns out that backtracking search implemented in Python solves what remains in approx. 10 seconds. A helpful heuristic is to try to fill the board starting from one corner and scanning towards another; then local conflicts are usually resolved quickly.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be an editorial?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    At the moment no, but you can see all the submissions in the scoreboard and ask further questions here if necessary.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Solution to E? I tried writing a binary search for the lower bound but it got way too complicated. These ACers are working some coding magic

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

    It can be done with a binary search. We try to binary search the highest upper bound of passengers x such that there are no solutions. If there is a solution, then you want to keep the number of passengers as close to the upper bound x as possible without exceeding it. You'll also need to ensure that after leaving a station the number of remaining passengers r is greater than or equal to the number of passengers currently in train, so you'll need to update the upper bound x to min(x, r).

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve F?

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

    Shameless self-promo

    It can be proved the two problems have the same result for a >= 2. a = 1 is just... trivial.

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

      So this problem is just the problem in the link with an additional constrain on a?

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

        And a player can create new heaps of coins, but this does not change the winning condition in the no-constraint game. However, without this condition, the constrained version may be very different.