Before contest

Codeforces Round #492 (Div. 1) [Thanks, uDebug!]

17:09:21

Register now »

Codeforces Round #492 (Div. 1) [Thanks, uDebug!]

17:09:21

Register now »

*has extra registration

Before contest

Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

17:09:21

Register now »

Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

17:09:21

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 166 |

3 | Petr | 155 |

3 | csacademy | 155 |

5 | Swistakk | 149 |

5 | lewin | 149 |

7 | Um_nik | 142 |

8 | Errichto | 140 |

9 | matthew99 | 138 |

9 | Vovuh | 138 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2018 02:25:39 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

I loved solve hsin.hr problems. Quality of problem is high. Thank you.

How often do you have a contest there? One in a year or mouth?

Usually 7 rounds in one season and a special, more difficult final round. So, roughly one contest a month.

But it is clashes with my birthday :(

Just for remind

Contest starts in 3 minutes. Good luck everyone.

How to solve F? BTW, what was the purpose of this E?

Seemed fairly easy, I only spent about 1.5 hours coding and I think I got all. My solutions:

p4a_{ij}=a_{0, ij}^x_{i}^x_{j}, wherex_{i}is xor'd every time cityiis selected,a_{ij}is the final adjacency matrix,a_{0, ij}the inital adj. matrixp5offline with map<> and a sum-BIT with range updates,

p6reducible to: you have a tree with

Nvertices, block exactlyKvertices 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 inO(NK^{2}), but forK< 64,O(NK) with bitsets is possibleUPD: Damnit, my last problem failed just on a triviality.

Or you could simply use long long instead of bitset(in the last problem).

I always use long long *as* bitset.

Can you tell more about your p4 and p5 solutions, please?

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).

Can you explain how can you reduce it to a tree since the graph may have cycles?

The cycles are irrelevant. You can block what's on the cycles in any way you want.

Could you explain problem 5's solution using BIT in more detail? Tnx. :)

As the contest has ended, so how long should we wait for the system testing to finish?

Edit: Ranklist can be seen now

How did Mo's algorithm TLE on E? I thought 5 seconds was enough for 500,000*700 = 350,000,000.

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

Oh, I see why now. I used map instead of unordered_map. Silly me XD. Thanks for the code.

Actually with unordered_map it still TLEs. http://pastebin.com/CyARk8ck[Code]

Don't use unordered_map.

Why not?

Because he is getting TLE?

I mean why is it slower than a map?

I never told him to use map.

You are absolutely right. My solution (MO) had passed.

I thought

log(N) ≠ 700.Sqrt(N) = 700?)

Yup, MO definitely worked for me, might be an error in the code or high constant.

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

You need O(1) acces to cnt[v[st]] , not O(log n) with map

Did Coordinate compression so that the values fit inside array.Accepted code

Thanks :)

I got TLE with MO too :(

Perhaps, you got TLE with map/unordered_map, too? Could you show your code?

Can you please see my code, I also used map with Mo's algo but got TLE in last 4 cases.

Don't use map.

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.

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

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.

I didn't understand your algorithm. Aren't the endpoints of an edge always in the same connected component?

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

A_{node}then for some 3 nodesx,y,zif there is an edge already presentA_{x}+A_{y}should be even, otherwise odd(similarly forA_{x}+A_{z}andA_{y}+A_{z}). It is easy to see this only satisfies when eitherA_{x}+A_{y},A_{x}+A_{z},A_{y}+A_{z}are all even or 1 of them is even while other two are odd. This corresponds to the clique condition.CodeEDIT: sorry for errors, i didnt pay attention while typing.

With his wording, it sounds like he didn't think cliques of size two were okay.

Or perhaps he missed the case where all

A_{x}+A_{y},A_{x}+A_{z},A_{y}+A_{z}are odd. That is, there are no edges in graph originally. It is easy to miss it.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:

CodeYes! 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 :)

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 nodeswandy. After flippingw, 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.Flipping a node twice is the same as not flipping it, so yes, you were correct. It's a 2SAT problem.

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.

This would result in the same graph as if you had never flipped the first node.

No, you won't obtain a different graph. It's the same as flipping the same other nodes and not touching this one.

You are right. I'm sorry, I'm stupid

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 :(

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

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!

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.

Did anyone else solved

Problem E : Poklonwith segment tree? i would like to compare my segment tree approach!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.

okay lets jump into it with an example (given array):

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 1`

but 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 1`

can 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 1`

and the answer is 2!

we simple used segment tree to update and find the query.

CODE

PS: sorry for my bad English and the way i wrote, i usually do not post in codeforces :S

Tnx. I learned a lot from you! Have a nice day. ;)

I used a segment tree :-

Code

But it is clash with global game jam :(

How do I solve p3? A trivial solution gains 50 points.

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.

Thanks!! I love you. I'll try it.