Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By DBradac, history, 23 months 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
•

 » 23 months ago, # |   +23 I loved solve hsin.hr problems. Quality of problem is high. Thank you.
 » 23 months ago, # |   0 How often do you have a contest there? One in a year or mouth?
•  » » 23 months ago, # ^ |   0 Usually 7 rounds in one season and a special, more difficult final round. So, roughly one contest a month.
 » 23 months ago, # |   -15 But it is clashes with my birthday :(
 » 23 months ago, # |   0 Just for remind
 » 23 months ago, # |   +5 Contest starts in 3 minutes. Good luck everyone.
 » 23 months ago, # |   +8 How to solve F? BTW, what was the purpose of this E?
 » 23 months 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.
•  » » 23 months ago, # ^ |   +5 Or you could simply use long long instead of bitset(in the last problem).
•  » » » 23 months ago, # ^ |   +3 I always use long long *as* bitset.
•  » » » » 23 months ago, # ^ |   0 Can you tell more about your p4 and p5 solutions, please?
•  » » » » » 23 months 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).
•  » » 23 months ago, # ^ |   +1 Can you explain how can you reduce it to a tree since the graph may have cycles?
•  » » » 23 months ago, # ^ |   0 The cycles are irrelevant. You can block what's on the cycles in any way you want.
•  » » 23 months ago, # ^ |   +7 Could you explain problem 5's solution using BIT in more detail? Tnx. :)
 » 23 months 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
 » 23 months ago, # |   0 How did Mo's algorithm TLE on E? I thought 5 seconds was enough for 500,000*700 = 350,000,000.
•  » » 23 months 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
•  » » » 23 months ago, # ^ |   0 Oh, I see why now. I used map instead of unordered_map. Silly me XD. Thanks for the code.
•  » » » » 23 months ago, # ^ |   0 Actually with unordered_map it still TLEs. http://pastebin.com/CyARk8ck[Code]
•  » » » » » 23 months ago, # ^ |   +8 Don't use unordered_map.
•  » » » » » » 22 months ago, # ^ |   0 Why not?
•  » » » » » » » 22 months ago, # ^ |   0 Because he is getting TLE?
•  » » » » » » » » 22 months ago, # ^ |   0 I mean why is it slower than a map?
•  » » » » » » » » » 22 months ago, # ^ |   0 I never told him to use map.
•  » » 23 months ago, # ^ |   +3 You are absolutely right. My solution (MO) had passed.
•  » » 23 months ago, # ^ |   -6 I thought log(N) ≠ 700.
•  » » » 23 months ago, # ^ |   0 Sqrt(N) = 700?)
•  » » 23 months ago, # ^ |   0 Yup, MO definitely worked for me, might be an error in the code or high constant.
•  » » 23 months 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
•  » » » 23 months ago, # ^ |   +1 You need O(1) acces to cnt[v[st]] , not O(log n) with map
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +3 Did Coordinate compression so that the values fit inside array.Accepted code Thanks :)
•  » » 23 months ago, # ^ |   0 I got TLE with MO too :(
•  » » » 23 months ago, # ^ |   0 Perhaps, you got TLE with map/unordered_map, too? Could you show your code?
•  » » » » 23 months ago, # ^ |   0 Can you please see my code, I also used map with Mo's algo but got TLE in last 4 cases.
•  » » » » » 23 months ago, # ^ |   +1 Don't use map.
•  » » » » 23 months 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.
•  » » 23 months 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
 » 23 months 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.
•  » » 23 months ago, # ^ |   +6 I didn't understand your algorithm. Aren't the endpoints of an edge always in the same connected component?
•  » » » 23 months 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.
•  » » » » 23 months ago, # ^ |   +3 With his wording, it sounds like he didn't think cliques of size two were okay.
•  » » » » » 23 months 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.
•  » » » » » 23 months 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; } 
•  » » » » 23 months 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 :)
•  » » » 23 months 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.
•  » » » » 23 months ago, # ^ |   +3 Flipping a node twice is the same as not flipping it, so yes, you were correct. It's a 2SAT problem.
•  » » » » » 23 months 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.
•  » » » » » » 23 months ago, # ^ |   +8 This would result in the same graph as if you had never flipped the first node.
•  » » » » » » 23 months 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.
•  » » » » » » » 23 months ago, # ^ |   +3 You are right. I'm sorry, I'm stupid
 » 23 months 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 :(
 » 23 months 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
 » 23 months 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!
 » 23 months 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.
 » 23 months ago, # |   0 Did anyone else solved Problem E : Poklon with segment tree? i would like to compare my segment tree approach!
•  » » 23 months 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.
•  » » » 23 months 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
•  » » » » 23 months ago, # ^ |   0 Tnx. I learned a lot from you! Have a nice day. ;)
•  » » 23 months ago, # ^ |   +1 I used a segment tree :-Code
 » 23 months ago, # |   0 But it is clash with global game jam :(
 » 22 months ago, # |   0 How do I solve p3? A trivial solution gains 50 points.
•  » » 22 months 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.
•  » » » 22 months ago, # ^ |   0 Thanks!! I love you. I'll try it.