ko_osaga's blog

Baltic Olympiad in Informatics 2018
By ko_osaga, history, 8 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?
»
8 years ago, hide # |
 
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
»
8 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

How to solve B from practice tour?

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← 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
  • »
    »
    8 years ago, hide # ^ |
     
    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
»
8 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

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

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

→ Reply
»
8 years ago, hide # |
 
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
»
8 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

How to solve Worm Worries?(day 1)

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Thank you!

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

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

      → Reply
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        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
»
8 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
8 years ago, hide # |
← 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
»
8 years ago, hide # |
 
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
  • »
    »
    8 years ago, hide # ^ |
     
    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
    • »
      »
      »
      8 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        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
    • »
      »
      »
      8 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        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
  • »
    »
    8 years ago, hide # ^ |
     
    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
»
8 years ago, hide # |
← Rev. 5  
Vote: I like it +4 Vote: I do not like it

How to solve problem A from the second day?

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

Congrats for the first gold Gediminas!

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

How to solve C from day 2?

→ Reply
»
4 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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