Hello Codeforces!
I'm glad to announce that on Sep/19/2017 15:05 UTC Codeforces Round #435 for the second division will take place. As usual, First division participants can take part out of competition.
This round was prepared by me.
I'd like to thank mohammedehab2002 for writing the statements and the editorials and testing the round, Livace,Alladdin,300iq and cdkrot for testing the round, vintage_Vlad_Makeev for helping us in contest preparation, translating the statements into Russian and making one of the problems more interesting, KAN and Ahmad_Elsagheer for giving their opinions and thoughts about the problems and MikeMirzayanov for the great Codeforces and Polygon platforms.
You will be given 6 problems and 2 hours to solve them.
The scoring distribution will be announced later.
UPD. 500-1000-1500-1750-2000-2750
**UPD Congratulations to the winners:
Div1+Div2:
1-Shik
5-scanhex
Div2:
2-scanhex
5-NickR
UPD editorial
Cool.
Hope there wont be too long In Queue submissions...Fix this..its ruining CF...
You should have post this announcement after today's QF Quals mirror is finished.
Is it ....emmmmm geometrical?
please end... contests had be unrated for many times.
Is it rated?
I hope so.
we should do it seriously no matter whether it is rated You will not know whether it is rated until the contest ends :)
Pls do something about the long queues. Yesterday's contest was just an example of it but in practice also these days the subs take too much time to judge.
Mike told that it was his mistake and there was no internal fault(that's what I understood from his explanation :) sorry if I am wrong). Yes many times while practicing there are situations of LONGGGG queues... Anyways hope it will be a good RATED round :)
is it rated?
hope this time in the questions the fullstops and multiplication signs will be different! last time they used '.' for both and it made the question A look way complicated XD lol!
Do you mean you can't distinguish this: "·" from this: "."?
even if it was that it is still confusing right? :p XD lol.
Gl & Hf to everyone!
The queue problem isn't going away. Even in yesterday's NEERC Subregional, the queue was too long and it affected the contest. When you submit a code, and you get a WA after 7-8 minutes, it doesn't feel good. In a contest, every second counts. Also, you can't concentrate properly on another problem even if you want to while waiting for a queued verdict. It's frustrating. I hope this doesn't occur in today's round. If it does, then it'd be really disheartening. CF is the best, we want it to remain the same way.
Is it mathematical?
he is also the author of this round. so maybe you can try it to find out?
In fact, Most of the problems in round #396 are mine while most of the problems in this round are his .
Hope the server will work effiently
My first contest in CODEFORCES is Round 396 which is conducted by you and I am very happy that again I am participating in your contest.
Thank you.
why the last contest was unrated?
Technical reasons
Score Distribution ? Not Declared Yet , 1 & Half Hour Left
already one
Auto comment: topic has been updated by mahmoudbadawy (previous revision, new revision, compare).
if repeted problem sucks
Scala support is completely broken and couple of users reported it for a while. See: http://codeforces.net/blog/entry/54283 http://codeforces.net/blog/entry/54245
I also messaged the admins about it and its still not fixed :(
Hope someone from CodeForces notices this!
I think it is fixed now.
Thank you MikeMirzayanov — I verified it works now!! If it is possible, can you reset my ratings to before the past couple of contests? All my Scala solutions failed during contest due to this bug (I verified they would have passed tests otherwise now).
Am I the only one that gets stuck on infinite loading when trying to submit? Have been trying to submit C for 15 min already with no success.
maybe the problem is with your computer
or internet
Yeah it turned out to be the wifi, I did the rest of the contest connected to my phone's hotspot.
How to solve B ?
Count the number of nodes in the odd levels of the tree (first set) and count the number of nodes in the even levels of the tree (second set). Then multiply both of them and subtract the edges that are already exist.
I can`t understand why the following code gives wrong answer
It might be because of overflows. Change int to long long may be.
here's my solution.Maybe it's make sense.first,we can mark every nodes with zero or one following the the rules of Bipartite Graph,and we can figure out how many ones and zeros, and the result is the count of zeros times ones' ,at last,we should minus the loops.
can someone help me figure out why my solution gives tle? I used a random algorithm, the expected running time should be small and it runs fast in my computer. I cant pass pretest 6.
Same here. Try test: 2 0
Hi, gives no in 0.003 seconds.
Maybe RAND_MAX is 32767?
Yes, that was it! Thanks a lot. Its good I learned this while not actually participating. In my computer MAX_RAND is way bigger so it worked fine.
So in general it would be wise to first take the residues mod 32767? and then use them? In case RAND_MAX is bigger, so you dont get overflow
To get around it you could go
(rand()<<15)|rand()
Hello, thanks for the comment, can you explain the logic behind this when RAND_MAX is 2^31-1?
Well, the whole point of using this is that Codeforces is run on Windows servers, which means that RAND_MAX is in fact 2^15-1, so this of course combines two random numbers to get one that is ~2^30. If you were using a *nix system then there would be no need for the bit shift, however if you did, then it would overflow. It's probably safer then to have an if statement along the lines of
Oh, I understand. That safe solution makes a lot of sense, Ill do that from now on, thanks for the help. fare well and prosper.
How to solve C? Good problem in my opinion
I did this : if n <= 4 then you can just brute force, also in 2 0 case answer is NO, else i just find xor of all numbers from 1 to n — 2, the you just have to find two numbers, such that their xor is equal to (xor from 1 to n — 2) ^ x. Also, if (xor from 1 to n — 2) ^ x is 0, I delete n — 2 and add 0 to answer, so I find two numbers, such that their xor is equal to (xor from 1 to n — 3) ^ x
NO only if the case is 2 0.
if n>=2 then let the first number be 2^18. Then keep filling numbers starting from 1, incrementing by 1 or 2[by 2 if the xor so far turns out to be 2^18], till there's one number left to be filled. The last number = xor(xor so far, x).
UPD: failed systests :(
When n ≥ 3, define ak = k for k = 0, ..., n - 3. Calculate p = x^0^1^...^(n - 3). Then define an - 2 = 218 and an - 1 = 218 + p or similar. This will guarantee that there are no two identical numbers in the sequence ai and all elements are smaller than 219 - 1 < 106
You failed systest because p can be zero right?
Actually, no. I forgot the case n = 2 and x = 0. I took care of the case p = 0 by redefining a0 = 219 - 1, an - 2 = 3 × 217, an - 1 = 217 - 1. I considered that corner case, and yet forgot abound n = 2 and x = 0. Forgot to mention this in the original comment.
Most recent submission : 30524864
Submission during contest : 30508844
Only difference is the case n = 2.
n — 2 random numbers and then generate last two.
stupid (n == 2 && x == 0) if :(
Nice problems, how to solve C?
I had an idea that if a is odd number then aXOR(a + 1)XOR(a + 2)XOR(a + 3) = a - 1, so we generate first 4 * k numbers and find remaining ones with some bruteforce.
I used the same but when a is even a^(a+1)^(a+2)^(a+3)=0
My problem was NO case :(
OK, I couldn't debug my solution during contest ( cause of stupid Wi-Fi problems) but I did now and it got AC, I will try to explain it:
We have 2 cases that we need to deal with:
1) N is odd
2) N is even
Let P be a power of 2 > 1e5. And in every case we will use an auxiliary array "numbers" which has n numbers such that not one of them is x.
Case 1 solution: let the first n-1 numbers be ans[i] = P + numbers[i] and their xor be _xor. our last number will be ans[n]=xor ^ _xor
Case 2 solution: let the first n-2 numbers be ans[i] = P + numbers[i] and their xor be _xor. If _xor = x, we will just change one of ans[i] to be a diffrent and number and ans[n-1] = _xor ans[n] = x;
here is a countercase for your claim.
3, 4, 5, 6
by your claim, answer is 2 but correct answer is 4.Can answer be "NO" in C except 2 0 case?
6 0
10 0
n%4==2 0
0 1 2 262147 4 262148
Oh with this case I expect lots of people will be failing. I myself got hacked.
6 0
doesn't it work?
My program gives 1 2 3 4 8 12 to 6 0 and i think its correct
1 2 4 8 16 31
satisfies 6 0 case
YES 29637 1088 18455 13546 1 2937
For 6, 0 my code prints:
781959 11593 584443 901753 630736 488604
Which when xor'ed gives 0. Am I missing something?
Now i don't have to wait System testing, C is WA :(
How to solve D?
Binary search. Even tho I expect that my code runs in an infinite loop for some cases.
Use srand(time(0)) and rand() to generate 15 different integers in range 1 to n. Then Check By Changing the position of a string of n '0'es . Then Print The Answer.
What's probability of finding correct answer in your solution?
And Don't lie that you didn't try to send random solve for C.
Will the random solution pass for problem C? (If not, how to hack it?)
my solution is random solution , but i can not prove its time complexity.
Yes, random solution works.
I randomly pick up (n — 1) different numbers from 0 to 524287 , calculate there xor sum S, then check if S xor x is used. if not, then these (n — 1) numbers and S xor x together is a solution (S xor x < 524288, obviously); if so, then make another try. Since there are plenty of numbers to choose, the probability to success is about 90% percent, maybe higher (I test n = 100000 several times, and they all succeed at the first attempt). So, if you tried many many times, (say, 100 times) and failed, then you can assume this is impossible and print "NO".
I passed system test, used 46ms/2100Kb, it works.
Can anyone say this code bug?(Div 2/c)
It does not print "YES" neither "NO" You should print "NO" iff N=2, X=0
tank you.
I wanna cry, it was 5 seconds left before I press submit and it tells me contest is over((( Pretty sure the code i was about to submit was correct
Same here hhh. I just adds "stdout.flush()" 5 seconds before it ends.
For problem E, I have O(N + M + (M — N) log (M — N) + Q log (M — N)). Is that right?
Here is a solution to F:
First of there is a basic observations which is important for the solution.
Now lets use ai as lcp(i, i + 1) ( ai = lcp(i, i + 1) ).
The problem becomes:
We have an array ai. We have queries for finding the maximum value of min(ai, ai + 1, ..., aj - 1) * (j - i + 1) for some i and j in a given range. We also have a query for updating a value at a given position.
We also have some additional constraints. There are at most different values ai — it's easy to prove.
So the main idea is to store different segment trees (for every value of ai). In the segment tree for a value X we will consider only elements with values ≥ X. For simplicity let's assume that in the segment tree all positions with value ≥ X are set to 1 and all other to 0. Then if we want to find the maximum length of an interval [i;j] inside our query interval such that min(ai, ai + 1, ..., aj - 1) > = X we can simply find the length of the longest interval in the segment tree for X with all elements equal to 1.
Then the query can be done by considering every segment tree, doing query for each of them and then getting max X * TX.query(l, r).
The update can be done by simply preforming at most updates in segment trees.
The only problem with this solution is the memory. It will consume memory. Fortunately we can use a persistent segment tree instead of a regular one and this way the memory will be .
PS: I was to lazy to write it during the contest, but is should pass.
That is so brutal! I hope there is a nicer solution!
Wow. ._. I thought of this solution as well, but didn't code it cause I was sure it would get TLE >_<
ignore*
found my mistake in div2c
Solution must print value <= 1000000
How 2 solve D ? I do not even understand why there is mention of fflush
fflush
is to let the system know that you have print something so it can response to it. (Or under normal condition all the outputs are sent together at the end to save time.)Does it mean that the input and output of this question are interactive? I first encountered this type of problem.So I need to design the query sequence?
Yes, you may decide what the next query will be based on what you have received.
So fast system testing
System Testing Pending
Refresh Page after 10min
79% done
This times system testing is running at speed of thunder lmao :D
upvote for the very quick testing
![ ](
image upload
)
I could succeed to hack one's code ,if the website can run faster ,and my rank will be rise 200 and more!!! why my hack in the last minute can't do it's proper work?
By the way, how to solve the f**k problem C?
Easy solution for C. if n<3, brute force. otherwise, xor first n-3 numbers,say res.(res = 0^1^...^(n-4)) Then 0,1,...,(n-4),(1<<18),(1<<19),((1<<18)+(1<<19))^(x^res) is answer.
I just randomly picked all but one numbers and force the last number to fit the requirement.
No math here, great!
You are lucky, your algorithm is incorrect. What if e.g. n=4 x=0 and your random pick is [1, 2, 3]?
Read the question carefully, 0 is allowed so just 0 xor 1 xor 2 xor 3 = 0
Although the last number did have a collision, I would throw everything away and restart for another try. If it always failed ( say, failed 100 times or so), It could be pretty sure that this was impossible and should print "NO". It's the same as what Miller-Rubbin primality test do.
You are right about reading carefully, the example should have been n=4 x=1 with [1, 2, 3]. In your original message you didn't mention trying '100 times or so'. You'd have to be very unlucky indeed.
Easy solution for problem C : https://ideone.com/FZ6rfw
C with x=0 really made the problem trickier.
C with n=2 and x=0 made my solution wrong :|
UPD: fortunately, I have some other bug :P
vintage_Vlad_Makeev, KAN, MikeMirzayanov, I have accidentally sent the same hack twice (the page did not reload and I sent it from a new tab). Now I have two unsuccessful attempts. Can it be fixed?
Removed one of the attempts.
Thanks.
Looks like I'm finally going to div.1! I'm so happy, it was quite a long journey :)
Hello, actually my wrong solution for problem D passed main tests. Here is my solution — http://codeforces.net/contest/862/submission/30518750 and it runs into an infinite loop in the following case : "10"
"10" is test case #121 (last), and seems your solution works on it.
Thanks for the good news. Idk how its working but on my machine its not running. Just felt that in case the main tests were wrong, I should have informed.
Now my C solution failed for the stupidest reason, I forgot to print YES before the answer itself in one of the cases. Why is output so poorly formatted anyway? Isn't it the tradition of problem setting to print -1 when there is no solution?
Somehow I managed to accumulate more downvotes than "is it rated" comments :D
Auto comment: topic has been updated by mahmoudbadawy (previous revision, new revision, compare).
After 17 fails and 1:49 my submission for D passed, but it failed again on 59th test. The worst feeling ever
nice problems, c is interesting for me and random_shuffle() solution hhe
How can one proove that random brute solution for C will not time-out ?
please don't make other rounds
can anyone please help me! This is my solution can someone please tell why is it a run time error one the codeforces compiler? it works in my system and had passed all the testcases! but then it gave a run time error?? thank you!
At this statement
if(fans[sizea]==0)
you might be getting a runtime error as size of fans is sizea.Does anyone knows what exactly compiler version and flags are used when you choose GNU C++11? I have a trouble with my solution http://codeforces.net/contest/862/submission/30520451. On my computer it answers 0 on first test using GCC 5.4.0, and on my friend's computer it returns the same answer using GCC 4.8. But test system thinks that answer is -273605408. What the problem?
dude i guess they use something quite different because i had the same kind of issue! i ran your code in my computer and it gives 0. i guess codeforces has totally different compiler and flags. its just bad luck that we dont have their compiler version.
May be we should ask admins about it? I have too few rating points to loose it that way :c
Dude I asked KAN and he said it had nothing to do with compiler, actually I tried accessing memory that wasn't allotted so in that case it works sometimes and sometimes it doesn't! I guess something similar in your case too! Maybe but if you think there is still a problem you should approach. :)
Well, then i should check my code again.
http://codeforces.net/blog/entry/79
Thank you.
Here
max_l
can equaln
and also you accesspref_l[1]
which might not exist ifn
is 1.Thank you.
Can someone give me some links to good random algorithms tutorial. I see a lot of people used it to solve C.
i have got 237 point int this round keep doing well mahmoudbadawy thank you so much for this round and problem :)
for problem C you can just select first n-1 elements randomly (from 0 to 2^19-1) and see if the number that you need to get the desired xor is available. try it 100 times, if none of those 100 times works then print NO. this works because the probability the nth number will be available is approximately 1/5 so the probability you get it wrong is 1/5^100. Of course this is just a heuristic, you need some sort of uniformity argument but w/e.
thats because 2^19-1 is approximately 5*10^5, so at least four fifths of the numbers are unnocupied.
Wow, I used exatly the same algorithm here, same range and also tried 100 times.
did it work? I had to fix one little thing, I used srand and rand(). You need a small modification because rand only goes up to 2^15-1.
Yes, I made a little function to do that. int randInt(){return (rand() * RAND_MAX + rand()) % 524288;}
Could you please elaborate a bit more on the 1/5 probability? Specially when we don't know the number of solutions. Also why (from 0 to 2^19-1) and not [0, 10^6]? Thanks!
In the worst case ( n = 100000 ), we have 524288 numbers ([0, 524287]) to choose and 99999 numbers used. The last number y to choose, which is the xor sum of these 99999 numbers and the given x, has a probability 99999 / 524288 to bump into another used number. That's about 1/5 probability to fail.(note that y and x is one-to-one corresponding, so all these numbers have equal probability)
And why we are not using [0, 10^6]? Let's take a smaller situation to think about. Say, the number limitation is 10, would you be ok to randomly pick up numbers from [0, 10]? For example, if you picked up 8 and 7, and 8 xor 7 is (1000)2 xor (0111) 2 = (1111)2 = 15, which is above the limitation. However, if you only choose number from [0, 7], then the forth binary digit will always be 0, so ther xor sum will be smaller than 8, of course smaller than 10.
So that's what happening here, everything here will be less than 524288, since the 20th binary digit is always 0. There's no need to expand the range to 1000000.