By mahmoudbadawy, history, 12 months ago, ,

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,gainullin.ildar and cdkrot for testing the round, gritukan 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

2-NiroBC

5-scanhex

Div2:

1-NiroBC

2-scanhex

5-NickR

UPD editorial

•
• +353
•

 » 12 months ago, # |   -20 Cool.
 » 12 months ago, # |   +44 Hope there wont be too long In Queue submissions...Fix this..its ruining CF...
 » 12 months ago, # |   -60 You should have post this announcement after today's QF Quals mirror is finished.
 » 12 months ago, # |   -97 Great announcement thank you so much for this. by All Health Post
 » 12 months ago, # |   +27 Is it ....emmmmm　geometrical?
 » 12 months ago, # |   +14 please end... contests had be unrated for many times.
 » 12 months ago, # |   -48 Is it rated?
•  » » 12 months ago, # ^ |   -23 Of Course It Is
•  » » 12 months ago, # ^ |   +15 I hope so.
•  » » 12 months ago, # ^ |   -37 Of Course it is not.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 we should do it seriously no matter whether it is rated You will not know whether it is rated until the contest ends :)
 » 12 months ago, # |   -27 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.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +14 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 :)
 » 12 months ago, # |   -28
 » 12 months ago, # |   -54 is it rated?
•  » » 12 months ago, # ^ |   -31
 » 12 months ago, # |   0 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!
•  » » 12 months ago, # ^ |   +5 Do you mean you can't distinguish this: "·" from this: "."?
•  » » » 12 months ago, # ^ |   +5 even if it was that it is still confusing right? :p XD lol.
 » 12 months ago, # |   -15 Thank You very much for sharing this
 » 12 months ago, # |   -15 Gl & Hf to everyone!
 » 12 months ago, # |   +53 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.
 » 12 months ago, # |   0 Is it mathematical?
•  » » 12 months ago, # ^ |   +10 he is also the author of this round. so maybe you can try it to find out?
•  » » » 12 months ago, # ^ |   +23 In fact, Most of the problems in round #396 are mine while most of the problems in this round are his .
 » 12 months ago, # |   0 still long queue,please fix it asap.
 » 12 months ago, # |   -11 cool
 » 12 months ago, # |   +2 Hope the server will work effiently
 » 12 months ago, # | ← Rev. 2 →   +16 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.
 » 12 months ago, # |   -16 why the last contest was unrated?
•  » » 12 months ago, # ^ |   0 Technical reasons
 » 12 months ago, # |   0 Score Distribution ? Not Declared Yet , 1 & Half Hour Left
•  » » 12 months ago, # ^ |   0 already one
 » 12 months ago, # |   0 Auto comment: topic has been updated by mahmoudbadawy (previous revision, new revision, compare).
 » 12 months ago, # |   -20 if repeted problem sucks
 » 12 months ago, # |   0 Scala support is completely broken and couple of users reported it for a while. See: http://codeforces.com/blog/entry/54283 http://codeforces.com/blog/entry/54245I also messaged the admins about it and its still not fixed :(Hope someone from CodeForces notices this!
•  » » 12 months ago, # ^ |   +3 I think it is fixed now.
•  » » » 12 months ago, # ^ |   +21 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).
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 maybe the problem is with your computer
•  » » » 12 months ago, # ^ |   0 or internet
•  » » » » 12 months ago, # ^ |   0 Yeah it turned out to be the wifi, I did the rest of the contest connected to my phone's hotspot.
 » 12 months ago, # |   -12 boring mex, xor & binaries, supposed to have more fun ((
 » 12 months ago, # |   0 How to solve B ?
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 this solution came to my mind when time left was 4 minutes :( sadly i got errors and when i fixed them time left was 11 seconds. I clicked submit and copied the code and pasted. And then the contest over notification arrived. Sad but true :(
•  » » » 12 months ago, # ^ |   0 I cant understand why the following code gives wrong answer int one = 0; queue q; q.push(1); v[1] = true; while(!q.empty()) { int u = q.front(); q.pop(); if(v[u]) { one++; } vector::iterator iter; for(iter = e[u].begin(); iter != e[u].end(); iter++) { v[*iter] = !v[u]; q.push(*iter); } } int count = (one * (n-one)) - (n-1); 
•  » » » » 12 months ago, # ^ |   +1 It might be because of overflows. Change int to long long may be.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
 » 12 months ago, # | ← Rev. 2 →   +3 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.
•  » » 12 months ago, # ^ |   0 Same here. Try test: 2 0
•  » » » 12 months ago, # ^ |   0 Hi, gives no in 0.003 seconds.
•  » » 12 months ago, # ^ |   +5 Maybe RAND_MAX is 32767?
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 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
•  » » » » » 12 months ago, # ^ |   +3 To get around it you could go (rand()<<15)|rand()
•  » » » » » » 12 months ago, # ^ |   0 Hello, thanks for the comment, can you explain the logic behind this when RAND_MAX is 2^31-1?
•  » » » » » » » 12 months ago, # ^ |   0 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 if(RAND_MAX < 1<<16) x = (rand()<<15)|rand(); else x = rand(); 
•  » » » » » » » » 12 months ago, # ^ |   +3 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.
 » 12 months ago, # | ← Rev. 2 →   +10 How to solve C? Good problem in my opinion
•  » » 12 months ago, # ^ |   0 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
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 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 :(
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 You failed systest because p can be zero right?
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   +5 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 : 30524864Submission during contest : 30508844Only difference is the case n = 2.
•  » » 12 months ago, # ^ |   0 n — 2 random numbers and then generate last two.
•  » » 12 months ago, # ^ |   0 stupid (n == 2 && x == 0) if :(
 » 12 months ago, # | ← Rev. 2 →   0 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.
•  » » 12 months ago, # ^ |   0 I used the same but when a is even a^(a+1)^(a+2)^(a+3)=0
•  » » » 12 months ago, # ^ |   0 My problem was NO case :(
•  » » » » 12 months ago, # ^ |   0 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 odd2) N is evenLet 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 ^ _xorCase 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;
•  » » 12 months ago, # ^ |   0 here is a countercase for your claim. 3, 4, 5, 6 by your claim, answer is 2 but correct answer is 4.
 » 12 months ago, # |   +5 Can answer be "NO" in C except 2 0 case?
•  » » 12 months ago, # ^ |   -11 6 010 0n%4==2 0
•  » » » 12 months ago, # ^ |   +38 0 1 2 262147 4 262148
•  » » » 12 months ago, # ^ |   0 Oh with this case I expect lots of people will be failing. I myself got hacked.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 6 0 YES 1 2 3 4 8 12 doesn't it work?
•  » » » 12 months ago, # ^ |   0 My program gives 1 2 3 4 8 12 to 6 0 and i think its correct
•  » » » 12 months ago, # ^ |   0 1 2 4 8 16 31 satisfies 6 0 case
•  » » » 12 months ago, # ^ |   0 YES 29637 1088 18455 13546 1 2937
•  » » » 12 months ago, # ^ |   0 For 6, 0 my code prints: 781959 11593 584443 901753 630736 488604 Which when xor'ed gives 0. Am I missing something?
•  » » » 12 months ago, # ^ |   0 Now i don't have to wait System testing, C is WA :(
 » 12 months ago, # |   0 How to solve D?
•  » » 12 months ago, # ^ |   0 Binary search. Even tho I expect that my code runs in an infinite loop for some cases.
•  » » » 12 months ago, # ^ |   0 How Binary Search Works Here? Describe Please.
•  » » 12 months ago, # ^ |   -11 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.
•  » » » 12 months ago, # ^ |   0 What's probability of finding correct answer in your solution?
 » 12 months ago, # |   0 And Don't lie that you didn't try to send random solve for C.
 » 12 months ago, # |   0 Will the random solution pass for problem C? (If not, how to hack it?)
•  » » 12 months ago, # ^ |   +3 my solution is random solution , but i can not prove its time complexity.
•  » » 12 months ago, # ^ | ← Rev. 6 →   0 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.
 » 12 months ago, # | ← Rev. 2 →   0 Can anyone say this code bug?(Div 2/c) #include #define int long long using namespace std; const int maxn=1e5+7; int a[maxn]; int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,x;cin>>n>>x; int sum=0; for(int i=0;i0&&nwx
•  » » 12 months ago, # ^ |   0 It does not print "YES" neither "NO" You should print "NO" iff N=2, X=0
•  » » » 12 months ago, # ^ |   0 tank you.
 » 12 months ago, # |   +3 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
•  » » 12 months ago, # ^ |   0 Same here hhh. I just adds "stdout.flush()" 5 seconds before it ends.
 » 12 months ago, # | ← Rev. 2 →   0 For problem E, I have O(N + M + (M — N) log (M — N) + Q log (M — N)). Is that right?
 » 12 months ago, # |   +24 Here is a solution to F: First of there is a basic observations which is important for the solution. lcp(sl, sl + 1, ..., sr) = min(lcp(sl, sl + 1), lcp(sl + 1, sl + 2), ..., lcp(sr - 1, sr)) 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.
•  » » 12 months ago, # ^ |   +15 That is so brutal! I hope there is a nicer solution!
•  » » 12 months ago, # ^ | ← Rev. 2 →   -8 Wow. ._. I thought of this solution as well, but didn't code it cause I was sure it would get TLE >_<
 » 12 months ago, # | ← Rev. 3 →   0 ignore*found my mistake in div2c
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 > 10^5 is ok, just <= 10^6 
•  » » 12 months ago, # ^ |   0 Solution must print value <= 1000000
•  » » 12 months ago, # ^ |   0 how to do it. I tried but nothing came to my mind
 » 12 months ago, # |   -8 How 2 solve D ? I do not even understand why there is mention of fflush
•  » » 12 months ago, # ^ |   0 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.)
•  » » » 12 months ago, # ^ |   0 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?
•  » » » » 12 months ago, # ^ |   0 Yes, you may decide what the next query will be based on what you have received.
 » 12 months ago, # | ← Rev. 2 →   +21 So fast system testing
 » 12 months ago, # | ← Rev. 7 →   +11 System Testing PendingRefresh Page after 10min79% done This times system testing is running at speed of thunder lmao :D
 » 12 months ago, # |   0 upvote for the very quick testing
 » 12 months ago, # | ← Rev. 3 →   +18 ![ ](image upload)
 » 12 months ago, # |   -21 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?
 » 12 months ago, # | ← Rev. 2 →   0 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.
•  » » 12 months ago, # ^ |   0 I just randomly picked all but one numbers and force the last number to fit the requirement.No math here, great!
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 You are lucky, your algorithm is incorrect. What if e.g. n=4 x=0 and your random pick is [1, 2, 3]?
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   -9 Easy solution for problem C : https://ideone.com/FZ6rfw
 » 12 months ago, # |   0 C with x=0 really made the problem trickier.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +4 C with n=2 and x=0 made my solution wrong :|UPD: fortunately, I have some other bug :P
 » 12 months ago, # | ← Rev. 2 →   0 gritukan, 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?
•  » » 12 months ago, # ^ |   +46 Removed one of the attempts.
•  » » » 12 months ago, # ^ |   0 Thanks.
 » 12 months ago, # |   +4 Looks like I'm finally going to div.1! I'm so happy, it was quite a long journey :)
 » 12 months ago, # |   +3 Hello, actually my wrong solution for problem D passed main tests. Here is my solution — http://codeforces.com/contest/862/submission/30518750 and it runs into an infinite loop in the following case : "10"
•  » » 12 months ago, # ^ |   +4 "10" is test case #121 (last), and seems your solution works on it.
•  » » » 12 months ago, # ^ |   +4 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.
 » 12 months ago, # |   -59 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?
•  » » 12 months ago, # ^ |   +22 Somehow I managed to accumulate more downvotes than "is it rated" comments :D
 » 12 months ago, # |   0 Auto comment: topic has been updated by mahmoudbadawy (previous revision, new revision, compare).
 » 12 months ago, # |   +9 After 17 fails and 1:49 my submission for D passed, but it failed again on 59th test. The worst feeling ever
 » 12 months ago, # |   +7 nice problems, c is interesting for me and random_shuffle() solution hhe
 » 12 months ago, # |   +3 How can one proove that random brute solution for C will not time-out ?
 » 12 months ago, # |   -42 please don't make other rounds
 » 12 months ago, # | ← Rev. 2 →   0 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!
•  » » 12 months ago, # ^ |   0 At this statement if(fans[sizea]==0) you might be getting a runtime error as size of fans is sizea.
 » 12 months ago, # |   0 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.com/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?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 12 months ago, # ^ |   0 May be we should ask admins about it? I have too few rating points to loose it that way :c
•  » » » » 12 months ago, # ^ |   0 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. :)
•  » » » » » 12 months ago, # ^ |   0 Well, then i should check my code again.
•  » » 12 months ago, # ^ |   +5
•  » » » 12 months ago, # ^ |   0 Thank you.
•  » » 12 months ago, # ^ |   +5  vector pref_l(n); pref_l[0] = layers[0]; if (max_l > 0) pref_l[1] = layers[1]; for (int i = 2; i <= max_l; ++i) { pref_l[i] = pref_l[i - 2] + layers[i]; } Here max_l can equal n and also you access pref_l[1] which might not exist if n` is 1.
•  » » » 12 months ago, # ^ |   0 Thank you.
 » 12 months ago, # |   +7 Can someone give me some links to good random algorithms tutorial. I see a lot of people used it to solve C.
•  » » 12 months ago, # ^ |   0 I need it too.
 » 12 months ago, # |   0 i have got 237 point int this round keep doing well mahmoudbadawy thank you so much for this round and problem :)
 » 12 months ago, # |   +14 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.
•  » » 12 months ago, # ^ |   0 thats because 2^19-1 is approximately 5*10^5, so at least four fifths of the numbers are unnocupied.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +5 Wow, I used exatly the same algorithm here, same range and also tried 100 times.
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ |   +5 Yes, I made a little function to do that. int randInt(){return (rand() * RAND_MAX + rand()) % 524288;}
•  » » 12 months ago, # ^ |   0 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!
•  » » » 12 months ago, # ^ | ← Rev. 6 →   +2 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.
 » 12 months ago, # |   -14