By DBradac, history, 3 years ago, ,

Join us this Saturday on the 5th round of this year's COCI!

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

• +60

 » 3 years ago, # |   +23 I loved solve hsin.hr problems. Quality of problem is high. Thank you.
 » 3 years ago, # |   0 How often do you have a contest there? One in a year or mouth?
•  » » 3 years ago, # ^ |   0 Usually 7 rounds in one season and a special, more difficult final round. So, roughly one contest a month.
 » 3 years ago, # |   -15 But it is clashes with my birthday :(
 » 3 years ago, # |   0 Just for remind
 » 3 years ago, # |   +5 Contest starts in 3 minutes. Good luck everyone.
 » 3 years ago, # |   +8 How to solve F? BTW, what was the purpose of this E?
 » 3 years ago, # | ← Rev. 2 →   +3 Seemed fairly easy, I only spent about 1.5 hours coding and I think I got all. My solutions: p4aij = a0, ij^xi^xj, where xi is xor'd every time city i is selected, aij is the final adjacency matrix, a0, ij the inital adj. matrix p5offline with map<> and a sum-BIT with range updates, p6reducible to: you have a tree with N vertices, block exactly K vertices so that each route from a leaf to the root contains exactly 1 blocked vertex and the root isn't blocked; solution: tree DP — straightforward in O(NK2), but for K < 64, O(NK) with bitsets is possibleUPD: Damnit, my last problem failed just on a triviality.
•  » » 3 years ago, # ^ |   +5 Or you could simply use long long instead of bitset(in the last problem).
•  » » » 3 years ago, # ^ |   +3 I always use long long *as* bitset.
•  » » » » 3 years ago, # ^ |   0 Can you tell more about your p4 and p5 solutions, please?
•  » » » » » 3 years ago, # ^ |   +3 Notice that for each edge, it would be redundant to switch both endpoints. This means we can simply go through the vertices one by one (denote this u) such that u is not marked, and if there is any other vertex v, such that there is no edge u-v, then we will switch all edges from u. We will then mark all vertices v such that there is no edge u-v (the same edges as mentioned above).
•  » » 3 years ago, # ^ |   +1 Can you explain how can you reduce it to a tree since the graph may have cycles?
•  » » » 3 years ago, # ^ |   0 The cycles are irrelevant. You can block what's on the cycles in any way you want.
•  » » 3 years ago, # ^ |   +7 Could you explain problem 5's solution using BIT in more detail? Tnx. :)
 » 3 years ago, # | ← Rev. 3 →   0 As the contest has ended, so how long should we wait for the system testing to finish? Edit: Ranklist can be seen now
 » 3 years ago, # |   0 How did Mo's algorithm TLE on E? I thought 5 seconds was enough for 500,000*700 = 350,000,000.
•  » » 3 years ago, # ^ |   +3 I used Mo's algorithm and got full points. Implementation details are often important in Mo's algorithm. My implementation is here: http://paste.dy.fi/TVD
•  » » » 3 years ago, # ^ |   0 Oh, I see why now. I used map instead of unordered_map. Silly me XD. Thanks for the code.
•  » » » » 3 years ago, # ^ |   0 Actually with unordered_map it still TLEs. http://pastebin.com/CyARk8ck[Code]
•  » » » » » 3 years ago, # ^ |   +8 Don't use unordered_map.
•  » » » » » » 3 years ago, # ^ |   0 Why not?
•  » » » » » » » 3 years ago, # ^ |   0 Because he is getting TLE?
•  » » » » » » » » 3 years ago, # ^ |   0 I mean why is it slower than a map?
•  » » » » » » » » » 3 years ago, # ^ |   0 I never told him to use map.
•  » » 3 years ago, # ^ |   +3 You are absolutely right. My solution (MO) had passed.
•  » » 3 years ago, # ^ |   -6 I thought log(N) ≠ 700.
•  » » » 3 years ago, # ^ |   0 Sqrt(N) = 700?)
•  » » 3 years ago, # ^ |   0 Yup, MO definitely worked for me, might be an error in the code or high constant.
•  » » 3 years ago, # ^ |   0 Same here. I thought my solution with Mo's algo would pass all testcases but gave TLE on last 4 test cases. Here is my solution
•  » » » 3 years ago, # ^ |   +1 You need O(1) acces to cnt[v[st]] , not O(log n) with map
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Did Coordinate compression so that the values fit inside array.Accepted code Thanks :)
•  » » 3 years ago, # ^ |   0 I got TLE with MO too :(
•  » » » 3 years ago, # ^ |   0 Perhaps, you got TLE with map/unordered_map, too? Could you show your code?
•  » » » » 3 years ago, # ^ |   0 Can you please see my code, I also used map with Mo's algo but got TLE in last 4 cases.
•  » » » » » 3 years ago, # ^ |   +1 Don't use map.
•  » » » » 3 years ago, # ^ |   0 Oh wow I'm so dumb.. I have solved the exact problem a few weeks ago and I just copied the code and modified 2 lines, but I didn't see that the limits for the numbers are bigger here so I didn't switch from array to unordered_map. Well I guess that's what I get for copying the solution.
•  » » 3 years ago, # ^ |   +6 Actually it's 500,000*700*log(N) when you update the index with map, use array instead of map then it becomes 500,000*700
 » 3 years ago, # | ← Rev. 3 →   0 Seems I got 105/120 on D with a seemingly wrong solution. My solutionI checked whether there exists an edge such that both of its nodes are in the same connected component. If so, return no.I couldn't find a counterexample during the contest, can maybe someone give me one? EDIT: Seems I only failed one test case, the solution might even be correct, I'd still like your opinion, since I can't prove it. EDIT 2: Seems the only test case I failed was 3 0.
•  » » 3 years ago, # ^ |   +6 I didn't understand your algorithm. Aren't the endpoints of an edge always in the same connected component?
•  » » » 3 years ago, # ^ | ← Rev. 4 →   0 He meant that all connected components in the graph are cliques. The solution is indeed correct(i got it accepted, probably he had bug in his code). The solution is easily provable to be correct.If we denote number of clicks(where a click toggles the edges and their complement) on a node as Anode then for some 3 nodes x, y, z if there is an edge already present Ax + Ay should be even, otherwise odd(similarly for Ax + Az and Ay + Az). It is easy to see this only satisfies when either Ax + Ay, Ax + Az, Ay + Az are all even or 1 of them is even while other two are odd. This corresponds to the clique condition. Code#include #include #include using namespace std; const int maxn = int(1e3)+5; int n, in[maxn]; bool G[maxn][maxn]; void dfs(int node, int comp) { in[node] = comp; for(int i = 0;i < n;i++) { if(!in[i] && G[node][i]) { dfs(i, comp); } } } int main(void) { int m, u, v; scanf("%d%d", &n, &m); for(int i = 0;i < n;i++) G[i][i] = 1; if(!m) { printf("NE\n"); return 0; } while(m--) { scanf("%d%d", &u, &v); u--; v--; G[u][v] = G[v][u] = 1; } int ctr = 1; for(int i = 0;i < n;i++) { if(!in[i]) { dfs(i, ctr++); } } for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(in[i] == in[j] && !G[i][j]) { printf("NE\n"); return 0; } } } printf("DA\n"); } EDIT: sorry for errors, i didnt pay attention while typing.
•  » » » » 3 years ago, # ^ |   +3 With his wording, it sounds like he didn't think cliques of size two were okay.
•  » » » » » 3 years ago, # ^ |   0 Or perhaps he missed the case where all Ax  +  Ay, Ax  +  Az, Ay  +  Az are odd. That is, there are no edges in graph originally. It is easy to miss it.
•  » » » » » 3 years ago, # ^ |   0 The case I missed was 3 0. Even i_dont_talk's missed 2 0, luckily that was in the sample tests. I submitted a minute before the end so I didn't have time to look for special cases.My code is practically the same as i_don't_talk's: Code#include #define MAXN 1010 using namespace std; bool mat[MAXN][MAXN]; int pos[MAXN]; int n; void dfs(int i, int comp) { pos[i] = comp; for(int j = 1; j <= n; j++) { if(mat[i][j] && pos[j] == 0) dfs(j, comp); } } int main() { int comp = 0, m; scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); mat[x][y] = 1; mat[y][x] = 1; } int poc1, poc2; for(int i = 1; i <= n; i++) { if(pos[i] == 0) { comp++; dfs(i,comp); } } for(int i = 1; i <= n; i++) { for(int j = 1; j < i; j++) { if(mat[i][j] == 0 && pos[i] == pos[j]) return printf("NE"), 0; } } printf("DA"); return 0; } 
•  » » » » 3 years ago, # ^ |   0 Yes! Thank you so much! Yes, I just realized what I described were cliques haha Yes, I see it now why it's correct. Thanks again :)
•  » » » 3 years ago, # ^ |   +5 Sorry, I should've explained better. I marked connected components based on the edges that existed in the beginning, but the edges I checked whether they had endpoints in the same connected component were the non-existing ones, the ones you were supposed to create. So for N = 3, M = 1, e ={ 1, 2 }, the edges I looked at were {1, 3} and {2, 3}. I noticed that if you flipped the node x, you'd also have to flip every node it's currently connected to, so you could get that edge back after destroying it, so basically, you'd have to flip the entire connected component. The problem arises when two nodes that aren't directly connected are in the same connected component, let's say nodes w and y. After flipping w, you'd create the edge {_w, y_}, but you'd have to flip y too, therefore destroying the edge. The only thing I'm not sure about, and only based on my gut feeling is that each node will be flipped at most once.
•  » » » » 3 years ago, # ^ |   +3 Flipping a node twice is the same as not flipping it, so yes, you were correct. It's a 2SAT problem.
•  » » » » » 3 years ago, # ^ |   0 Well, I may be wrong, but not really right? Say if you flipped a node, then flipped some other nodes, then flipped this very node again, you will obtain different graph.
•  » » » » » » 3 years ago, # ^ |   +8 This would result in the same graph as if you had never flipped the first node.
•  » » » » » » 3 years ago, # ^ |   +3 No, you won't obtain a different graph. It's the same as flipping the same other nodes and not touching this one.
•  » » » » » » » 3 years ago, # ^ |   +3 You are right. I'm sorry, I'm stupid
 » 3 years ago, # |   +2 In a frenzy, I accidentally submitted my STRELICE solution for POKLON, and got 0 points... after the contest, I submitted the old POKLON solution and it got full points :(
 » 3 years ago, # |   +9 For problem D.The only case that this can happen is either there exists only one complete graph (trivial case), or two complete graphs.Code
 » 3 years ago, # |   +18 P6 is clearly undefined if Hansel can't paint exactly K colors. (e.g S = 1) The game can't proceed, and there is no winner and loser. I made a clarification request about this after 1h of contest, but couldn't hear any response. I understand everyone can make a mistake, but please don't dismiss the clarification next time!
 » 3 years ago, # |   0 Just want to point out that p5 is almost exactly the same as 375D - Tree and Queries. So if anyone wants practice for something similar, this problem is perfect.
 » 3 years ago, # |   0 Did anyone else solved Problem E : Poklon with segment tree? i would like to compare my segment tree approach!
•  » » 3 years ago, # ^ |   0 Could you share your approach for a start? xD I solved it using MO's algorithm but I am interested how you did it using segment tree.
•  » » » 3 years ago, # ^ |   +6 My approach: problem: how many numbers in a segment that appears exactly 2 times! PREREQUISITE : loj - 1188; i wrote an editorial there. Solution : off-line solve, segment tree. okay lets jump into it with an example (given array): 8 1 1 1 2 3 5 1 2 first lets solve the problem if the query always starts from 0th index and ends at any index. how to approach that? using this array: 0 1 -1 0 0 0 0 1 (and make cumulative sum array of course!)query [0-7] ans = 1. correct.query [0-1] ans = 1. correct.okay let me explain how i made this array here. we marked the index where x has appeared 2nd time as 1, meaning: till this index, there is an answer.then, as we need numbers who are present EXACTLY 2 times, we marked the the index where x has appeared 3rd time as -1, which crosses out index where x appeared 2nd time, meaning: till this point there is no answer! i hope the making of the array is clear now!now the next part, what happens when the starting index of query is not 0th index? this is where off-line solve comes into play!we will use this array still:0 1 -1 0 0 0 0 1but how do we get the answer when the query is lets say [1,2] using current array if we try to find the answer then the answer will be 0, which is wrong! so how do we find it? think about it! if we make the 1st index 0, 2nd index 1 and 6th index -1 then we can answer any query starting from 1st index! :D and the array is :0 0 1 0 0 0 -1 1can you say why we specifically updated the 1st,2nd,6th index? because those are the places where 1 is present. and we changed the positions where 1 is present, why? because 1 is 0th index, which is the previous 1st index.so for example if the query is [2-7] the we would have to do the same for 0th index value, 1st index value. and the array will be like:0 0 0 0 0 0 1 1and the answer is 2!we simple used segment tree to update and find the query.CODEPS: sorry for my bad English and the way i wrote, i usually do not post in codeforces :S
•  » » » » 3 years ago, # ^ |   0 Tnx. I learned a lot from you! Have a nice day. ;)
•  » » 3 years ago, # ^ |   +1 I used a segment tree :-Code
 » 3 years ago, # |   0 But it is clash with global game jam :(
 » 3 years ago, # |   0 How do I solve p3? A trivial solution gains 50 points.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 You only have to find the area of the first quadrant and then multiply it by 4. - For each rectangle do x=x/2 and y=y/2. - For each X store the max Y coordinate for it. - Start from largest X and visit till x=1. If for current X the Y coordinate(if exist) is greater than the max_y_coordinate(till now), update the max_y_coordinate. Answer=Answer+max_y_coordinate.
•  » » » 3 years ago, # ^ |   0 Thanks!! I love you. I'll try it.