pllk's blog

By pllk, history, 6 years 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

| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

The contest has now started!

»
6 years 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?

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

Will there be an editorial?

  • »
    »
    6 years 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.

»
6 years 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

  • »
    »
    6 years 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).

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

How to solve F?

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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?

      • »
        »
        »
        »
        6 years 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.