# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Name |
---|
2017/2018?
Does anyone know the duration of the contest?
Edit: Thanks!
3 hours
why there is no editorial for this year's contests?
How to solve 4th and 5th problem ?
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.
Code
This complexity can be decreased a little bit if we are using hashing, even with sorting (not maps), it would be much faster.
sorry i had a mistake
Nice idea. Thanks. :)
D was also solvable with bitset in O(n * m * 26 + n ^ 2 * m / 32) which passed for all points
Could you please share your solution that uses bitset?
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.
Code
Thanks :)
I haven't submitted yet, but the fifth problem should be solvable with centroid decomposition.
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?
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.
Please do share your code if you manage to complete coding and testing your idea. It will be helpful.
Are we allowed to send submissions after the end of the contest?
No. Either wait until they publish the test cases and test locally or wait until https://oj.uz/ adds the new round.
Ok,thank you
Uploaded here: https://oj.uz/problems/source/372
Fourth task gives failed verdict.
Sorry, the uploader behaved wrong specifically in this task :( Now the issue is fixed.
Thanks! Can you please also add previous month's contest?
Problems except Slagalica are open: https://oj.uz/problems/source/371
Thank you.
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.
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?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).
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 clearI 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.
does anyone have the passed solution to E?
I used divide and conquer on the tree , and 2 dp
First dp is how much gas is needed , so that we can travel from root to vertex V
Second dp is how much gas stayed after travel from vertex V to root
Code Link