### giorgosgiapis's blog

By giorgosgiapis, 8 months ago, ,

Third round of COCI 2017/2018 season will take place this Saturday at 14:00 UTC.
You can find the full schedule for this season here and register for the contest here.

Let's discuss the problems here after the contest.

•
• +29
•

 » 8 months ago, # |   +10 Sorry if this question has been asked before, but I quickly Googled it just now and can't find it.Is there a way to change our COCI account password? Thanks.
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 Step 2: Look at the line "Forgot username and password..." and you will see a link directed to an other website. Step 3: Enter your email you used to register.I didn't try, but I hope these will help you.
•  » » » 8 months ago, # ^ |   0 I just tried this. This feature will generate a new (random) password for you and the new password will be emailed to you.I want to be able to change it to my own custom password.
•  » » » » 8 months ago, # ^ |   0 There is currently no feature that allows you to change your old password to a custom one, sorry.
•  » » » » 8 months ago, # ^ |   0 try to send clarification request
 » 8 months ago, # |   0 duration ?
•  » » 8 months ago, # ^ |   0 Three hours.
 » 8 months ago, # |   +1 Good luck to everyone!
 » 8 months ago, # |   0 Weird. I don't see tasks.
 » 8 months ago, # |   +22 Is there something with 0, (2^m)-1 and subsequence that xor of all elements == (2^m)-1 in E task?
 » 8 months ago, # |   +31 How to solve C, E, F?Is there smth faster than for C?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +7 E: An interval can't win iff it contains exactly 2k pair (x, 2n - 1 - x).
•  » » » 8 months ago, # ^ |   +19 Do you have any proof?
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   +16 Proof is easy. Let its xor sum be X. Then for each element a in that interval we must have a^(2n - 1)^X also is in that interval. So we have d pairs (a, a^(2n - 1)^X). Because its xor sum is X, so X must be 0.
•  » » » 8 months ago, # ^ |   0 How do you check if an interval meets the condition effectively?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Denote N = 2M - 1. You can answer the queries of the type "maximum/minimum index i such that N - perm[i] exists in the target interval" in O(1) with O(NlogN) or even O(N) precomputation with RMQ. Then, if the answer to any of the queries doesn't belong to the target interval, the interval is winnable (as explained in chemthan's post). Unfortunately, as the task is to count the winnable intervals rather than answer to queries, this method is only O(N2), which is enough only for 50% of the points.
•  » » » 8 months ago, # ^ |   0 How to solve it after this? It seems now it reduces to: count the number of subarrays with exactly 0 or 2 instances of every element.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 If my solution is correct, time complexity of my solution is O(R2 * S)Problem C
•  » » » 8 months ago, # ^ |   0 Yeah, that was the intended solution.
•  » » » 8 months ago, # ^ |   +3 So can you explain it?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +9 Sure, let's first think about the game in a different light. Suppose that everything on the grid stays still and the main character can in one second move from (r, c) to (r - 1, c - 1), (r - 1, c) or (r - 1, c + 1). It is easy to see those games are equivalent.Let dp[r][c][o] denote the longest valid expression you can acquire if you are currently on position (r, c) on the screen and the difference between the number of open parentheses and closed parentheses in the expression you have acquired thus far equals o. Computing all dp values takes O(R3) time. This solves the part of the problem that deals with the length of the sequence.For the reconstruction, we'll keep around a set of dp states that can potentially lead us to the lexicographically smallest solution. At the beginning, that set contains only Mirko's initial position. We will now make transitions from those states (similar to transitions in dp) that lead to longest solutions and traverse only the empty cells of the grid (this is a standard bfs). Once we have exhausted the empty cells, we have obtained the set of cells that contain the next parenthesis in our sequence. At this point we will disregard all cells that have ')' written on them in case there exists a single cell with '(' written on it. Repeating this process yields the lexicographically smallest sequence in O(R2).
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   +3 Since there is no test case with expression longer than 50, separate reconstruction part is actually not needed. We can define dp value as pair of (longest valid expression, lexicographic price of expression) and then just maximize this pair using dp.If for some state longest valid expression is k then lexicographic price is k-bit number created from this expression with ( being 1 and ) being 0 — this k-bit number is solution itself.EDIT: Actually I modified this approach a bit and it works for all possible cases i.e. with expressions up to 100, just replace k-bit number with solution string, add custom operator< and then just print that string at the end.
•  » » » » » » 8 months ago, # ^ |   0 What makes you think there is no test case with expression longer than 50?
•  » » » » » » » 8 months ago, # ^ |   0 Well, I meant in this specific contest there was not :). Of course there could be a test case with expression longer than 50.
•  » » » » » » » » 8 months ago, # ^ |   0 You made me a bit paranoid for a second because I generated the test data :)Now I see that we uploaded the wrong .zip archive at hsin.hr/coci which contains the test data for our local version of the contest (honi). That version of the task had looser constraints and the solution you described was supposed to get accepted.The correct archive should be up tomorrow.
•  » » » » » » » » » 8 months ago, # ^ |   0 As noted in the edit of my comment above, this approach is working for all possible test cases if the lexicographic price part is replaced by plain string, bitset could be used as well. Thus special reconstruction phase could be avoidable after all. Waiting for additional test cases.
 » 8 months ago, # | ← Rev. 2 →   +25 Wasn't C was harder than other C's in COCI?
•  » » 8 months ago, # ^ |   +4 Yes, considerably.
 » 8 months ago, # |   0 D is pretty easy right? Unless I missed something that made it hard...
•  » » 8 months ago, # ^ |   +5 Yeah.. Did you wrote simple BFS like me?
•  » » » 8 months ago, # ^ |   +1 Same here. Honestly, C and D should be swapped.
•  » » » » 8 months ago, # ^ |   0 Im not sure simple bfs was the optimal way. My code was not that simple
•  » » » 8 months ago, # ^ | ← Rev. 2 →   -8 oh my god! I didn't read the D ,because i wanted to write c with recursion. #facepalm
•  » » » » 8 months ago, # ^ |   -8 really ,it is a simple bfs.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Yup. Well two BFS, but still very simple. I actually have a stupid typo in my last submission so it won't pass but it definitely seems too easy.
•  » » » » 8 months ago, # ^ |   +5 I don't know, but it reminded me this problem: http://codeforces.com/contest/877/problem/D
 » 8 months ago, # |   0 Do you know when can i see the results?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +8 Usually, after 40 min. we can see results, but there can be delay sometimes.Results delayed :(
•  » » 8 months ago, # ^ |   0 in messages i saw this " Results will be available tomorrow. Thank you for patience. "
 » 8 months ago, # |   0 What is the optimal solution in problem B?
•  » » 8 months ago, # ^ |   +6 Precalculate prefix sums for each letter. When answering queries, check if count of each letter in same on intervals. Codeintt pref[26][5 * max4]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); IO; string s; intt q; cin >> s; for (intt i = 0; i < s.size(); i++) { pref[s[i] - 'a'][i]++; for (intt j = 0; j < 26; j++) { pref[j][i] += pref[j][i - 1]; } } cin >> q; while (q --) { intt a, b, c, d; cin >> a >> b >> c >> d; a--, b--, c--, d--; if (b - a != d - c) { cout << "NE" << endl; continue; } intt ok = 1; for (intt i = 0; i < 26; i++) { if (pref[i][b] - pref[i][a - 1] != pref[i][d] - pref[i][c - 1]) { ok = 0; break; } } cout << (ok == 1 ? "DA" : "NE") << endl; } return 0; } 
 » 8 months ago, # |   0 What is the solution for C? I wrote a solution that works in O(3^R), but it is obviously too slow.
 » 8 months ago, # |   +5 Will they open the analysis mode?
 » 8 months ago, # |   0 Turn on analysis mode please.
•  » » 8 months ago, # ^ |   +14 The analysis mode is open now.