Atreus's blog

By Atreus, history, 9 months ago, ,

Hello!

This blog is to let you know that tomorrow another round of Croatian contest, COCI will be held.

Feel free to discuss problems here after the contest ends.

Update: Result

• +34

 » 9 months ago, # |   +40 2017/2018?
 » 9 months ago, # | ← Rev. 2 →   +13 Does anyone know the duration of the contest?Edit: Thanks!
•  » » 9 months ago, # ^ |   +6 3 hours
 » 9 months ago, # |   +11 why there is no editorial for this year's contests?
 » 9 months ago, # |   +21 How to solve 4th and 5th problem ?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +9 Great tasks, it was interesting to do it.For the fourth task, I have one TLE, but generally it can be easily solved (on codeforces it was working enoguh fast).I stored bitmasks for all strings: 0 if character is '?' othewise 1. For example, string ab??c? would be 110010. Each string save in group with all other strings with that bitmask. Now iterate over all possible pairs of bitmasks (from 0 to 2m in double loop ), and find all 1 on same postions in both strings. That letters should be same, other letters are not important(at least one string contains '?' on other positions). So you have two arrays without ? and you need to count amount of same elements, one from first array one from second. It can be done with std::map. The complexity of this solution is O(2m * mn logn). Each group(mask) will be compared with 2m other masks, and everytime in one comparation we go over whole group + mlogn for using maps. CodeThis complexity can be decreased a little bit if we are using hashing, even with sorting (not maps), it would be much faster.
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 sorry i had a mistake
•  » » » 9 months ago, # ^ |   0 Nice idea. Thanks. :)
•  » » 9 months ago, # ^ |   0 D was also solvable with bitset in O(n * m * 26 + n ^ 2 * m / 32) which passed for all points
•  » » » 9 months ago, # ^ |   0 Could you please share your solution that uses bitset?
•  » » » » 9 months ago, # ^ |   +3 We have a bitset of size n (number of words) for each letter of the alphabet, set the i-th bit to 1 in the bitset corresponding to the letter ai. If the letter is '?' set i-th bit to 1 in all bitsets. We do this m times.Now we can just start with a bitset where all bits are set to 1 and the number of matching strings with the i-th string is bitwise and (&) of bitsets corresponding to the letters in the string. Note that if the letter aij = '?' we don't need use bitwise and since it won't change anything. One more thing is before we find the solution for i-th word we need to turn all bits on positions less than i to 0 so we don't count some pair twice. My explanation wasn't very good but I think the code is rather clear.
•  » » » » » 9 months ago, # ^ |   0 Thanks :)
•  » » 9 months ago, # ^ |   0 I haven't submitted yet, but the fifth problem should be solvable with centroid decomposition.
•  » » » 9 months ago, # ^ | ← Rev. 4 →   0 Was the idea anyhow similar to the one used in this problem. I mean something like merging positive length paths at every node in the centroid tree so that we don't care about the fuel being exhausted somewhere in the middle but only compute the sum of vertices in the path  -  sum of edges in the path and then take the positive paths found in this way and a concatenation of such path will be a valid path?
•  » » » » 9 months ago, # ^ |   0 Well my idea was to compute prefix/suffix minimum of sum_v — sum_e in order to make sure that the fuel level never drops below 0, but you're probably on the right track.
•  » » » » » 9 months ago, # ^ |   0 Please do share your code if you manage to complete coding and testing your idea. It will be helpful.
 » 9 months ago, # |   0 Are we allowed to send submissions after the end of the contest?
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 No. Either wait until they publish the test cases and test locally or wait until https://oj.uz/ adds the new round.
•  » » » 9 months ago, # ^ |   0 Ok,thank you
•  » » » » 9 months ago, # ^ |   +23 Uploaded here: https://oj.uz/problems/source/372
•  » » » » » 9 months ago, # ^ |   +1 Fourth task gives failed verdict.
•  » » » » » » 9 months ago, # ^ |   +17 Sorry, the uploader behaved wrong specifically in this task :( Now the issue is fixed.
•  » » » » » 9 months ago, # ^ |   0 Thanks! Can you please also add previous month's contest?
•  » » » » » » 9 months ago, # ^ |   0 Problems except Slagalica are open: https://oj.uz/problems/source/371
•  » » » » » » » 9 months ago, # ^ |   0 Thank you.
 » 9 months ago, # | ← Rev. 2 →   0 I am interested what is expected solution for the third task? Is it O(n3), or O(n2 logn) ?I have done it in second complexity with hashing and binary search. But it looks that both solutions are passing. If you planned O(n3) solution, then you shouldn't have put subtask n ≤ 200, otherwise you should put at least n ≤ 1000.
•  » » 9 months ago, # ^ |   0 I did it in O(n^3) with execution time less than one second. The second task is very useless. Btw, can you explain your solution?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +11 Sure, it is not very hard.Probably you did it on following way : Iterate over every pair of rows, check whether strings are angrams (have same number of occurrence of each letter) and then find with one extra loop longest common prefix/suffix. If n - prefix + sufix ≤ k we found one pair and finished job. Now this searching for longest common prefix/suffix can be done with hashing and binary search (try prefix [1... x] compare are hashes same and move left/right border as it needed, same I did for suffix).
•  » » » » 9 months ago, # ^ |   0 Ohhh got it! It makes a lot of sense. My solution is a little bit complicated because of that I didn't see the way to reduce it to n^2 log n. Thanks for the explanation, very clear
 » 9 months ago, # |   +8 I wrote a python script that can be used to locally test codes on the test cases being provided on the website. It runs the code on all input files one by one and then compares the output against the output file being provided in the test cases. I used diff command to compare files though it doesn't seem to work probably because of encoding or something, but I thought it may still be helpful for some people for later times maybe. You can find it here.
 » 9 months ago, # |   0 does anyone have the passed solution to E?
•  » » 9 months ago, # ^ | ← Rev. 4 →   +1 I used divide and conquer on the tree , and 2 dpFirst dp is how much gas is needed , so that we can travel from root to vertex VSecond dp is how much gas stayed after travel from vertex V to rootCode Link