Блог пользователя Swistakk

Автор Swistakk, 10 лет назад, По-английски

Hi. BOI (Baltic Olympiad in Informatics) will be held on Thursday and Friday. I just learnt that organizers provide possibility of participation in an online mirror of that contest. Enjoy: https://sio2.mimuw.edu.pl/en/c/boi2015-online/dashboard/ !

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I would also be interested if they will provide live scoreboard of onsite event if you know.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why I can't submit practice problem ?!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"500 Internal Server Error" at the moment :(

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think we don't have full feedback ?!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can I find the results of online participants?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will it be possible to practice the problems after the contest ends?

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Can anyone share idea how to solve Tug of War? :)

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Make a graph of 2n vertices that represent positions on the left and right rope segment respectively. Connect two vertices (representing different rope segments) with an edge of weight w if there exists a contestant of strength w who likes both positions on the rope.

    It is easy to prove that if there exists a connected component which is a tree then solution does not exist. So let's check it at first.

    So we get a graph that has 2n vertices, 2n edges and none of it's connected components is a tree. So it is a forest of medusas (trees with an additional edge that forms one cycle, looking as a cycle with trees attached to it's vertices). For every vertex of degree 1 we know how we have to assign the corresponding contestant, so iteratively remove those until only cycles are left.

    Every cycle can be assigned to the left rope in only two ways, let's say one has cumulative strength A and the other B. We can at first use the strength A and leave the option to change the difference between cumulative strength of left and right rope segment by B - A for further use.

    We can treat these options (B - A values) as items in knapsack problem and check if the solution exists this way.

    It will not pass the time limit yet as the size of the knapsack is up to 20 * n and there are up to n items. However, we can see that the sum of the item values is also limited by 20 * n, so if there are a lot of items many of them will have the same value. Now we can group them in packages of size 2i (if we have 17 items of value 5 we split them into items of values [1, 2, 4, 8, 2]). It is easy to observe that the knapsack algorithm with these modified items produces exactly the same output as on the original ones, but is faster. That's the final algorithm and AFAIK it scores 100.

    Finally let's adress what did I mean by "if there are a lot of items many of them will have the same value". Let's assume that there are m different values in the knapsack. So the sum of the items is at least 1 + 2 + ... + m = O(m2). As the sum is limited by 20·n then . So the complexity of the algoritm is . I know that using 20 in this notation lacks the mind and dignity of a man, but I'm too lazy to correct it now.

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Ranking is now available !

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I've been interested in why no one has decided Task: SEQ ???