### Vovuh's blog

By Vovuh, 3 years ago, translation, ,

Hello, Codeforces!

5th august 2015 at 19:00 MSK Codeforces Round #Pi will take place for second division participants. Participants from the first division are able to participate out of the contest.

This is my first round on Codeforces. I hope you will enjoy the tasks and this will stimulate me to prepare new rounds! Wish you quick Accepted verdicts and successful hacks.

I want to thank Michael Mirzayanov (MikeMirzayanov) for wonderful platforms Polygon and Codeforces and for help in preparing the tasks, Maxim Akhmedov (Zlobober) for help in contest preparation, Maria Belova for translation statements to english, and also my friends Danil Sagunov (dans) and Vitaliy Kudasov (kuviman) for solving the tasks.

Participants will be given six tasks and two and the half hours for solving them. Scoring system will be announced closer to round start.

UPD: Scoring: 500-1000-1500-2000-2500-2500.

UPD Editorial

•
• +280
•

 » 3 years ago, # | ← Rev. 2 →   0 I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?
•  » » 3 years ago, # ^ |   +27 Maybe because it's round 314. As a remainder PI = 3.1415...
•  » » » 3 years ago, # ^ | ← Rev. 4 →   -7 Oh, it seems so :) I thought that round #314 will be held after Pi-round, but I was wrong.P.S. Thanks for clarifying. Perhaps, I would not participate in this round because Pi-round sounds like a Math-round. And I'm weak at math :P
•  » » » » 3 years ago, # ^ |   +19 So, next PI round will be at 3141 th contest ... about 3000 rounds later :v :P
•  » » » » » 3 years ago, # ^ |   0 Looking forward to participate in that Round :)
•  » » » » » » 3 years ago, # ^ |   +5 Well, that would be more than 50 years from now. So, I don't want to miss today's Pi round. Let's hope that, we can see our grandchildren participating in a CF Pi-round :P
•  » » » » » » » 3 years ago, # ^ |   +2 Too bad ;( We lost "Round #e" (271). I love "e" more than "pi".
•  » » 3 years ago, # ^ |   -26 His name is P1kachu similar to Pikachu. First two words are Pi, this may be the reason
 » 3 years ago, # |   -20 Hopefully there will be interesting and original math problems!
•  » » 3 years ago, # ^ |   +10 What is the point of hoping for something like this; this is not IMO. Instead, you should be hoping for an interesting and varied problem-set — one consisting of other things as well.
•  » » » 3 years ago, # ^ |   -23 Because it is Pi round, hope for comp geo :O
 » 3 years ago, # |   0 nezt PI Round #3141 ?
•  » » 3 years ago, # ^ |   0 According to this logic, first Pi round was 3, but was it?
•  » » » 3 years ago, # ^ |   0 Another round is 31, but was it?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 And round 1,4,9,16,... should be perfect square rounds, but 1 should also be square root round, but were they?
•  » » » » » 3 years ago, # ^ |   0 In that logic every round should be named integer round -_-
 » 3 years ago, # |   +7 Hello! Should I pronounce your name as Pi-kachu?
•  » » 3 years ago, # ^ |   +9 ლ(ಠ益ಠლ)
 » 3 years ago, # |   +42
•  » » 3 years ago, # ^ |   -13 I like this picture very much but what does it mean here??????????????? :|
•  » » » 3 years ago, # ^ |   +6 this contest prepared by P1kachu :)
•  » » » » 3 years ago, # ^ |   +1 Oh I realized :( Thank you for your answer :) Nice picture ;)
•  » » » » » 3 years ago, # ^ |   0 welcome~ hope you have a good contest!
•  » » 3 years ago, # ^ |   +1 so cute ^_^
 » 3 years ago, # |   +20 I think I'll skip this one and wait for Codeforces Round #Tau
 » 3 years ago, # |   -8 Is it a rating round？
•  » » 3 years ago, # ^ |   +1 of course
•  » » » 3 years ago, # ^ |   0 Ok. Come on!
 » 3 years ago, # |   +240
•  » » 3 years ago, # ^ | ← Rev. 2 →   +51 Nice try Internet Explorer(or Edge)... Very nice try...
•  » » » 3 years ago, # ^ |   +39 Speaking of internet explorer reminds me this pic:
•  » » 3 years ago, # ^ |   +4 Codeforces Round #FF also instead #255.
 » 3 years ago, # |   0 This time they write "Scoring system will be announced closer to round start.". Why they don not use same sentence ??????????????? ;)
 » 3 years ago, # |   +2 W<...
 » 3 years ago, # |   +36 Maybe there will be a problem about circles ? :-)
•  » » 3 years ago, # ^ |   -8 Why are you so diao?
•  » » » 3 years ago, # ^ |   0 Oh , xiaoxin juju appears upstairs！
•  » » » » 3 years ago, # ^ |   0 baba will not like you TUT
•  » » » » » 3 years ago, # ^ |   -8 oh~xiaoxin juju
•  » » 3 years ago, # ^ |   +6 i do think geometry is your dish.
•  » » 3 years ago, # ^ |   +3 You were wrong :D
•  » » » 3 years ago, # ^ |   0 Oh~ it seems that the writer missed a good opportunity :P
 » 3 years ago, # |   +1 So this contest will be all about math problems? (#Pi)
•  » » 3 years ago, # ^ |   0 It will be crazy, I guess.
 » 3 years ago, # |   +18 I think that this round shuld be irracionally long. Lets say 3h 8m 30s or 3.14h :)
 » 3 years ago, # |   +2 i'm thinking what will a Codeforces Round #i be like... i'd be imaginary for sure :D
 » 3 years ago, # |   +11 "Wish you quick Accepted verdicts and successful hacks." — interesting combination. To hack successfully, I need to lock a problem. Then someone hacks me (according to your wishes) and I can't correct my solution because I've locked it before. Very sad scenario.Anyway, have fun everybody :)
•  » » 3 years ago, # ^ |   +7 paradoxical :p
•  » » 3 years ago, # ^ |   0 What bothers me usually is when authors wish high ratings for all of the participants :-/
•  » » » 3 years ago, # ^ |   0 How does Tourist get rating rise?
•  » » » » 3 years ago, # ^ |   +20 Well, I assume he wins contests.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 You get rating rise when you perform better than your expected position in a contest. Tourist's expected position=1. He can't be better than 1. Yet, he gets rating rise. Am I missing something?
•  » » » » » » 3 years ago, # ^ |   0 I really do not know how the rating works, but I guess that expected position doesn't have to be an integer. He'd get precisely expected position 1 if he were to compete alone, any participant added should change his expected position a bit, but in the end it probably stays in the interval [1;2], so getting 1 is the only way to score better than his expected position :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 So lock in the last 5 minutes, and spend 2hr 25 minutes before that making sure your answer is correct :)
•  » » 3 years ago, # ^ |   -7 You solved C in 3 minutes!!! What is this sorcery?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Z38 had A after 2 minutes (1:56). I was ~80 seconds slower in task with roughly the same amount of code needed. It doesn't look like sorcery.
•  » » » » 3 years ago, # ^ |   0 Like you didn't even have to read the question, you just started typing #JustDiv1CoderThings
 » 3 years ago, # |   +8 why 2:30 ???
•  » » 3 years ago, # ^ |   +1 Six problems I guess :p
 » 3 years ago, # |   0 So i guess in each of the problems today we have to be introduced with the person "Mr. PI" :D :D :D
 » 3 years ago, # |   +1 when you are wishing for some body successful hacks you are wishing for some body else unsuccessfulsubmits!!! i don't think it's a good wish!thanks ;)
 » 3 years ago, # |   +15 2.5 hour = 6 problems? So I guess P1kachu prepare a nice problem F for us to solve...
»
3 years ago, # |
-50

# define in_round_#pi ++

int RP;

int main(){ while(RP)RPin_round_#pi; return 0; //By the way,thanks to writer }

 » 3 years ago, # |   +34 Round #404 will be declared as round #Error or round #NotFound
•  » » 3 years ago, # ^ |   +4 Nice idea !!
•  » » 3 years ago, # ^ |   +1 numbered rounds of Fibonacci numbers: round #Fibonacci
•  » » » 3 years ago, # ^ |   +2 P.S. Next Fibonacci round is 377 *
•  » » » 3 years ago, # ^ |   0 now I found out first comment in blog create other comment first comment: "I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?" other comments also are about name of contests
•  » » » » 3 years ago, # ^ |   0 just kek
 » 3 years ago, # |   +23 That proud moment when a blue coder prepares a CF round :D Hats off !!! keep it up :D
 » 3 years ago, # |   0 This is the first contest i join ever on codeforces :)
•  » » 3 years ago, # ^ |   0 OK. Good Luck :)
 » 3 years ago, # |   0 It has been a long time since the last Div2 contest.. It's obvious that the number of registrants is very large this time and people are eager for such an event.. Let's enjoy
•  » » 3 years ago, # ^ |   +2 I'll be Grey in no time
 » 3 years ago, # |   +5 So since there are 6k+ participants, on a scale from Google.com to contest.Bayan.ir, how down is Codeforces.com going to be ?
 » 3 years ago, # |   +11 6278 people registered which is more than 6274 people registered for good bye 2014out of 6278 registrants 935 people are unrated
 » 3 years ago, # |   +3 The first round was written by Expert user that I have ever participated!
 » 3 years ago, # |   +12 What on earth is pretest 19 in Problem E?
•  » » 3 years ago, # ^ |   0 I guess you're not finding the bridges correctly. I got WA 19 because of a caveat in my solution, I only check for edges that definitely are on the shortest path ONLY from the start and the end, but there could actually be bridges in the middle of the path too. An example edge formation , start = 1 , end = 8 : 1 2 1 3 2 4 3 4 4 5 5 6 5 7 7 8 6 8The edge 4 5 is definitely on the shortest path since it is a bridge in the shortest path graph. Hope it helps .
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 No, I think I took care of that. Oh well, will wait for the editorial for E.
 » 3 years ago, # |   +17 Problem E with modulo based hacking was pretty funny. I had a generator that generates a input for any mod. Some guy from my room sent his solution in the last moment to make sure that I can not hack him. :)
•  » » 3 years ago, # ^ |   +5 Is there a solution without modulo calculations?
•  » » » 3 years ago, # ^ |   +40 What is a solution with modulo calculations?
•  » » » » 3 years ago, # ^ |   0 @ikbal can you show how you made the generator?Also I used doubles to calculate number of paths. Paths can be at most 10^500 which fits in a double. With modulo calculations, you just mod this number continuously.
•  » » » » 3 years ago, # ^ |   +8 We build DAG where there is a directed edge (u,v) if there is an edge (u,v) in graph and dest[s,u]+dest[u,v]+dest[v,t]==dest[s,t]. Then we say that edge (u,v) is a bridge if number of ways (s,u)*(v,t)=(s,t). But this values are large, so I took them by modulo
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +9 Instead of counting number of ways you can change this DAG into undirected graph (all edges become bidirectional) and just find all bridges in this graph.
•  » » » » » » 3 years ago, # ^ |   0 Can you please explain why this is correct ?
•  » » » » » » 3 years ago, # ^ |   0 I got a WA using an undirected graph. Can you explain the proof of this?
•  » » » 3 years ago, # ^ |   +16 Yes, there is. And not only one.1) You can find all edges that can be in shortest path and then find bridges in this graph.2) Find all edges that can be in shortest path. Then realize that we are on this edge in fixed interval of time. Edge is in all shortest paths if its interval doesn't intersect with other intervals. (It's my solution, you can read it).
•  » » 3 years ago, # ^ |   0 Was my solution also hacked because of modulo? It would be quite strange since I used both overflow hash & modulo. I even changed modulo after getting hacked, but still got WA (on your hack).
•  » » » 3 years ago, # ^ |   0 Just create two paths one with 10^9+7 and one with 2^64 ways. If we merge them together from their ends by an edge new long path would have (10^9+7 * 2^64) ways.
•  » » 3 years ago, # ^ |   0 What sense not to be hacked if solution is wrong?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +11 Because usually it's impossible for problem setter to create tests against every modulo.
•  » » 3 years ago, # ^ |   0 I'm wondering if his code gets accepted after all. :/
•  » » » 3 years ago, # ^ |   +5 Yes:D12374662P.S. Glad for you, pal:D
 » 3 years ago, # | ← Rev. 2 →   +1 Finally solved C with 2 seconds on timer :( That's embarrassing.
•  » » 3 years ago, # ^ |   0 me to.
 » 3 years ago, # |   0 Spent 30 minutes trying to find the problem with this attempt at problem C. Can someone lend a hand?http://pastie.org/private/mmg81uzwfniinmxabqa2rw
•  » » 3 years ago, # ^ | ← Rev. 2 →   +2 k * k overflows.EDIT: Result (num) could overflow too.
•  » » » 3 years ago, # ^ |   0 It returns 0, regardless of input. I didn't even have time to consider overflows haha.
 » 3 years ago, # |   +1 What was test case 5 of D? I used a solution that kept track of valid intervals where battleships could be placed: if bob's shot interrupted an interval, then I split it into 2 intervals, and for each interval I calculated IntervalSize / SizeOfShip. If this was less than NumberOfShips, then I printed that index and stopped the program. At the very end I printed -1 and ended to catch the case where it is undeterminable. What is wrong with this approach?
•  » » 3 years ago, # ^ |   +3 Ships cannot touch each other.
 » 3 years ago, # |   0 What's the intended solution on D?I tried keeping a sorted vector of pairs, representing all uninterrupted segments where you can place ships. Every time you fire a shot, you find the segment that shot is in and split the segment in two. Used binary search to make the segment searching faster, but my solution was wrong on case 5. Is the idea wrong, or did I mess up my implementation?
•  » » 3 years ago, # ^ |   0 How do you calculate the number of ships that can be placed into one interval?
•  » » » 3 years ago, # ^ |   0 interval size / size of ship
•  » » » » 3 years ago, # ^ |   +10 Yeah, that's wrong. They must be non touching. I saw this only after a lot of wrong submissions :D
•  » » » 3 years ago, # ^ |   +3 Let there be maximum of x ships of size a in the interval of size n.Then x*a+(x-1)<=nhence, x=(n+1)/(a+1)
•  » » 3 years ago, # ^ |   +5 Idea is ok. Alternative solution is to do binary search over result.
•  » » 3 years ago, # ^ |   0 I processed the queries from last to begin and kept a disjoint set for the connected parts and instead of splitting merging.
•  » » 3 years ago, # ^ |   0 Apparently, you can't have 2 ships RIGHT next to each other, so when calculating number of ships possible in an arrangement, you had to make sure you left 1 space in between each(so you had to add extra logic for both inside the interval, as well as between consecutive intervals.
•  » » 3 years ago, # ^ |   +10 My solution was binary searching for the answer. You fix the amount of shots fired then you mark those cells. Once you've marked some cells as shot you can get the maximum amount of ships that can be placed in O(N) using greedy approach.
•  » » 3 years ago, # ^ |   0 1) Let's find the asnwer by binary search (answer — k) 2) Each iteration of search we will check by function CHECKING that says TRUE if we can't place all ships with k turns and FALSE if we can. If True, you should make left_border=k, and if False — right_border=k+1 3) How does CHECKING work? Make a vector of field and fill it by 1(free place) and 2(place where Bob shooted). Then in cycle just greedy fill it by ships from left to right and calculate its total. Return total
 » 3 years ago, # | ← Rev. 4 →   0 Eh, I believe the "two weapons cannot touch" part in D should have been explained more clearly... I was thinking it just meant a cell cannot belong to more than one weapon (and I guess so did everyone getting WA on pretest 5).
•  » » 3 years ago, # ^ |   0 The same thing happened with me. I spent 2 hours making numerous test cases and my code was working for all of them. So , after the contest , upon asking adurysk I realized that two ships could not "touch" meant they couldn't be adjacent . FacepalmNeeded to change (N/K) to (N+1)/(K+1) to get it Accepted :P
•  » » » 3 years ago, # ^ |   +12 It was written both in statement and in input section. How could it be explain more clearly?
•  » » » » 3 years ago, # ^ |   0 It just said "the ships cannot intersect and even touch each other"- it would be better if the problemsetter explicitly mentioned that you cannot place two weapons right next to each other.
•  » » » » » 3 years ago, # ^ |   +13 The author separately mentioned intersecting and touching, shouldn't that be a hint that these describe two distinct situations?
 » 3 years ago, # | ← Rev. 2 →   0 The round was awsome. I enjoyed a lot E and F. Congrats for the round. Also , was F a dp in O(N^3*K) ?
•  » » 3 years ago, # ^ |   0 My F was O(n ^ 2 + nk) i think
•  » » » 3 years ago, # ^ |   0 Mine is O(N^2 * K) afterall ( http://codeforces.com/contest/567/submission/12374862 ) , but it can be done in your complexity.
 » 3 years ago, # |   0 what a contest !!!!
 » 3 years ago, # |   +1 Can someone help how to solve C ?? :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 two mapsm1[x] = y <=> count of subsequence of length one finishing at x equals ym2[x] = y <=> count of subsequence of length tho finishing at x equals ySo, we getting num a. Then ans += m2[a/k]; m2[a] += m1[a/k]; m1[a]++
•  » » » 3 years ago, # ^ |   0 sorry but i didnt get u ??
•  » » » » 3 years ago, # ^ |   0 If we've got num a, how many subsequence of length one finishing at a? As many as subsequences of length two finishing at a/k. So ans += m2[a/k]Analogycal, how many subsequences of length two finishing at a? As many as subsequences of length one finishing at a/k. So m2[a] += m1[a/k]m1[a]++ because we've got new subsequence of length one finishing at a.
•  » » » » » 3 years ago, # ^ |   0 yeah got it thanks :)
 » 3 years ago, # |   0 What was the idea for keeping track of the number of shortest path? Does it use Dijkstra?
 » 3 years ago, # |   +5 Can anyone who solved F explain a solution? The problem seemed like hell to me :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 DP; you put the pairs from largest to smallest. States are "the blocks you put so far are in the interval [i,j]". There are just 3 possible transitions from any state and you just need to check if any in/equality becomes invalid for each of them.The simplest implementation is O(KN3), which definitely passes.
•  » » 3 years ago, # ^ |   +3 dp[left][right] — in how many ways can we fill blocks 1... left and right... 2N with small numbers (numbers lower that those left for interval left + 1... right - 1. We must consider 3 cases: adding two new equal numbers in left + 1, left + 2, or in left + 1, right - 1, or in right - 2, right - 1. For all 3 cases we must check is everything would be ok for them — those two places are equal to each other but lower than remaining places in left + 1... right - 1.
 » 3 years ago, # | ← Rev. 4 →   -7 OMG i forgot to remove debugging code and the stderr flushes made me TLE on problem D.... ;( for(auto i:my)cerr << i.first <<":"<
•  » » 3 years ago, # ^ |   0 use tab indent to understand your bug!!
•  » » » 3 years ago, # ^ |   0 There are no bugs there, its just that i'm writing a bunch of endl's to cerr (which i used while working in the problem), and i didn't remove them before submitting....
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone explain me how to solve problem D??
•  » » 3 years ago, # ^ |   -6 what a question !!! :D
•  » » » 3 years ago, # ^ |   0 If you want to tell then tell me otherwise no need to comment . Ok
•  » » 3 years ago, # ^ |   +3 One way is to find result by binary search. Then, we mark some cells as blocked and we need to count maximal possible number of ships. Say if you need more explanation.
•  » » » 3 years ago, # ^ |   0 Yeah can you elaborate it more??
•  » » » » 3 years ago, # ^ |   +3 which part?
•  » » » » » 3 years ago, # ^ |   0 Here binary Search will be applied on what?And then How cells can be marked as blocked??
•  » » » » » » 3 years ago, # ^ |   +3 Binary search on result — size of prefix of given blocked cells. Cells can be marked as blocked with array of booleans. Then we iterate from 1 to size_of_grid and calculate number of ships we can have.
•  » » » » » » » 3 years ago, # ^ |   0 Hey can u please explain problem E. Or to be more specific, can u explain how to find an edge that the president may or may not go. I understood how to collect the edges that are part of shortest path but couldn't figure out how to classify edges which are part of shortest path in terms of those which will be visited for sure vs may or may not case.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The rough idea is to maintain the maximum number of ships you can put on the board.Notice the fact when you hit a spot, you are splitting an interval(between 2 previously-hit spots) into 2 intervals. With that, you can calculate how many ships can be put on the original interval and on these new 2 intervals, and update the number we're maintaining.Use std::set to store previously-hit spots.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Let's use a some set, which will keep disjoint segments. Also let's keep some value T which means what is the maximum number of ships we can arrange on a board.When we add a segment to the set, we must increase T by some value x, which means the maximum number of the ships we can arrange on current segment. This number is equal to (len + 1) / (a + 1) where len is a length of the segment and a is the length of the shipAt first let's add segment (1, n) to the set.So, when the cell c is coming, let's find a some segment(l, r) which keeps c (l <= c <= r). We decrease T by (len(l, r) + 1) / (a + 1). Then we add segments (l, c - 1) and (c + 1, r) to the set and increase T by appropriated values.If we processed current operation and T is less than k, answer will be equal to the number of operations we processed already.For keeping segment we can use a simple set of pairs. My solution: 12365410
•  » » » 3 years ago, # ^ |   0 Wow, I used to write a segment tree in that problem, but your solution is much more simple than mine, thanks!
•  » » » » 3 years ago, # ^ |   0 Of course, you can use segment tree, but I think set is the simplest one.
 » 3 years ago, # |   +67 Nice problems P1kachu! I like C and F especially. Hope to see more rounds from you.
 » 3 years ago, # | ← Rev. 2 →   0 I got stuck (kept failing test case #13) in problem B. Embarrassing, but this was my first contest. Here is my solution:https://ideone.com/G5fuEl Can some one give me any ideas? I can't sleep, keep thinking about it :|.
•  » » 3 years ago, # ^ |   0 You can view small inputs after the contest. Scroll to the end here: 12373900
•  » » 3 years ago, # ^ |   +3 In the if at line 29 you should add : p[abs(arr[i])]-=arr[i]; This is because the person left, but you never marked him coming in. So in the beginning of the iteration you added arr[i], marking him leaving, once you understand that he's been in all along you should make up for his coming.Feel free to ask questions :)
•  » » » 3 years ago, # ^ |   0 Thanks a lot. Ah.. you guys are amazing :). It looks like everyone here has very good analytical skills. I'll keep practicing, hope to get better.
•  » » » 3 years ago, # ^ |   0 Just one question I had in mind.. did you guys used some debugger when you were starting out?
•  » » » » 3 years ago, # ^ |   0 Debug output is usually the fastest way. Just add some safeguards to your template to prevent it from working on the server side: #ifndef ONLINE_JUDGE # define LOG(x) (cerr << #x << " = " << (x) << endl) #else # define LOG(x) ((void)0) #endif ONLINE_JUDGE is defined in the Codeforces environment.
•  » » 3 years ago, # ^ |   0 Your if "if(p[abs(arr[i])]<0){" should be done at most once for every arr[i]. You have WA for test 3 - 5 + 5 - 5 
 » 3 years ago, # |   0 What is the idea of E?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +11 My solution is to dijkstra 2 times, one from s and one from tfor each edge u->v if dist(s->u) + c(u,v) + dist(v, t) == dist(s, t), u->v may be a "sure" edgeTake all those edges and eliminate the direction, we can find the bridge by simple DFS.Note that there may be multiple edges between two vertexes. I failed E during the contest because of that :(
•  » » » 3 years ago, # ^ |   0 can u please explain this :"Take all those edges and eliminate the direction, we can find the bridge by simple DFS."Also it would be great if you can give a brief explanation about problem E
 » 3 years ago, # |   0 In problem C, what would be the answer if k=1 ??
•  » » 3 years ago, # ^ |   0 You could easily count how many times a given numbers repeats using a map, then it's basically C( [amount of repetitions of this number], 3) which is equal to [reps * (reps-1) * (reps-2)/6] when you simplify the formula.
•  » » » 3 years ago, # ^ |   0 Thanks, my code gave AC, unpredictable integer overflow at the contest -_-
•  » » » » 3 years ago, # ^ |   0 Why is it unpredictable ?
•  » » 3 years ago, # ^ | ← Rev. 5 →   0  for(int i=0;i
 » 3 years ago, # |   0 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { String s = in.readLine(); String[] ar = s.split(" "); if (ar[0].charAt(0) == '+' && !t[Integer.valueOf(ar[1])]) { cur++; t[Integer.valueOf(ar[1])] = true; } else if (ar[0].charAt(0) == '-' && t[Integer.valueOf(ar[1])]) { cur--; } else if (ar[0].charAt(0) == '-' && !t[Integer.valueOf(ar[1])]) cap++; cap = Math.max(cap,cur); } out.print(cap); }my code above for problem B is incorrect, because the bold line, without that line, the code is correct. But the number assigned to people is unique, why can someone take same number twice?
•  » » 3 years ago, # ^ |   +2 please paste your code here.
 » 3 years ago, # |   0 Wow the problemsets are really nice. It's hard to believe that it's prepared by a blue coder.
•  » » 3 years ago, # ^ |   +4 That's because, this rating shows the measurement of competitive programming skill which is different from problem inventing skills. There are many cases where enough knowledge doesn't help the subject to do better in competitive programming.
•  » » 3 years ago, # ^ |   +1 No.
 » 3 years ago, # |   0 Can someone point out the mistake in this code?Problem DThank you in advance.
•  » » 3 years ago, # ^ |   0 it=s.upper_bound(mp(mov[i],-1)); should be it=s.upper_bound(mp(mov[i],n+1)); in order to find the intersecting interval after decrementing it. If you have an interval that starts at mov[i], upper_bound will return it and decrementing will miss it.
•  » » » 3 years ago, # ^ |   0 Thanks a lot. Silly mistake, could have been avoided during the contest.
 » 3 years ago, # |   0 While solving E, i had to keep track of number of shortest paths passing through a particular edge. But this value can exceed 10^18. I used hashing modulo 2 large primes to keep track.Is there any other (deterministic) workaround to this?
•  » » 3 years ago, # ^ |   +3 Yup, Bridges in the "shortest path graph" are guaranteed to be on every possible shortest path.
•  » » » 3 years ago, # ^ |   +1 Woah, that's a great observation, thanks :)
 » 3 years ago, # |   0 used coordinate compression in c :P
 » 3 years ago, # |   +4 It's just div 2, but I'm very happy anyway. Nice problems! :D
 » 3 years ago, # |   0 Thanks for a great contest!
 » 3 years ago, # |   +1 Hello, this is my first contest. I'm just curious about one thing : when does the rating change after a contest?
•  » » 3 years ago, # ^ |   0 It will be update, may be today or at most tomorrow.
•  » » 3 years ago, # ^ |   +8 Hello, dear newcomer! You should now that right now Mike Mirzayanov, Zlobober and others are sitting at the round table and hotly-debate everyone's rating change. It takes a lot of time, you know. It was my not serious thought of things when I took part in my first contests. Now I think, that the question of looking for cheaters is hardtime. Maybe anyone know another 'why'?
•  » » » 3 years ago, # ^ |   0 Thanks for the answer, I expected it to be more automatically updated. Great to know that they look for cheaters.
•  » » 3 years ago, # ^ |   0 Mia rating
 » 3 years ago, # |   0 Your problems are really amazing. Thank you :)
 » 3 years ago, # | ← Rev. 5 →   -7 Thank you for the contest. Can you update top 5 contestants as well :D ?Update: Down voters, so you don't want to see your name when you are in top 5?
 » 3 years ago, # |   0 Why my solution is skipped? I use only one account.http://codeforces.com/contest/567/submission/12361738
 » 3 years ago, # |   0 Can anybody help me check my code of problem E: http://codeforces.com/contest/567/submission/12382102Thanks!
•  » » 3 years ago, # ^ |   0 You haven't taken into account multiple edges while checking the YES condition
•  » » » 3 years ago, # ^ |   0 I think my code has covered this case. Can you give me a test case to illustrate it?
•  » » » » 3 years ago, # ^ |   0 Yeah you are right you have taken that into account.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Deleted
 » 3 years ago, # |   0 Could someone explain this testcase (which is the 37th) of Problem E? 10 10 1 10 1 5 178 1 8 221 2 7 92 2 8 159 3 5 55 3 6 179 3 10 237 4 8 205 5 6 191 8 10 157 The output is NO for all edges except the two that lie on the unique shortest path of length 378, for which the answer is YES. What I don't understand is why the answer for all other edges is NO. Let's take for example the path (1 — 5 — 3 — 10 ) of length 470. The first and the last edge could be reduced by 93 to give a path of length 377 in which case they lie on the unique shortest path. I probably misunderstood something in the problem statement. Thanks in advance.
•  » » 3 years ago, # ^ |   +3 I had the same problem.In the statement it says The road is directed from city ai to city bi. In this test case you can't go from 5 to 3 and therefore the path (1 — 5 — 3 — 10) doesn't exist.
 » 3 years ago, # |   +1 It's my first contest in codeforces and I enjoyed it very much. Wish your next round,and I hope I can do better then.
 » 3 years ago, # | ← Rev. 4 →   +1 could someone tell me why this solution gives TLE for problem D? It's run in O( m log(m) ) 12387839
•  » » 3 years ago, # ^ |   0 :p :p
•  » » 3 years ago, # ^ |   0 Not too sure about the TLE, but my suspicion is your set of ints. You should hold your intervals/segments as pairs of ints. Modify your program accordingly and it should pass.
•  » » » 3 years ago, # ^ |   0 No you don't need to. Refer to my submission
•  » » 3 years ago, # ^ |   0 Lower (or upper) bound has linear complexity on set. Use set.lower_bound(value) instead. (logn)
•  » » » 3 years ago, # ^ |   0 got AC :) thanks for this information I didn't know that lower_bound have linear complextiy on set Miyukine.
•  » » 3 years ago, # ^ |   0 12399997 AC
 » 3 years ago, # |   +6 I am not from the top 5, but I love to see the winners' names in the updates :)