Swistakk's blog

By Swistakk, 9 years ago, In English

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/ !

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

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

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

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

Why I can't submit practice problem ?!

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

"500 Internal Server Error" at the moment :(

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

I think we don't have full feedback ?!

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

Where can I find the results of online participants?

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

    There is only a photo for results after 2.5 hours on the Facebook page

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

      It's results of onsite participants. I asked for online ones.

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

        The results will be available around 5PM CEST.

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

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

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

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

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

Ranking is now available !

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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