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
link for the contest: COCI
let's discuss the problems after the contest ends.
Good luck and have fun!
UPD: results are out!
Interesting problems.
How to solve VUDU ?
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<i. It reduces to s[i]-P*i>=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)
To make things easier, you can sort the prefix sum array and work with indices. No need to compress the BIT now.
Archazey My solution is the same as you the only difference is that I am using segment tree but my solution is giving MLE.
Can you post a link to your code?
here is it link
I optimized my code to link (I removed the array sum) but it still gives MLE.
I solve it with meet in the middle method. It came out very similar to merge sort.
Did you use any data structure?
No, only arrays
I think this is called divide and conquer, not meet in the middle
Yes, right
How to solve SAVEZ?
I solved it z-function + hash.. But I don't know correct this solution or not.
I did it with hash only, and a map to store the longest sequence at that hash.
Yeah it's exactly what I did, but I'm afraid that ML is too tight for double-hash.
Ooh, yes.. for nothing i wrote this z-function, it can be easily check with hash :(
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) :(
That's why we use
unordered_map
.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 :)
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.
Won't this give MLE?
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<i) equal to that prefix (so it respects the property).Those words can be hashed and put in maps. And also in M[word] you store maximum dp of words with that hash number,because you want to maximize your dp[i].
So briefly,dp[i]=max(1,max(M[word])),word being a prefix that is also suffix of word i
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.Won't this get MLE?
I stored transitions in
map<int, int> nx[1024];
When I wanted to find a transition, I did:
Memory limit was stupid though.
I used Trie without any space optimizations and did not get MLE. Weak test data?
No, it should work without any space optimizations even with 64MB ML. That is, if you are using
map<char, int> nx[2000000]
and notint 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.
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].
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?
I tried to use kd-tree, but it works too slow even on random tests. Maybe in C++ it would be faster.
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
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:
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? :)
You are right, my solution is wrong >.<
I got lucky to not receive any WA. Spent too much time making other tasks work (especially fitting D in ML), which strangely ended up being beneficial as I didn't think this solution through, else I wouldn't have coded it!
Oh, I see. "Successful hacking attempt at HellKitsune's solution", I guess ;)
Anyway, congrats on winning the contest!
Thanks! It feels like cheating a bit though >.<
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.
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.
Here we go: 14144018
Wow, changed from BFS to DSU and my code runs in 0.54s. Thank you very much.
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.
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.
Inclusion&Exclusion Principle + BitMask in problem B?
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.
Artur is geometry?
yes, it is. For any two segment, you check whether a segment has to be after the other segment and then sort them.
It is right? But relations is not transitive...
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).
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
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
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
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?
What do you think is the problem of my solution for SAVEZ?
It gets WA on 1C.
What is SIGABRT?
It is Mle (Memory limit exceed)