Recent actions
On zelibobaAIM Tech Round 4, 3 weeks ago
0

Stay tune for daily DJ MixerMix blog

On zelibobaAIM Tech Round 4, 3 weeks ago
0

Can we get an Editorial?

On zelibobaAIM Tech Round 4, 3 weeks ago
0

Can somebody please help me find out what's wrong with my solution for problem B? 29850486

On zelibobaAIM Tech Round 4, 3 weeks ago
0

I had imagined that. Thank you.

On zelibobaAIM Tech Round 4, 3 weeks ago
+1
On zelibobaAIM Tech Round 4, 3 weeks ago
0

Hi! are there any editorials for this round ?

On zelibobaAIM Tech Round 4, 3 weeks ago
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 subsequence-sort). 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.

On zelibobaAIM Tech Round 4, 3 weeks ago
+1

i am not able to see the tutorials (not allowed to view the requested page) please help me!

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Hey, The sorting sub sequence question is not clear to me!! Can you please try to explain it to me!

Thank you!

On zelibobaAIM Tech Round 4, 4 weeks ago
+1

Can anyone kindly explain the question-Sorting by Subsequences?

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Can anybody please help me in finding out why exactly my submission for DIV-2 Problem-D: Interactive Lower Bound is failing on the first test-case itself? Any help is greatly appreciated. Thanks!

On zelibobaAIM Tech Round 4, 4 weeks ago
+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 :(

On zelibobaAIM Tech Round 4, 4 weeks ago
+3

Got what you wanted to say. I erred, the list was strictly increasing, so no duplicates. Whoch wasbtthe case bugging me.

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.

On zelibobaAIM Tech Round 4, 4 weeks ago
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 (1999-K) steps of the right one. For a properly chosen K (for example K=1000) the probability of success goes up to 99.999999999%.

On zelibobaAIM Tech Round 4, 4 weeks ago
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

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Yes, I agree. But, the probability of error with a unique sequence is ( almost 0 ) * (# tests) = (almost 0), isn't?

On zelibobaAIM Tech Round 4, 4 weeks ago
+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?

On zelibobaAIM Tech Round 4, 4 weeks ago
0
#if RAND_MAX <= 32768
#define rand() ((rand()<<15)+rand())
#endif
On zelibobaAIM Tech Round 4, 4 weeks ago
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?

On zelibobaAIM Tech Round 4, 4 weeks ago
+12

Where is the editorial?

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Thanks mate, It worked :-)

On zelibobaAIM Tech Round 4, 4 weeks ago
+15

When will the tutorial be ready?

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Because without srand(time(0)) the sequence from rand() will be fixed and there's a case against that sequence.

On zelibobaAIM Tech Round 4, 4 weeks ago
+12

On zelibobaAIM Tech Round 4, 4 weeks ago
-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 :)

On zelibobaAIM Tech Round 4, 4 weeks ago
0

if you add (long long) before your pow calls, it works

On zelibobaAIM Tech Round 4, 4 weeks ago
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[].

On zelibobaAIM Tech Round 4, 4 weeks ago
0

My output:- 112589990684259972 Answer:- 112589990684259800 Making unsigned didn't change the answer. Still getting wrong answer on test case 18.

On zelibobaAIM Tech Round 4, 4 weeks ago
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".

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Problem B div2 I got wrong answer on test case 18.Please help. My_Code

On zelibobaAIM Tech Round 4, 4 weeks ago
0

We are working on it now.

On zelibobaAIM Tech Round 4, 4 weeks ago
+16

Access not allowed?

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Why am I not able to see the tutorials? It says "You are not allowed to see the requested page."

On zelibobaAIM Tech Round 4, 4 weeks ago
0

rand()/double(RAND_MAX)*n passed. see 29761972

On zelibobaAIM Tech Round 4, 4 weeks ago
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

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
+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

On zelibobaAIM Tech Round 4, 4 weeks ago
+10

The IOI syllabus states that randomized algorithms are "out of focus" (see page 11), which means that

Contestants are not expected to have knowledge of these topics. Most competition tasks will not be related to any topics from this category.

However, this does not prevent the inclusion of a competition task that is related to a particular topic from this category. The ISC may wish to include such a competition task in order to broaden the scope of the IOI.

If such a task is considered for the IOI, the ISC will make sure that the task can reasonably be solved without prior knowledge of the particular topic, and that the task can be stated in terms of [required] concepts in a precise, concise, and clear way.

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.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

I understood your answer. It's an outstanding problem! Thank you.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

After changing std::rand() to custom rand i got AC

but in my "stdlib.h" file i see...

/* The largest number rand will return (same as INT_MAX).  */
#define	RAND_MAX	2147483647

shiiiiiiiiiiiiieeeeeeeeeetttt

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Can anyone explain why one the solutions get AC and another doesn't? Div1B AC WA6

On zelibobaAIM Tech Round 4, 4 weeks ago
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).

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.

On zelibobaAIM Tech Round 4, 4 weeks ago
+26

999 is the best choice, look here: 29776215

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.0-4.5 seconds on all our tests.

Solution

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

On zelibobaAIM Tech Round 4, 4 weeks ago
+4
On zelibobaAIM Tech Round 4, 4 weeks ago
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

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Where is the editorial?

On zelibobaAIM Tech Round 4, 4 weeks ago
0

okay I am wrong they are 100% ok :|||

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Yes. In the implementation I use exactly this.

On zelibobaAIM Tech Round 4, 4 weeks ago
+19

O_O

Yes. There's bug there, but another one =) We don't need bfs() there, it was part of debug. After commenting this line OK in 3.962 sec.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Check this.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Sad! AC after changing queue to static array. :(

On zelibobaAIM Tech Round 4, 4 weeks ago
+29

Look like I've found my true rating

On zelibobaAIM Tech Round 4, 4 weeks ago
+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 time-based seeds makes sense.

On zelibobaAIM Tech Round 4, 4 weeks ago
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?

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

just change cnt to long double it will work

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

I just used long double instead and round() for the division and the problem was accepted :) :)

On zelibobaAIM Tech Round 4, 4 weeks ago
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.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

I think that we must send the index of the desired element. So, the probability is 2000/50000, isn't? Thank you.

On zelibobaAIM Tech Round 4, 4 weeks ago
+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!

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Thank you :)

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Formula for calculating number of subsets without including empty set is: (2^n)-1.

On zelibobaAIM Tech Round 4, 4 weeks ago
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

On zelibobaAIM Tech Round 4, 4 weeks ago
+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)

On zelibobaAIM Tech Round 4, 4 weeks ago
+25

BTW, it looks like a bug, that you don't do k = 0 after bfs() in update query. With k = 0 your code works 10% faster.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

I got WA on 18 even though I used long in Java. But I used Math.pow() which I think has rounding error

On zelibobaAIM Tech Round 4, 4 weeks ago
-8

Captain Obvious, need your help!

On zelibobaAIM Tech Round 4, 4 weeks ago
0

:( :( :( :(

any one else failed the test 18 div2 B for overflow :| :|

anyway,, this round was nice but problem D-div2 was a bit surprising actually

On zelibobaAIM Tech Round 4, 4 weeks ago
0

I got WA DIV2-D final test-22, because I was type 20000 (20 thousands) instead of 2000. There are very weak pre-tests.

On zelibobaAIM Tech Round 4, 4 weeks ago
Created or updated the text
On zelibobaAIM Tech Round 4, 4 weeks ago
+18

you've just made your dream come true

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Can someone please tell me why I'm getting WA. http://codeforces.com/contest/844/submission/29761165

On zelibobaAIM Tech Round 4, 4 weeks ago
+17

Well, why not. Each deterministic solution has counter-tests. 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.

On zelibobaAIM Tech Round 4, 4 weeks ago
+213

I can't believe my performance of today, is this a dream?

On zelibobaAIM Tech Round 4, 4 weeks ago
+3

FML >_<

On zelibobaAIM Tech Round 4, 4 weeks ago
+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.

On zelibobaAIM Tech Round 4, 4 weeks ago
+1

Because (long) += (double) operator truncate data and compiler didn't say about it!
l:long += d:double works like l = (long)(l + d) so you lose precision since l + d not power of two.

On zelibobaAIM Tech Round 4, 4 weeks ago
+3

Using random_shuffle more than once seems to work:
1x : 29761406
2x : 29761568
5x : 29761106

On zelibobaAIM Tech Round 4, 4 weeks ago
0

Thanks, I'll have to look it up

On zelibobaAIM Tech Round 4, 4 weeks ago
0

okay, but can you explain why
Math.pow(2, white) - 1 this gets WA, but
(long) Math.pow(2, white) - 1 this gets AC

?

On zelibobaAIM Tech Round 4, 4 weeks ago
+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 32-bit int) from a double. As a tip, whenever you need to calculate 2 ^ p, I would just do (1L << p).

On zelibobaAIM Tech Round 4, 4 weeks ago
0

http://codeforces.com/contest/844/submission/29744761

Look that submission. It get Wrong answer on test 1 [main tests]. It is mistake.

On zelibobaAIM Tech Round 4, 4 weeks ago
+1

Try 1L << p.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

What is the best time for a "wrong" solution vs a "correct" solution?

On zelibobaAIM Tech Round 4, 4 weeks ago
+1

Use (1<<x) to get the x-th power of 2 :)

On zelibobaAIM Tech Round 4, 4 weeks ago
0

No. Algorithm is called in-place merge sort. I have never implemented it, but I remember it was described in one of the Knuth's volume.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

if i cast the result of (long)Math.pow() then it works =/

On zelibobaAIM Tech Round 4, 4 weeks ago
0

isn't it nlog^2n ?

On zelibobaAIM Tech Round 4, 4 weeks ago
+5

Also it could use another fixed seed.

On zelibobaAIM Tech Round 4, 4 weeks ago
0

There is merge sort which uses O(1) additional memory.