ko_osaga's blog

By ko_osaga, history, 7 months 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  

»
7 months 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:

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

How to solve B from practice tour?

  • »
    »
    7 months 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
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain the way you sorted here?

  • »
    »
    7 months 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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    7 months 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.

»
7 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
7 months 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.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Worm Worries?(day 1)

  • »
    »
    7 months 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

    Mariusz1

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

      Thank you!

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

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

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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]?

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

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

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
7 months 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?

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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)?

      • »
        »
        »
        »
        7 months 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.

    • »
      »
      »
      7 months 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)?

      • »
        »
        »
        »
        7 months 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.

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

          I hope the intended solution will be more elegent

          • »
            »
            »
            »
            »
            »
            7 months 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.

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months 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 )

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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!

  • »
    »
    7 months 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

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

      Very nice and elegant solution.

»
7 months ago, # |
Rev. 5   Vote: I like it +4 Vote: I do not like it

How to solve problem A from the second day?

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Congrats for the first gold Gediminas!

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C from day 2?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

but bad site tho