pllk's blog

BOI 2016: online contest
By pllk, history, 9 years ago, In English

Baltic Olympiad in Informatics 2016 will take place in Helsinki, Finland, May 11–15.

https://www.cs.helsinki.fi/group/boi2016/

Besides the official contest, there will be an online contest that will be open for everybody.

The format is like IOI: two contest days, five hours time to solve three tasks, full feedback.

On both contest days, the online contest runs simultaneously with the official contest, i.e., the contest times are:

Link to the contest system is here:

http://cses.fi/

You can already register an account to the system. The link to each contest will be activated 15 minutes before the contest.

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

Comments Comments (42)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome! Are there any prizes or certificates for the online mirror?

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

    No prizes, it's for fun and practice

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

Why is it soooo early in the morning :(

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

Where to register?

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

Any chance the system allows offline participation (practice) after the competition is over? I have school both days and some tests I can't skip but I was really hoping to practice on BOI tasks.

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

The first contest will start in 15 minutes!

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

WoW! Outstanding performance of Polish team, especially a.piasta and zdolna_kaczka.

Are online mirror results published somewhere?

And the last one, how to solve that shitty spiral? :P

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

    My solution goes something like this. Let's observe the lines y = x and y = -x. Notice that those lines correspond to the "turning points" of the spiral. Every query can be split into O(1) rectangles such that every rectangle is a square whose diagonal is a part of the line y = x or y = -x, or a rectangle which is not crossed by those lines. Now, the sum in each of those rectangles(and special squares) can be expressed as a polynomial of degree 4.

    It is easy to implement a function that calculates the value of a certain position in O(1). Using this, we can calculate several positions in a rectangle and using interpolation calculate the entire sum.

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

    Still better task than Bowling

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

Can you please enable practice soon? I finished problem spiral 3 minutes after the end of the competition and I want to know if I was that close to getting 300.

PS: I saw that we can view the tests, so I run them on my PC and it seems it worked.

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

    Now it's possible to upsolve the tasks in the system.

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

Day 1 results of official contest

Day 1 results of mirror contest

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

The second contest will start in 15 minutes!

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

How to solve Cities for k={4,5} ?

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

Stuck solving subtask 1 of problem Cities (52+27+100) 479 in total

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

How to solve A? I solved A in O(2knlogn) which should be just fine, but somehow I have to use fast IO and switch from Dijkstra using set to using priority queue to get AC (1.98s/2s) :(

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

    Can you tell your solution? In my solution, I'm trying all possible cases for all k values. It's O(N * log(N)) but code is so disgusting and doesn't work for k > 5

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

      It's something like dp(x, i) is the minimum cost of a tree rooted at i connect the important city in bitmask x. State transition should be simple. Just note that to update from dp(x, i) to dp(x, j), use a priority queue like in Dijkstra algorithm.

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

    Well i have O((2 ^ k)nlogn + n * (3 ^ k)) and i got TLE on the last subtask, how did you remove the n * (3 ^ k)?

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

      What is that n3k in your solution ? Maybe I have calculate my complexity wrong.

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

        well i updated dp[mask][v] by dp[sub][v] and dp[mask ^ sub][u] that's why it was 3 ^ k — but now i know how to remove it thanks :D

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

    my solution is O(K^2MlgM + K!N) and I'm surprised how diverse the complexity is :p

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

Ok, the contest is over and I, as any other conscientious student, tried to solve the problems after the contest. Of course, I don't think that I'll be able to find the solution to the second problem by myself, but at least I've tried the 3rd problem. Guess what? No result. Can someone who got 100 points on it, explain it to me? I've got 68 points in contest with some sort of dynamic programming with memoization which can be showed to be called at most Nlog times. It keeps something like the best string that can be obtained applying moves on the nodes in the subtree supposing that the root has a specific value. I managed to keep the string in a smart way which works due to the particularity of the reccurence. My final solution has Nlog^2 time complexity. And as far as I was able to see in the other codes, they all use almost the same recursive method.

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

    well i didn't save the string i saved the best state to which we can go in every state and i have some function show which is for generating the string — first it calculates the dp and after that it will go to the best state that dp has
    http://cses.fi/57/result/26804

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

      I think I understood your code but I still have a big question: why does it work? As far as I can see, you store in dp[v][x] the position where the root, considered to have value x will end in the minimal lexicographic solution of v's subtree. Ok, the problem is: why can you compare two solutions, distinguishing which one is better based only on the final position of the root's value? The states of the dp are exactly the same as mine, but I don't know how to prove this assumption (that states that just the final position matters). Can you, please, post a more detailed solution, or, at least, some steps of the proof?

      Thanks in advance!

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

        Well i didn't have a prove in the contest but i can kinda say why it works
        well there's a fact that the minimum of the root and childs remain in the root and the others will be at the root of one of the childs now imagine we have 2 ways of giving the max element and min element (lets call them mx and mn) to the childs. let's see the first distribution min will end up in lmnpos and max will end up in lmxpos
        well let's call the other way rmnpos and rmxpos
        well from the minimum of the four elements i declared above to the root all the elements will be the same in both distributions now i just have to say that the minimum of the four elements is the minimum element for sure :D — lmxpos > rmnpos (since the minimum element get's a better position for sure !!) and rmxpos > lmnpos
        so the one who's minimum is the leftmost is surely the best state

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

Does anybody know the optimal solution to Maze (B)? I got 65 points doing something like this (putting the coins into places with three walls around them): 

ox#....o#
.#..#..#o
...#..#..
..#..#...
o#..#..#.
#..#..#..
..#..#..#
....#o..o

...so I suspect that the solution is based on using diagonal lines like these, but better.

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

    I generated the "most challenging mazes found by the jury" using a dynamic programming solution http://paste.dy.fi/c9e that should give optimal results. In this solution, we construct a tree with at most k + 1 leaves in the grid by filling the grid row by row, maintaining the cells of the boundary and information about which boundary cells are connected to each other. The optimal mazes look somewhat irregular: http://paste.dy.fi/uJN/plain . The code ran for a long time and took a lot of memory, and therefore using a solution like that during the contest time would still require a lot of optimization (for example, pruning some cases out of the dynamic programming).

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

Slightly unrelated, but is there any judge where we can find past BOI tasks to practice on?

I couldn't find any via Google :/

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

Is it possible for the official contestants to view their solutions now? I would love to view my codes from BOI.

→ Reply