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?

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

nice

How to solve B from practice tour?

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.

CodeCould you explain the way you sorted here?

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

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

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

Thanks

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

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

How to solve Worm Worries?(day 1)

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

Thank you!

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

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.

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

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

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

I guess that is the intended solution.

YES

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

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

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.

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)?I agree, this is probably not the intended solution, but it gets 100 points.

I don't know if I get your idea correctly, but... isn't that still

O(N^{2}*M/ 64)?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.

I hope the intended solution will be more elegent

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.

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

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

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

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

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?

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.

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

I have simple solution using hash.

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

Very nice and elegant solution.

How to solve problem A from the second day?

Congrats for the first gold Gediminas!

How to solve C from day 2?

DP for every possible path ending at some node.

but bad site tho