### kingofnumbers's blog

By kingofnumbers, 6 years ago,

Hello!

This is to remind you about second round of Croatian open competition in informatics will be held tomorrow Saturday 07.11.2015. 14:00 GMT/UTC

let's discuss the problems after the contest ends.

Good luck and have fun!

UPD: results are out!

• +68

 » 6 years ago, # |   0 Interesting problems.How to solve VUDU ?
•  » » 6 years ago, # ^ |   0 Translate average for a subsequence to difference_of_partial_sums/nr_of_elements.s[i]=sum of first i elements.(s[i]-s[j])/(i-j)>=P with j=s[j]-P*j. So the problem reduces to finding how many elements <= x there are,which can be done with BIT and compression(because numbers get very big)
•  » » » 6 years ago, # ^ |   +3 To make things easier, you can sort the prefix sum array and work with indices. No need to compress the BIT now.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Archazey My solution is the same as you the only difference is that I am using segment tree but my solution is giving MLE.
•  » » » » 6 years ago, # ^ |   0 Can you post a link to your code?
•  » » » » » 6 years ago, # ^ |   0 here is it link
•  » » » » » 6 years ago, # ^ |   0 I optimized my code to link (I removed the array sum) but it still gives MLE.
•  » » 6 years ago, # ^ |   0 I solve it with meet in the middle method. It came out very similar to merge sort.
•  » » » 6 years ago, # ^ |   0 Did you use any data structure?
•  » » » » 6 years ago, # ^ |   0 No, only arrays
•  » » » 6 years ago, # ^ |   0 I think this is called divide and conquer, not meet in the middle
•  » » » » 6 years ago, # ^ |   0 Yes, right
 » 6 years ago, # |   0 How to solve SAVEZ?
•  » » 6 years ago, # ^ |   0 I solved it z-function + hash.. But I don't know correct this solution or not.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +6 I did it with hash only, and a map to store the longest sequence at that hash.
•  » » » » 6 years ago, # ^ |   +3 Yeah it's exactly what I did, but I'm afraid that ML is too tight for double-hash.
•  » » » » 6 years ago, # ^ |   +4 Ooh, yes.. for nothing i wrote this z-function, it can be easily check with hash :(
•  » » » » » 6 years ago, # ^ |   -8 memory limit is too strict!it could be done with aho-corasick with 26*maxn memory, that it is a bit bigger than a memory limit(64MB) :(
•  » » » » » » 6 years ago, # ^ |   +3 That's why we use unordered_map.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -9 shit!I was too newbie for that :(!but I had guessed that I can use map, but I wondered it well be memory limit exceeded like previous ones!WHY?!how ever, thank you, teacher :)
•  » » 6 years ago, # ^ |   +3 I solved it using two Tries. One for the original strings, and one for the same strings but reversed. Not sure if my solution is right though.
•  » » » 6 years ago, # ^ |   0 Won't this give MLE?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +11 Dynamic programming.First observation. For a subset,the property stated has to be respected just for adjacent words,it's easy to prove. So for i1,i2,....,ik, word i2 has to end and begin with i1, i3 with i2.....dp[i]=maximum subset from the first i elements where the last one is word i. To calculate that,for every prefix of length x of word i which is also a suffix of word i ,you want those words j (j
•  » » 6 years ago, # ^ |   +19 Without hashes: Use trie. Let's put strings one by one in it, solving the problem for the given string at the same time. Once we added the string and calculated the answer for it, we will remember this answer in the node of the trie that corresponds to the end of this string.Processing a string: mark all positions i such that the first i characters are equal to the last i characters of the string. You can do it with z-function (or KMP if you prefer so). While moving through the trie, take a maximum of all previously remembered answers that lie on nodes which correspond to the marked positions. The answer for the current string is this maximum value plus one.
•  » » » 6 years ago, # ^ |   0 Won't this get MLE?
•  » » » » 6 years ago, # ^ |   0 I stored transitions in map nx[1024];When I wanted to find a transition, I did: int ind = ((s[i] - 'A') << 21) | pos; auto it = nx[ind & 1023].find(ind >> 10); Memory limit was stupid though.
•  » » » » » 6 years ago, # ^ |   0 I used Trie without any space optimizations and did not get MLE. Weak test data?
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 No, it should work without any space optimizations even with 64MB ML. That is, if you are using map nx[2000000] and not int nx[2000000][26].For some reason though, I got run-time errors on pretests with 2 million maps, even though on my machine the solution consumed around 35MB. So I wrote the above and it passed, thankfully.
•  » » 6 years ago, # ^ |   0 Z-function + trie. BUT if there was more memory, at least 75 MB, then it can be solved with ONLY trie (no hash, no zf). Hint: try to decompose all strings, s[0]s[1]s[2]...s[n] -> s[0]s[n]s[1]s[n-1]...s[n]s[0].
 » 6 years ago, # |   +23 Did anyone solve F (drzava)? I could only come up with a conceptual solution using Delaunay triangulation (to compute euclidean minimum spanning tree). That can't be the intended solution though, right?
•  » » 6 years ago, # ^ |   +5 I tried to use kd-tree, but it works too slow even on random tests. Maybe in C++ it would be faster.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 One observation is that we never need more than K closest neighbours of the city (is it even correct? I only had 30 minutes to solve this task, so I didn't have much time to prove things). What I did is I took K closest cities by X, K closest cities by Y, and then merged the two lists and took K closest cities overall.Then you can do binary search for the squared distance, finding the connected components using only edges found above, and trying to find solution for the problem for each connected component separately.This works in N * K * log(MAX_DIST^2). Could still be too slow for 1 second, not sure.Edit: looks like this solution is not fast enough, or my implementation is slow. 96 points
•  » » » 6 years ago, # ^ |   +15 Pardon me, but could you elaborate on the "K closest cities by X, K closest cities by Y" part?I do understand that no more than k cities are necessary (pigeonhole principle) — but how does taking the k closest cities by x/y help?Consider the following points, with k = 2: 0 0 0 100 0 101 100 0 101 0 1 1 2 2 When inspecting (0,0) the k "closest" (in your x/y kind of sense) ones are the ones with the other coordinate being  ≥ 100. Here (1/1) and (2/2) should be taken, right?I believe I'm missing something really obvious here. Still, would you mind to explain? :)
•  » » » » 6 years ago, # ^ |   +5 You are right, my solution is wrong >.
•  » » » » » 6 years ago, # ^ |   0 Oh, I see. "Successful hacking attempt at HellKitsune's solution", I guess ;)Anyway, congrats on winning the contest!
•  » » » » » » 6 years ago, # ^ |   0 Thanks! It feels like cheating a bit though >.<
•  » » 6 years ago, # ^ |   +18 Here's my solution, which receives full points after a small bug-fix:We binary search on D, so now we need to solve the problem of finding whether a given value of D works. This is in two parts: joining with union-find all points within distance D, and then applying knapsack to each component to test if some subset adds to 0 mod K.Part 1: Scan by x-value, maintaining a set sorted by y-value of all points with x-value at most D behind the leading line. Now for each point (a,b) in our scan, we iterate in the set through all points in this set with y-value in (b-D,b+D), and join to (a,b) all points within distance D. These are the points in the rectangle [a-d,a]x[b-D,b+D]. Note that by Pigeonhole, if we ever find a component of size at least K, we may stop and return a YES. This short-circuiting means (I think) that there can only be ~180 points in this box without more than K points lying in close proximity, and in most cases there should be much less.Part 2 modulo knapsack is quite easy, so of course this is where I made a bug.This solution is O(N*K*log(MAX_DIST)) but runs in less than 0.5 seconds on the test data.
•  » » » 6 years ago, # ^ |   0 Could you share your code on this problem please ? I've been trying to use your idea but cannot make it run faster than 2.6s.
•  » » » » 6 years ago, # ^ |   +3 Here we go: 14144018
•  » » » » » 6 years ago, # ^ |   +8 Wow, changed from BFS to DSU and my code runs in 0.54s. Thank you very much.
 » 6 years ago, # |   +20 What was the point of 64MB memory limit in SAVEZ? It made usage of data structures hard and the only option was to use hashing — which is more boring than "real" string algorithms.
•  » » 6 years ago, # ^ |   0 Don't be silly. Hashing is one of the most fundamental and most flexible techniques; that's why, it's as "real" as it gets.
 » 6 years ago, # |   0 Inclusion&Exclusion Principle + BitMask in problem B?
•  » » 6 years ago, # ^ |   0 You can just increment the bitmask, I think that will pass. I tried to optimize mine by adding the lowest bit and clearing the rest when there is a mismatch.
 » 6 years ago, # |   0 Artur is geometry?
•  » » 6 years ago, # ^ |   0 yes, it is. For any two segment, you check whether a segment has to be after the other segment and then sort them.
•  » » » 6 years ago, # ^ |   +5 It is right? But relations is not transitive...
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I solved it using topological sort on a graph where an edge i->j means that I have to remove i before j. The long thing is to create the graph but it can be done in O(N^2) comparing every pair of segments in O(1) [ here is the long thing, you have to consider some corner cases where the segments are vertical lines ]. Relation is transitive, i.e. if i < j and j < k --> i < k , that's why topological sort works (where a < b means that I have to remove a before b).
 » 6 years ago, # |   +8 for third problem , what is neatest way (and bug-free) to check which segment is above the other between two segments (or stating that no one is above the other) many people got WA on this problem, and I think most of them failed because of bug in that part of their codes
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I think it's not that neat, but let me share my solution:I first check if their projections on x axis intersect. If not, then they don't block each other. Then I think them as lines instead of line segments and find their equations. Then I choose the bigger one of left ends of segments as common x value that both have y values. I plug that common x into their equations. The line segment with the less value is the one which blocks the other, so we should remove it first. The only tricky situation is when a line segment doesn't have a slope. In that case, instead of using equation, we can use any value between y1 and y2 of that line segment.My code
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Maybe your algorithm is still correct. But some ARTUR test cases (e.g 10a) make the sticks touch each others at beginning. Therefore, the topological order determination make WA. I already send a clarification and hope for their correction of test data
•  » » » 6 years ago, # ^ |   0 It didn't get WA, but it's because of my luck. If they can touch, this solution is wrong. Didn't problem say they can't touch?
•  » » 6 years ago, # ^ |   +3 double solvey(int p, int x) { if (x1[p] == x2[p]) { return min(y1[p], y2[p]); } return 1.0 * (y2[p] - y1[p]) / (x2[p] - x1[p]) * (x - x1[p]) + y1[p]; } bool covers(int p, int q) { // requirement: x1[p] <= x2[p] and x2[p] <= x2[q] // x does not overlap if (min(x2[p], x2[q]) < max(x1[p], x1[q])) return false; int z = min(x2[p], x2[q]); double yp = solvey(p, z); double yq = solvey(q, z); return yp < yq; } 
 » 6 years ago, # | ← Rev. 2 →   0 What do you think is the problem of my solution for SAVEZ?It gets WA on 1C.
 » 6 years ago, # |   0 What is SIGABRT?
•  » » 6 years ago, # ^ |   +3 It is Mle (Memory limit exceed)