| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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:
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.
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
zdolna_kaczka
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.
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(N2 * 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.
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
For anyone who finds this on Google, the official solutions can be found in this repository: https://github.com/nordicolympiad/baltic-olympiad-2018