### ko_osaga's blog

By ko_osaga, history, 18 months ago, ,

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

 » 18 months ago, # |   +76 There will be online contests. I got the following links from the organizers: Practice session: https://boi18-practice-open.kattis.com Day 1: https://boi18-day1-open.kattis.com Day 2: https://boi18-day2-open.kattis.com
•  » » 15 months ago, # ^ |   -18 nice
 » 18 months ago, # |   +6 How to solve B from practice tour?
•  » » 18 months ago, # ^ | ← 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#include using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1LL << 55) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 100111 typedef long long ll; typedef long double ld; typedef pair pii; vector adj[maxn]; ll t[maxn], dp[maxn], cur[maxn]; int sz[maxn]; ll ans = 0; bool comp(pair a, pair b){ return a.fi * b.se < b.fi * a.se; } void DFS(int x){ sz[x] = 1; dp[x] = t[x]; vector > here; here.pb(mp(1, 0)); for(int v : adj[x]){ DFS(v); sz[x] += sz[v]; here.pb(mp(dp[v], sz[v])); } for(int i = 0; i < here.size(); i++) dp[x] += here[i].fi; ans += dp[x]; if(here.size() == 1) return; sort(here.begin() + 1, here.end(), comp); ll cost = 0; cur[here.size() - 1] = 0; for(int i = here.size() - 2; i >= 0; i--) cur[i] = cur[i + 1] + here[i + 1].se; for(int i = 0; i < here.size(); i++) cost += cur[i] * here[i].fi; ans += cost; } int main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%lld", t + i); int m; scanf("%d", &m); while(m--){ int x; scanf("%d", &x); adj[i].pb(x); } } DFS(1); printf("%lld\n", ans); return 0; } 
•  » » » 11 months ago, # ^ |   0 Could you explain the way you sorted here?
•  » » 18 months ago, # ^ |   +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
 » 18 months ago, # |   +8 How to get full score for A problem from practice tour?
•  » » 18 months ago, # ^ |   +8 A simple solution is to do the calculation with Python's arbitrary-precision decimal numbers (decimal). Just print the answer with sufficient precision.
•  » » » 18 months ago, # ^ |   +8 Thanks
 » 18 months ago, # |   +29 Live scoreboard of the official contest: https://boi2018.progolymp.se/livescore/
 » 18 months ago, # |   0 How to solve the second subtask of problem Worm Worries? I couldn't do it in less than 42 queries.
 » 18 months ago, # |   +8 How to solve Worm Worries?(day 1)
•  » » 18 months ago, # ^ | ← Rev. 2 →   +28 As far as I know: 1 dim: golden ratio division2 dim: splitting similar to KD-trees3 dim: pick Q/2 points and crawl greedily from the best oneMariusz1
•  » » » 18 months ago, # ^ |   +3 Thank you!
•  » » » 18 months ago, # ^ |   +3 Can you explain more about the 'golden ratio division'?
•  » » » » 18 months ago, # ^ |   +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.
•  » » » » » 18 months ago, # ^ |   +8 If f(x) > f(x-1), why we can't just restrict to [x, b]?
•  » » » » » » 18 months ago, # ^ |   +7 looks like I have no idea what I'm talking about!
 » 18 months ago, # |   +10 Can B(martian DNA) be solved with two pointers for 100 pts?
•  » » 18 months ago, # ^ |   0 I guess that is the intended solution.
•  » » 18 months ago, # ^ |   0 YES
 » 18 months ago, # | ← Rev. 2 →   +8 How to solve problems A and B from the second day?
 » 18 months ago, # |   +4 I completely give up on Day 2 B... Can anyone tell me the solution?
•  » » 18 months ago, # ^ |   +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.
•  » » » 18 months ago, # ^ |   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)?
•  » » » » 18 months ago, # ^ |   +10 I agree, this is probably not the intended solution, but it gets 100 points.
•  » » » 18 months ago, # ^ |   +5 I don't know if I get your idea correctly, but... isn't that still O(N2 * M / 64)?
•  » » » » 18 months ago, # ^ |   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.
•  » » » » » 18 months ago, # ^ |   +6 I hope the intended solution will be more elegent
•  » » » » » » 18 months ago, # ^ |   +26 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.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.
•  » » » » » » » 18 months ago, # ^ |   0 Is it possible that you post all codes and all editorials?
•  » » » » » » » » 18 months ago, # ^ |   +10 Yes, they should be added to the website some time tomorrow.(In the meantime, editorial for day 1: https://www.overleaf.com/read/vkygrnxjffzf )
•  » » » » » » » » 18 months ago, # ^ |   +18 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-2018Also, newsletter with my and jsannemo's somewhat cryptic crossword: http://boi2018.progolymp.se/day4.pdf
•  » » » » » » » » » 15 months ago, # ^ |   0 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?
•  » » » » » » » » » 15 months ago, # ^ |   +20 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.
•  » » » » » » » » » 15 months ago, # ^ |   0 Ahh got it thanks! It then also make sense because i is not of your choice necessary. Thanks for making it clear!
•  » » 18 months ago, # ^ |   +38 I have simple solution using hash.You can look at my code for more details: https://pastebin.com/4Nf1pY3s
•  » » » 18 months ago, # ^ |   +3 Very nice and elegant solution.
 » 18 months ago, # | ← Rev. 5 →   +4 How to solve problem A from the second day?
 » 18 months ago, # |   +18 Congrats for the first gold Gediminas!
 » 18 months ago, # |   +3 How to solve C from day 2?
•  » » 18 months ago, # ^ |   0 DP for every possible path ending at some node.
 » 15 months ago, # |   -8 but bad site tho