ko_osaga's blog

Baltic Olympiad in Informatics 2018
By ko_osaga, history, 7 years ago, In English

Hello!

According to the official site, BOI 2018 will be held in this weekend. Good luck to all participants!

I wonder if the organizers are planning any online contests. I actually found this Kattis site, but I think this is for official participants. Any ideas?

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

Comments Comments (41)
| Write comment?
»
7 years ago, # |
  Vote: I like it +76 Vote: I do not like it

There will be online contests. I got the following links from the organizers:

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

How to solve B from practice tour?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    It is quite hard to explain the solution (at least for me) but here is my code and if you have any questions, just ask me.

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

    We're still in the process of writing up solution spoilers, but here's some work in progress in case it's useful (also for problem A): https://www.overleaf.com/read/rmkvkpmsfwvc

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

How to get full score for A problem from practice tour?

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

    A simple solution is to do the calculation with Python's arbitrary-precision decimal numbers (decimal). Just print the answer with sufficient precision.

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

Live scoreboard of the official contest: https://boi2018.progolymp.se/livescore/

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

How to solve the second subtask of problem Worm Worries? I couldn't do it in less than 42 queries.

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

How to solve Worm Worries?(day 1)

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    As far as I know:

    1 dim: golden ratio division

    2 dim: splitting similar to KD-trees

    3 dim: pick Q/2 points and crawl greedily from the best one

    zdolna_kaczka

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

      Thank you!

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

      Can you explain more about the 'golden ratio division'?

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

        This problem seems a little annoying to me, as you are just constant factor optimizing away from your standard binary search solution.

        My guess is the following: if your current interval is [a,b], Then query x, x-1, x+1 in that sequence in order.

        If f(x) <= f(x-1) then restrict to [a,x] and you've only used two queries (don't ask about x+1). Otherwise, query x+1, and if f(x) <= f(x+1) then restrict to [x,b], having used three queries.

        This asymmetry will cause you to choose a value of x which is not (a+b)/2 but closer to one side.

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

          If f(x) > f(x-1), why we can't just restrict to [x, b]?

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

            looks like I have no idea what I'm talking about!

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

Can B(martian DNA) be solved with two pointers for 100 pts?

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

    I guess that is the intended solution.

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

How to solve problems A and B from the second day?

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

I completely give up on Day 2 B... Can anyone tell me the solution?

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

    We can split each string into long long type bitmasks for each letter a, c, g and t, where we will have a 1 in some position if the according letter is present. Then the number of differences between two strings will be the sum of differences between all the masks a, c, g, t divided by 2.

    Link to my code: https://pastebin.com/K6dxZfAP.

    I also used a little optimization to reduce the amount of strings that are checked.

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

      Is this really the intended solution? Because I used bitset (which I think that works as fast as your approach) and it didn't work for n = 4100. The only optimization is that you checked the sum of differences. Are you sure that there isn't counterexample for your code (so it would get TLE)?

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

        I agree, this is probably not the intended solution, but it gets 100 points.

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

      I don't know if I get your idea correctly, but... isn't that still O(N2 * M / 64)?

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

        Yes. However, since the complexity is ~ 10^9 we can reduce it by using optimizations like shuffling the strings in random order, using pragmas, checking sum of differences, not checking strings who differed by more or less than k with some other string.

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

          I hope the intended solution will be more elegent

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

            The main intended solution was to generalize the "check sum of differences" thing to not check against the sum of everything, but against multiple random subsets. Or simpler, against a randomly weighted sum of differences.

            Example solution: https://gist.github.com/simonlindholm/9d53bf4f0043dc8a50bef91f3593de53

            And the official solution write-ups (which we kind of threw together in a hurry...): https://www.overleaf.com/read/yjywvxrqmsxd Also includes the solution for A.

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

              Is it possible that you post all codes and all editorials?

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

                Yes, they should be added to the website some time tomorrow.

                (In the meantime, editorial for day 1: https://www.overleaf.com/read/vkygrnxjffzf )

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

                Editorials are now linked from the website: http://boi2018.progolymp.se/tasks/

                Solutions and test data are available on GitHub: https://github.com/nordicolympiad/baltic-olympiad-2018

                Also, newsletter with my and jsannemo's somewhat cryptic crossword: http://boi2018.progolymp.se/day4.pdf

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

                  Sorry for necroposting, but I have a question regarding your proof for alternating current: in the proof for odd K, the case when s is covered by the possible intersection of w(i) and w(i-1) is not considered. In that case, it may be possible that no other segment covers s, and there is still some other solution that uses different types for w(i) and w(i-1), isn't that right (the argument is fine for the other case, as having at least one solution also implies that every s is covered by at least 2 cables, which are either both part of S, or one inside S and the other outside it, both cases having 2 cables of different types containing s which is fine)? What then?

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

                  No worries. It's perhaps a bit unclear in the proof, but we are assuming that a correct wiring exists, then taking that wiring's position i for which i and i-1 have the same direction. Thus the case you're referring to cannot occur.

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

                  Ahh got it thanks! It then also make sense because i is not of your choice necessary. Thanks for making it clear!

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

    I have simple solution using hash.

    You can look at my code for more details: https://pastebin.com/4Nf1pY3s

    → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +4 Vote: I do not like it

How to solve problem A from the second day?

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

Congrats for the first gold Gediminas!

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

How to solve C from day 2?

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

    DP for every possible path ending at some node.

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

BOI 2018 Day 2 Genetics can be solved without using bitsets.

First, we ensure random ordering of the strings by shuffling them arbitrarily. Then, we can partition the strings into $$$\sqrt{N}$$$ many 'compartments.' For each compartment, maintain the number of occurences of each letter at index $$$i$$$. In my implementation, this is stored as oc[blocks.size()][M][4]. Then, for each string, to check if it is valid, iterate over each string and check if the number of differences in each of the $$$\sqrt{N}$$$ many compartment is equal to (blocks[index].second - blocks[index].first + 1 - (index == id[i])) * K. If it is not, then obviously that string cannot be villain. Then, we've narrowed down the subset of possible strings to the point that we can just check each one brute-force.

implementation

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

For anyone who finds this on Google, the official solutions can be found in this repository: https://github.com/nordicolympiad/baltic-olympiad-2018

→ Reply