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

Автор ko_osaga, история, 6 лет назад, По-английски

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?

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

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

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

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

How to solve B from practice tour?

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

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

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

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

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

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

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

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

How to solve Worm Worries?(day 1)

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

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Thank you!

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

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

        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.

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

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

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

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

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

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

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

      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)?

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

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

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

        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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    I have simple solution using hash.

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

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится

How to solve problem A from the second day?

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

Congrats for the first gold Gediminas!

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

How to solve C from day 2?

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

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

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

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