0
I've thought about it a little more and turns out there is no blowup apart from the memory needed to store the O(k) queues. A vertex is pushed to the queue at most once per its incoming edge, and all outgoing edges from a reachable vertex are processed exactly once. So the total number of pushes to all queues is O(m). 
0
Why do you estimate the number of operations as 10^{8} here? The 1000 comes from the observation that at most half of the queries require answers so we may only do the BFS when the query of type 1 arrives. However, the BFS itself is not a standard lineartime BFS, but more like emulating a priority queue with multiple firstin firstout queues. I'm not sure that the worst case can be achieved, at least not without degrading to actual changes, because the number of edges changed in the problem is at most 10^{6} and the change itself (increasing by 1) seems too limiting. In the code, I'm talking about the fact that a vertex may, in principle, be pushed to every queue, which should blow up the time from O(n + m) to O(k(n + m)) for k queues. Lines 110 and 120 in your solution (link: http://codeforces.com/contest/843/submission/29769468) Lines 133 and 141 in the solution by malcolm from the comment below (link: https://ideone.com/KnxwBY) 
0
Can we get an Editorial? 
0
Can somebody please help me find out what's wrong with my solution for problem B? 29850486 
0
I had imagined that. Thank you. 
+1

0
Hi! are there any editorials for this round ? 
0
You have to perform up to N "sortings" on subsequences of the array, in a way that every index is sorted exactly once. For example, you could always sort the whole array as a single subsequence but the problem is asking for the maximum number of sortings that we can perform. For example, given the array {3, 5, 4, 1}, we can sort the subsequence of indexes {0, 1, 2, 3} and get the sorted array {1, 3, 4, 5}, but this way we only performed 1 sort. Instead, we could sort subsequence of indexes {0, 1, 3} to get the array {1, 3, 4, 5} and then we could sort the index {2} on his own(as we have to include every index in at least a subsequencesort). This way we perform 2 sortings and have the array sorted at the end of the process. If we sorted the subsequences {0, 3}, {1, 2}, we would've ended up with array {1, 4, 5, 3} which is not sorted so these are not valid subsequences. 
+1
i am not able to see the tutorials (not allowed to view the requested page) please help me! 
0
Hey, The sorting sub sequence question is not clear to me!! Can you please try to explain it to me! Thank you! 
+1
Can anyone kindly explain the questionSorting by Subsequences? 
0
Can anybody please help me in finding out why exactly my submission for DIV2 ProblemD: Interactive Lower Bound is failing on the first testcase itself? Any help is greatly appreciated. Thanks! 
+1
can you explain me what " squared distances " mean. i cant understand that and of course i didnt get the examples that made me very confused in the contest :( 
+3
Got what you wanted to say. I erred, the list was strictly increasing, so no duplicates. Whoch wasbtthe case bugging me. 
+3
Why I can not view the test case anymore? I need to know test case which make me wrong to practice, but it seems to Codeforces has prevented this feature. 
0
Randomly choosing 1999 indices is indeed hopeless — you are only about 4% likely to stumble upon the right value. The idea is to randomly choose K indices, and hope that you land within (1999K) steps of the right one. For a properly chosen K (for example K=1000) the probability of success goes up to 99.999999999%. 
0
If sequence is fixed, then there are tests for which probability to fail 1 and for which it's 0. If we consider tests random, then probability of fail would be almost 0, but tests are not random( they are prepared by authors or hackers) But for correct solutions for each test probability of fail nonzero but small 
0
Yes, I agree. But, the probability of error with a unique sequence is ( almost 0 ) * (# tests) = (almost 0), isn't? 
+4
Why do test cases unseen in these about 2 days? Does this happen only in problems of this contest or the whole CodeForces.com? 
0

0
Div 2 C I was able to think that we need a randomized solution but in no way was I certain that I will reach the correct output. It seems so unlikely, in an array of 50,000 elements, just in 1999 attempts reaching the correct answer. What is the math behind it? 
+12
Where is the editorial? 
0
Thanks mate, It worked :) 
+15
When will the tutorial be ready? 
0
Because without srand(time(0)) the sequence from rand() will be fixed and there's a case against that sequence. 
+12

52
Not a problem, it fits nicely within overall strategy of the contest, to fail expected solutions: B — set limit to 50K, so that normal random_shuffle or rand fails as it returns values up to 30K, set too strict time limit on D, so that vectors or queues will tle, etc. I wonder what surprises did you prepare in other tasks :) 
0
if you add 
0
Maybe the problem is in function pow(). In some situations it's work is strange... It's more safety to use the array pow2[]. 
0
My output: 112589990684259972 Answer: 112589990684259800 Making unsigned didn't change the answer. Still getting wrong answer on test case 18. 
0
I believe you should use "unsigned long long", not "long long int": the answer in test 18 is too big for "long long int". 
0
Problem B div2 I got wrong answer on test case 18.Please help. My_Code 
0
We are working on it now. 
+16
Access not allowed? 
0
Why am I not able to see the tutorials? It says "You are not allowed to see the requested page." 
0

0
can anyone tell me why this exceeds the time limit (on test case 52) in python? this seems to be a frequent issue with python... http://codeforces.com/contest/844/submission/29764117 
0
Hi, I have implemented a solution witch was accepted. However, I receive a wrong answer with the same solution without srand(time(0))! Why does it occur? The probability is almost 0 if we use the algorithm you have explained. I implemented it. Thank you, Rosklin. 
+10
Just make a list with the maximal allowed size (50000) and assuming the solution you are trying to hack checks 1000 random positions defined by srand(time(0)) you can hack all possibilities "seeded" in the spam time(0) to time(0) + 20 by noticing that at most 20000 numbers will be the indexes in this 20 cases, so just put all those 20000 indexes in the first positions of the list. Then put the answer (the lower bound of x) in the last position of the list. In that way all of the 20 tests will get TLE 
+10
The IOI syllabus states that randomized algorithms are "out of focus" (see page 11), which means that
Which I think means that randomized algorithms won't happen because contestants are not required to know that a program that succeeds 99% of time is a correct program. 
0
I understood your answer. It's an outstanding problem! Thank you. 
0
After changing std::rand() to custom rand i got AC but in my "stdlib.h" file i see...
shiiiiiiiiiiiiieeeeeeeeeetttt 
0
There was a test case against random_shuffle(), so not using anything else fails, but AC solution used rand() with random_shuffle(), and there weren't a test case against that. 
0

0
Yep, you're right. Actually, I did the same computations, but just for a second thought that it's preferable to have higher probability (but it's not as that is the probability of failure, which you want to minimize). 
+5
You might need a capacity higher than 1 for the edges on the mincut n = 5, m = 5, s = 1, t = 5 1 2 1, 1 3 1, 2 4 1, 3 4 1, 4 5 1 the answer should be something like 1, 1 1000, 1 1000, 1 1000, 1 1000, 2 2 You don't need to explicitly find the cycles, if you create a reverse edge with infinite capacity for edges with gi == 1 you do the same thing. 
+26
999 is the best choice, look here: 29776215 
+9
MinGW and its quirks strike again. Using std::random_device seems to be fine on Linux and MSVC but in MinGW it surpisingly results in fixed seed. If we're stuck on Windows I would like at least an option to compile with MSVC2017 which I'm doing locally anyway. 
+10
The time limit has been made strict to fail fast solutions which use Dijkstra every time to recalculate the distances. Our main solution runs in 4.04.5 seconds on all our tests. We were aware that handmade "lists on arrays" worked faster than vectors. However, we had AC solution written fully in vectors that worked ~6.5 seconds. We are extremely sorry for the guys who wrote correct solutions and could not optimise it to get AC. :( 
+4

0
Actually, std::sort shouldn't be quicksort but an nlogn variant called intro sort which uses median of medians algorithm for choosing pivots after O(logn) standard quicksort iterations 
0
Where is the editorial? 
0
okay I am wrong they are 100% ok : 
0
Yes. In the implementation I use exactly this. 
+19
O_O Yes. There's bug there, but another one =) We don't need 
0
Check this. 
0
Sad! AC after changing queue to static array. :( 
+29
Look like I've found my true rating 
+1
I think IOI is not against randomized algorithms per se, but against programs that may generate different output when run multiple times  If there was a program that generated correct output 1/4 of the time, does it count as an AC? I believe you can still use srand and things in IOI, but you must seed them deterministically. For codeforces, such behaviour is tantamount to asking to be hacked. So allowing timebased seeds makes sense. 
0
I believe that the key is to note that any edge contained in a (flow) cycle cannot be saturated in a maxflow. (Intuitively, if we have capacity to waste on making flow go circles, you cannot be the bottleneck). Finding edges contained in a cycle is easy, especially since m<=1000. So we forcefully remove such edges from our bottleneck consideration by setting them to capacity 1000. Now we find the mincut of the resulting graph (with all other edges weight 1). For any one such mincut, we set those capacities to be 1 and all other capacities to be 1000 for the output. Did I miss other details? 
0
The order of transformation matters since you are deleting edges (and parent/children relationships in the subtree flip really often). If my logic doesn't fail me, the way to solve this question is: For each subtree of the centroid(s), transform such that a node is adjacent to all other nodes in the subtree and is connected to the root. This gives distance 2 between all other nodes and the centroid. This also can be done in 2n operations. 
0
No, such a thing doesn't exist (assuming antagonistic test case)  The main idea is that if you query for 1000 times, you may get results from the smallest 2000 numbers, and if x is among the largest 5000 numbers, this gives you no information about the larger part of the linked list at all. So even deterministic solutions that pass systests are probably just "unpredictable" enough to pass off as random. 
0
just change cnt to long double it will work 
+89
Quite unfair in Div1 B It's guaranteed in the problem that the data is prepared already, so any random seed could pass the system test. But one can hacks the other by choosing the exactly same seed to generate data. It is the BIGGEST problem which cause the hack (also the problem) to be meaningless. Many(a big number) code passed the system test could be hacked this way and Many code which was hacked could pass the system test. It's a conflict between interactive problem and hack. Me: "My algorithm has 99.9999% possibility to get accepted." Hacker: "Your algorithm has 0.0001% possibility to get UNaccepted. Let me try your random seed and see." Spend my whole night on it (also the RAND_MAX problem). Feeling tired about it. Sad. 
0
Please Help! Why is http://codeforces.com/contest/844/submission/29765292 "Accepted" But http://codeforces.com/contest/844/submission/29765519 is "Wrong Answer". Thanks In Advanced. 
0
There was a deterministic solution in my room, so I deciphered exactly where it would probe and then arranged a custom hack that would exhaust the queries and still keep the solution out of reach. +100 points, thank you. 
0
You are initializing the random number generator with time. It's not really a mystery that it could behave differently on different runs. I suppose that if you submit the same code a few times without changing compiler or conditions order you will also get some AC and some WA. 
0
I just used long double instead and round() for the division and the problem was accepted :) :) 
0
Could you help me with the question Div2. D? I think we must send the index of the desired element. So, the probability is 2000/50000. Why not? Thank you, Rosklin. 
0
I think that we must send the index of the desired element. So, the probability is 2000/50000, isn't? Thank you. 
+51
How to lose 8th place? Not handle the first element in [B] at all while everyone struggling with randoms =) AlexDmitriev, kostroma, zeliboba and all other guys — I love your contests. They are hard, interesting and pretty much fun (even when everyone struggling with randoms). That's how it should be done. Thanks! 
0
Thank you :) 
0
Formula for calculating number of subsets without including empty set is: (2^n)1. 
0
Can anyone explain why one the solutions get AC and another doesn't. I don't understand because I just changed order of the conditions in the second while http://codeforces.com/contest/844/submission/29762117 AC http://codeforces.com/contest/844/submission/29762065 WA this screenshot shows the difference between the solutions but WA code under C++14 gets AC under C++11 http://codeforces.com/contest/844/submission/29762789 And code that I sent on contest and got WA under C++14 now gets AC under C++11 http://codeforces.com/contest/844/submission/29758399 WA from contest C++14 http://codeforces.com/contest/844/submission/29763381 AC C++11 
+5
you may say that upper bound is not n but number of changed edges (it's a bit less number when summed over all queries) 
+25
BTW, it looks like a bug, that you don't do 
0
I got WA on 18 even though I used long in Java. But I used Math.pow() which I think has rounding error 
8
Captain Obvious, need your help! 
0
:( :( :( :( any one else failed the test 18 div2 B for overflow : : anyway,, this round was nice but problem Ddiv2 was a bit surprising actually 
0
I got WA DIV2D final test22, because I was type 20000 (20 thousands) instead of 2000. There are very weak pretests. 
Created or updated the text 
+18
you've just made your dream come true 
0
Can someone please tell me why I'm getting WA. http://codeforces.com/contest/844/submission/29761165 
+17
Well, why not. Each deterministic solution has countertests. For 2x and 5x variations, no one saw them during the contest, so their killer tests were not entered. The 1x variation was common though. 
+213
I can't believe my performance of today, is this a dream? 
+3
FML >_< 
+24
Hell, I feel lucky today. It seems like I am one of few guys who used srand(kSeed) in div1B and just didn't meet any hackers in my room. 
+1
Because 
+3

0
Thanks, I'll have to look it up 
0
okay, but can you explain why ? 
+1
Math.pow() returns a double so it may have something to do with the fact that you are subtracting 1 (which may be interpreted as a 32bit int) from a double. As a tip, whenever you need to calculate 2 ^ p, I would just do (1L << p). 
0
http://codeforces.com/contest/844/submission/29744761 Look that submission. It get Wrong answer on test 1 [main tests]. It is mistake. 
+1
Try 
0
What is the best time for a "wrong" solution vs a "correct" solution? 
+1
Use (1<<x) to get the xth power of 2 :) 
0
No. Algorithm is called inplace merge sort. I have never implemented it, but I remember it was described in one of the Knuth's volume. 
0
if i cast the result of 
0
isn't it nlog^2n ? 
+5
Also it could use another fixed seed. 
Name 
