### JaySharma1048576's blog

By JaySharma1048576, 4 weeks ago,

Hint 1
Hint 2
Tutorial
Solution

Hint
Tutorial
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Solutions

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Solutions

#### E: The Final Pursuit

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Tutorial: Part 1 - Finding the Permutation
Hint 7
Hint 8
Hint 9
Hint 10
Tutorial: Part 2 - Colouring the Hypercube
Visualise the Colouring
Time Complexity
Solution

• +181

 » 4 weeks ago, # | ← Rev. 2 →   -102 -
•  » » 4 weeks ago, # ^ |   +90 No wonder you are gray.
•  » » » 4 weeks ago, # ^ |   -41 Video editorial of 1.A. Exciting Bets 2. B. Customising the Track
•  » » » » 4 weeks ago, # ^ |   +5 your video was helpful to me . thanks
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 Thanks. It means a lot :)
•  » » 4 weeks ago, # ^ |   -94 Problem C should be rejudged with eps = 0, author took esp = 1e-9 but 0 should have been taken ideally
•  » » » 4 weeks ago, # ^ |   +53 It's actually common to encounter precision problems, so if you didn't know it then you should learn it and get AC when you meet float problems again.
•  » » » » 4 weeks ago, # ^ |   0 Can u please check my latest solution it’s got problem c, I know I’ve done everything right except handle precision , can you tell me how to handle precision , thanks in advance :)
•  » » » » » 3 weeks ago, # ^ |   +5 You shouldn't just use $>$ in your code, you have to add that if the difference between two floating number is less then a certain value than it should be count as equal. That number depends but in this question as the editorial says 1e-6 should be enough.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 i didnt get it can u please explain what "exactly" i need to change in my code
•  » » » » » » » 3 weeks ago, # ^ |   0 you can change the if (a > v) to if (a > v && abs(a-v) > 1e-6).
•  » » » » » » » » 3 weeks ago, # ^ |   0 i did it and got ac thanks :) can you kindly tell me why was it needed and how it made my code work
•  » » » » » » » » » 3 weeks ago, # ^ |   0
•  » » » » 3 weeks ago, # ^ |   0 yungyao Can you provide any recourse or link, or even the keyword to search for, in order to learn how to handle precision in cases like this where this advance level of understanding is required.
•  » » » » » 3 weeks ago, # ^ |   0 I learn this from my friends so I am not sure about what resources are good. I think you can just search for floating number precision problems. Anyway the point is that C++ can not handle all floating number precisely, for example 0.1 + 0.2 == 0.3 will return false, so a lot of times if the difference between two floating numbers are small enough then it should be considered same.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sorry... I had a mistake in my code. eps=0 also works fine.
•  » » » » 4 weeks ago, # ^ |   0 Did you notice the variable "scale" in the tutorial?
•  » » » 4 weeks ago, # ^ |   0 I like your name.(not username , but name in profile). voyager
 » 4 weeks ago, # |   +15 you can find the explanation for my alternative solution for E in Tutorial: Part 1- Finding the Permutation.
 » 4 weeks ago, # |   -17 shit that was quick
 » 4 weeks ago, # | ← Rev. 2 →   +23 I was reminded why I don't know and don't like problems which are only about doubles. Spent 2hours trying to find out why a > 0 doesn't work...
 » 4 weeks ago, # |   -82 speedforces
•  » » 4 weeks ago, # ^ |   +5 yes, speedforces for those who solve only one problem in the round.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -20 thought I could get wholesome rivalry, sorry for being cocky:/
•  » » » » 4 weeks ago, # ^ |   +16 it's just stupid to write "I will beat you in the future" when you are rated 600 points lower. Just shut up and work hard.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -10 Its better to be at expert regularly giving contest than stop giving contest on becoming master once just so that you can flex .Maybe a guess or cheating.You can only become the driver of the bus of tourist,so stop putting anything related to our legend-tourist in your profile.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -48 What the hell. I stopped writing rated contests for a while even after becoming purple. I practice on hard problems exclusively during these periods, and when I feel I can jump to the next level (IM in this case) I continue writing contests. As for me becoming master by "fluke", in all the div2 rounds which are unrated for me I have written, I have solved 2400/2500 rated problems within the first hour. So no doubt I can maintain master if I write a contest now. But I don't want pressure of rated contests right now. Its just my personal preference.Your comment is incredibly insulting. You probably are a low rated div3 guy and dont know what it takes to achieve what I have. And as for the guy above, he keeps on writing "I will beat you" so I got angry.Peace.
•  » » » » » » » 4 weeks ago, # ^ |   -22 Yeah people like you who have achieved fcuk all in their life masquerading as all intelligent when i open CF is why i hate people so much. You just got lucky with your submissions and now act as a bl**dy know it all when in reality you are just a stupid BTech kid.Shut up and stop being a fcuking elitist.
•  » » » » » » » » 4 weeks ago, # ^ |   +7 If being lucky was the criteria for codeforces rating then I think all the LGMs should buy lottery tickets immediately.
•  » » » » » » » » » 3 weeks ago, # ^ |   +5 And Leo Messi would be newbie.
•  » » » » » » » 3 weeks ago, # ^ |   +37 The problems which get 2400/2500 in Div2 Rounds are not that difficult(they are around 2200 maybe) but the ones in Div1 like D1B-C(Rated <= 2400 usually) are much more harder. It usually happens with me, I frequently solve 2400/2500 in unofficial Div2s but can't get even close to a 2300 rated problem in Div1.
•  » » » » » » 2 weeks ago, # ^ |   0 Painful but true :").
 » 4 weeks ago, # | ← Rev. 5 →   +33 wtf....from the submission time we can track when solution gets leaked ... so we need to prepare even harder ..to solve before it or near that time... so that we are not at much loss...bcz anyways they wont be banned or even if they will start again this foolishness...
•  » » 4 weeks ago, # ^ |   +20 Typical cheater on codeforces lol
•  » » » 4 weeks ago, # ^ |   +1 i think he's trying to get an unreadable code so he doesn't get hacked, tho he will still fail to real cases if the solution is wrong
•  » » » » 4 weeks ago, # ^ |   +1 And that is still against the codeforces policy lmfao Read policy number 4 in Can-do's and Can't-do's section
•  » » » » 4 weeks ago, # ^ |   0 he will fail in real — interview for sure.. as he already sold his moral values..and already failed in real life..xd
•  » » » » » 4 weeks ago, # ^ |   +1 Another wtf submission:Submission A — 00:06Submission B — 00:09Submission C — 01:40Submission D1 — 00:53
•  » » » » » » 3 weeks ago, # ^ |   +5 Is this some sort of hack??
•  » » 4 weeks ago, # ^ |   0 XD WTF!
•  » » 4 weeks ago, # ^ |   0 Maybe he wants to have a higher rating by this disgusting way . However , He is lack of honesty which must be kept in our daily life .
•  » » 4 weeks ago, # ^ |   +7 MikeMirzayanov Please ban these type of user immediately to set an example, humble request, Please :\
 » 4 weeks ago, # |   -21 C was definitely the worst question, because it is a hit or miss. People who are used to this type of question would probably convert the doubles into integers/long long to prevent errors, but most people are gonna suffer from the terrible precision of long double. Aside from rambling, I think D2 is a pretty cool question nevertheless.
•  » » 4 weeks ago, # ^ |   +70 Well, float precision is an important skill for competitive programmers. For people that are not familiar with these kind of problems, they will learn from this.
•  » » » 4 weeks ago, # ^ |   0 How can we learn float precision skills ? How does float work ?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Here geeksforgeeks article here
•  » » » 2 weeks ago, # ^ |   0 Precision errors are unpredictable most of the time. I've seen problems where a mere change in the value of eps creates the difference between Accepted and Wrong answer on test 22 xD. For eg. changing eps to 1e-14 gives WA but 1e-10 works.
•  » » » » 8 days ago, # ^ |   0 Could you please share that task you talking about. Thank you.
•  » » » » » 8 days ago, # ^ |   0 It was in a gym contest I'll have to search. I'll share when I find it.
•  » » 4 weeks ago, # ^ |   0 I don't get why long double gives me WA but double gives me AC. I added 1e-14 to the inputs in both cases.
•  » » » 4 weeks ago, # ^ |   0 its the same case with int and Long long int its just a bigger set of bits to work on
•  » » » 4 weeks ago, # ^ |   0 Yeah why? also what does adding 1e-14 do?
•  » » » » 4 weeks ago, # ^ |   0 adding 1e-14 to the numbers increases precision up to 14 digits and from here on every operation will be performed up to this precision. I'm not sure if this is what happens but this simple trick has worked for me in many such problems.
•  » » » » » 3 weeks ago, # ^ |   +5 The same trick doesn't work if instead of adding 1e-14 we multiply by 1.00000000001 does multiplying not increase precision?
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +6 does multiplying not increase precision? No, multiplying doesn't improve precision. In fact, it makes precision worse.(Edit: Also, "adding 1e-9 or 1e-12" doesn't "improve" your precision. What it does is basically saying "if the probability is less than 1e-9, we'll assume it's zero". We need this because, for example, 0.3-0.2=0.09999999999999998 (you can check this in python).)
•  » » 3 weeks ago, # ^ |   0 how's it hit or miss? they said 1e-6, i used 1e-6, first try
 » 4 weeks ago, # |   +20 This was a fun round and figuring out how eps works finally paid itself off. Also massive props for making one of the most interesting interactives on codeforces. :)
 » 4 weeks ago, # | ← Rev. 2 →   +7 In C, one of my pretest answer was off by 0.002, rest were correct, so I was getting wrong answer, I usually use python, did a little bit of digging up after contest when I switched from float -> Decimal class, got the right answer :/
 » 4 weeks ago, # |   -56 ReadingStatementsForces
•  » » 4 weeks ago, # ^ |   +49 In what round do you not have to read the statement? April Fools??
 » 4 weeks ago, # |   0 When the proofs are by induction... you know it's either hit or miss.
 » 4 weeks ago, # | ← Rev. 3 →   +55
•  » » 3 weeks ago, # ^ |   +10
 » 4 weeks ago, # |   +11 Thanks for detailed editorial containing hints and multiple approaches.
 » 4 weeks ago, # | ← Rev. 2 →   +10 In problem C, why if 0 is used in place of epsylum(very small value) in the author's solution gives a wrong answer?
•  » » 4 weeks ago, # ^ |   +7 Exactly that's also my question
•  » » 4 weeks ago, # ^ |   -13 0 is an integer and eps is a double , that is why using epsilon prevents precision errors
•  » » 4 weeks ago, # ^ |   +102 The problem is that when you compare two floating-point numbers, the result of the comparasion may be wrong, because computers store numbers up to a certain precision.In this problem, when a certain probability becomes exactly 0, the respective variable may store a very small number due to precision issues, and you make an extra step due to that, changing the answer. You should always compare floating points with epsilon, unless the comparasion result is irrelevant.How to choose a proper epsilon? That is a difficult question in general, but in this problem it is easy. Let's say that you store the probability in variable a. I claim that the true value of a is always of the form $a= x\cdot 10^{-4}\cdot 2^{-steps}$, where $x$ is an integer and $steps$ is the number of steps made. It can be proved by induction on steps. Now it's easy to see that the true value is either $0$ or at least $10^{-4}\cdot 2^{-20} > 10^{-11}$. Given that precision issues are usually not greater than few least significant bits ($\approx 10^{-16}$ if you use long double), any epsilon between these numbers should work. It turns out that some other epsilons work too.The reference solution to this problem operates in integers, of course, and avoids these issues. It will be uploaded in the post soon.
 » 4 weeks ago, # |   +5 Thank you, liked the problems! Although I thought A is too hard to be A, but it was fun:)I have a question about my solutions. On my machine, the answer was printed, but in system I got WA. Here's my solution: 121640373. System said that on test 5 3 with start password 1 I tried five times and haven't guessed it, but when I was testing locally my program did. Can anyone please tell me why did it happen?
•  » » 4 weeks ago, # ^ |   +3 Thanks to kind man in technocup chat, problem solved, I thought that a xor b = z means that b equals z xor a. And this was mentioned in the editorial, so sorry for stupid question:)
 » 4 weeks ago, # |   0 I know this is generally a dumb question, but I have to ask — people who solved E, how did you come up with the colouring? Is it just a matter of throwing shit at the wall and seeing what sticks?
 » 4 weeks ago, # |   +157 If you didn't like the contest, don't downvote the editorial. Just downvote the announcement.
 » 4 weeks ago, # |   +58 Hello everyone, please do not downvote the editorial because you did badly or didn't like one problem from the round. Round authors and testers did their best to make the round as high-quality as possible, and you can see that they even implemented feedback to give hints inside the editorial, which is really appreciated!Thank you JaySharma1048576 for this wonderful round!!
 » 4 weeks ago, # |   +2 How could we guess to use epsilon in problems like C? Is it some rule to have it as 10^-6? I used it as 0, but my solution gave imprecise answers for 3rd test case in the sample test case. Even, the editorial solution gives the same answer as mine if epsilon was set to 0. So, I could confirm that I was getting wrong answers only because of the precision problems. Does using 1e-6 as epsilon work for other similar problems too?
•  » » 4 weeks ago, # ^ |   0 I also have the same doubt. In the official solution, if we change the value of eps to 1e-17 or lower, the answer varies drastically.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 Try if(0.1 + 0.2 == 0.3)cout << "Yes"; else cout << "No"; This will print "No"
•  » » 4 weeks ago, # ^ |   +4 When you must work with doubles/floats you should always test for equality with very small values such as (1e-6, or 1e-9), as opposed to 0, due to precision errors. If you compile with the -Wfloat-equal option, your compiler will automatically alert you to not test for equality with "==" or "!=" if you do in your code
•  » » 4 weeks ago, # ^ |   0 no 1e-6 is often too big to find equality in pb152 of PE you would find false solution if you used such an epsilon, sadly you have to use gut feeling to guess in each problem the good epsilon. By the way I got WA on test case 4 after the round I'm very angry against myself
 » 4 weeks ago, # |   +14 Really appreciate the quick and detailed editorial, it really helps to read the editorial while the problems are still fresh in your mind (if that sentence makes any sense :P). Having said that, I do think that a disclaimer that a round is gonna be more math-centric rather than algorithm based should be given as a lot of people might only enjoy algorithm based contests, but a decent round nonetheless :)
 » 4 weeks ago, # |   0 In problem C official solution, epsilon = 1e-9 is being used for checking 0 equality. However, if exact 0 equality check is used in the conditions, the solution fails by 0.03 even on pretest 1 (input 3). Can anyone please explain how do we determine what equality check to use in such questions ?
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   +11 In C, why there are precision issues, even if I set the argument to 0 explictly? I thought 0 can be represented accurately according to IEEE 754, but it seems in the function the zero becomes a small number rather than 0.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 It’s correct that literal zero has exact representation, but how do you deal with subtraction c - v and m - v in the writer’s solution, which can result in a tiny floating point number even when it’s zero in theory?
•  » » » 4 weeks ago, # ^ |   0 Oh I see, thank you!
 » 4 weeks ago, # |   +15 Language of C could have been better. Otherwise good problems(specially interactive ones)
 » 4 weeks ago, # |   0 Problem C, constraints hinted what to do and example hinted how to do. Just precision error was the problem. Anyways learned to deal with doubles today!!But my curiosity is : Can we derive a direct formula for it and solve in O(1)?
 » 4 weeks ago, # | ← Rev. 2 →   +51 This is to clarify why taking epsilon equal to $0$ will not work in C. Everyone know that floating point arithmetic is associated with some precision errors which is usually of the order $10^{-15}$. So, if $c=v$, ideally $c$ should become invalid but if due to some floating point precision error, $c$ becomes $10^{-15}$ and if you are comparing it with $0$, your code will treat it as still valid and this will cause a Wrong Answer. In this problem, taking any epsilon in the range $10^{-6}$ to $10^{-14}$ will work, not only $10^{-9}$. I was well aware that many participants will make this error. So, I included a test where this error arises in the samples itself (sample test case 3) so that no one gets unnecessary penalties.Moreover, the main solution against which the solutions are checked doesn't use floating point numbers. It uses integers after multiplying the values by a scaling factor. I am providing that solution in the editorial.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0 What would you like to say about the bad written statement of pC and pD? I am not a native speaker , it took me more than 30 minutes to understand pC, finally when I realised I could solve it, I was getting precision error on my compiler, can't you guys write simple statements like AtCoder does? (I know I will be downvoted, but just wanted to say this, I was disappionted reading so-long and trashy statements of pC and pD)
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0 "In this problem, taking any epsilon in the range $10^{-6}$ to $10^{-14}$ will work"@JaySharma1048576, Can you please show the proof for the above statement with all the steps!! I know I am asking for more but this kind of problem is not common(at least I encountered this for the first time) so please help! Thanks for the great round!
•  » » » 4 weeks ago, # ^ |   +3 Epsilon should neither be too high nor too low. In general, it should be less than the lowest significant number that may affect the answer and more than the highest precision error that may occur. $v$ has $4$ decimal places at max as given in the constraints. It follows that $\frac{v}{2}$ has $5$ decimal places at max. So, at any point when there are three valid items, $c$, $m$, and $p$ can have $5$ decimal places at max. When suppose $c$ becomes invalid, $\frac{c}{2}$ gets added to the probabilities of the remaining items which can have $6$ decimal places at max. After this, the number of decimal places in $m$ and $p$ can never go more than $6$ because all the probability will now go to $p$ only involving no division by $2$. So, at any point the maximum epsilon allowed is $10^{-6}$. If you look more carefully then the $5$-th and $6$-th decimal places will always be one of $00$, $25$, $50$ or $75$. So, the maximum epsilon allowed is in fact $25\cdot 10^{-6}$. But for simplicity, I have taken $10^{-6}$. The lower limit is, however, difficult to say. Precision errors are quite random and may be as low as $10^{-18}$ or as high as $10^{-15}$. But since double data type uses $52$ bits for mantissa, atleast $15$ decimal places of accuracy is guaranteed. So, anything greater than $10^{-15}$ must be fine for epsilon.
•  » » » » 3 weeks ago, # ^ |   0 Thanks!
 » 4 weeks ago, # |   0 Question was too much complex
•  » » 4 weeks ago, # ^ |   0 True
 » 4 weeks ago, # |   +7 Please do not downvote this blog. Some people might be unable to find the editorial.
 » 4 weeks ago, # | ← Rev. 2 →   +240 I'm kinda disappointed at problems in this round, cuz I feel they're not so relevant to Algorithm or something fun but more revelant to English Reading and Code Implementation. Problem A and B are not bad but the easy problems don't really effect the quality of a round. Problem C and D are just annoying implentions with no algorithm. Isn't Problem E just a well-known problem since a famous youtuber 3 Blue 1 Brown has talked about it? Although 3B1B doesn't give solutions directly, this problem is anyway standard. As for English Reading, the statement is unnecessary long and lack of logical relationship, I can't get the key info fluently at all. Everyone prefers short and clear statements, or at least a longer but logically reasonable statements, instead of these. Idk why author addes "You beat xxx" or "You race with xxx" in beginning, when xxx just doesn't appear in any part of the following statement. I can't see any logical relationship between this character and the problem. And tbh some elements in the statement like Cash Slip, Impound Strike Release Marker and Pink Slip of Rival's Car is extremely confusing, at least for me. I spend time looking up what does these words mean and thinking how they're revelant to the following statement but it just turns out that I'm wasting time.
•  » » 4 weeks ago, # ^ |   +47 I hadn't seen any problem like E before. Btw if setters never use something similar to "known" problems then will they even be known for most div2 participants?I mostly agree with the rest though.
•  » » » 4 weeks ago, # ^ |   +3 Well, fair enough. What I concern is, cuz it feel like a repeated problem in a sense, especially cuz it's not so relevant to a certain algorithm. I'm kinda worried about situations like someone easily solve it if he learned it before, when others with more experience in algorithm maybe can't get the point in a short time.Btw, to author if you're seeing, I don't mean to be negative to your efforts >_<, I respect all people contributing to CF. Just want to give some suggestions to look forward to your better problems. >_<
•  » » » » 4 weeks ago, # ^ |   +69 Sure. I am not blaming you for anything. I am taking your feedback positively and I will try to improve the statements next time.
•  » » 4 weeks ago, # ^ |   0 As a Div2 participant who was and is unable to solve C, D2, and E (I might get downvoted hard for this). You are right about almost everything but once you understand the problem D it was mesmerizing to me. It was one of the best if not the best problem I have ever solved without checking out the editorial. But yes problem statements were confusing and long.And about E. I have watched the video but I'm not confident enough in my coding skill that I'll be able to solve it (Actually I didn't even reach E during the contest). If the author is reading this then first thanks for the round and secondly your problems were great but statements can be improved (from the Div2's participants perspective).
 » 4 weeks ago, # |   +6 Thanks for detailed editorial containing hints and multiple approaches！ ><
 » 4 weeks ago, # |   +6 Hi! Guys you don't have to downvote the editorial because Author and coordinator and testers did their best to create this contest and dear Author made a great and complete editorial ! Afterall Good job everyone.
 » 4 weeks ago, # |   0 Great and detailed editorial! And thanks for the reminder that I'm just as bad at maths as I'm at algorithms (for now). Time for me to a lot do more practising :)
 » 4 weeks ago, # | ← Rev. 2 →   0 In problem A, the input constraints for a and b are 0 to 1e18. Many participants used int type variables to read a and b have verdict as Accepted. Is it because the main tests do not contain tests which are greater than INT_MAX. Example: 121578546
•  » » 4 weeks ago, # ^ |   0 The solution has #define int long long in the template.
•  » » » 4 weeks ago, # ^ |   0 Sorry. My bad.
•  » » 4 weeks ago, # ^ |   0 he/she has defined int as long long
 » 4 weeks ago, # |   +2 Problem C was not at all good; first and foremost, its language was as terrible as it could be. It was difficult to follow, and the variables used to describe the test cases were unclear. Simple and precise language can also be used to create a nice and fascinating problem.
 » 4 weeks ago, # |   +1 A: good idea, gcd(x, y) = gcd(x — y, y) B: intuitive, greedy C: implementation D: try 0~(n-1) with previous change
 » 4 weeks ago, # |   0 Problem C : I thought that I would not be able to do it even 1%. But I am happy that actually I solved the sample cases except 3rd one. I spent a lot of time in thinking about this. This is actually a very nice problem and increases thinking ability.
 » 4 weeks ago, # | ← Rev. 2 →   +3 Can anyone give the reason why 1 is added in the recursive solution given in the editorial of problem C in the line given below Spoilerans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));
•  » » 4 weeks ago, # ^ |   0 else you would get as whole answer 0, you must count future race and this particular race (which is the 1), hope I'm clear
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Got it . I was thinking about the probability of occuring the event all the time. btw Thank you
 » 4 weeks ago, # |   0 Why is this code https://codeforces.cc/contest/1543/submission/121641823 fast? Shouldn't it get TLE? Are tests bad?
 » 4 weeks ago, # |   +10 C can be solved with DP in O((2/V)^3) or even O((2/V)^2) https://codeforces.cc/contest/1543/submission/121629108
 » 4 weeks ago, # |   0 Well I overkilled B with some weird implementation 121633991
 » 4 weeks ago, # | ← Rev. 2 →   0 nevermind, got it
 » 4 weeks ago, # |   0 Is it preferable to avoid using accumulate to find sum of vector in C++,as in problem B using accumulate tofind the sum of vector, solution gets failed on pretest 2,but when I switch to find sum in usual way it get passed. Does anyone have any idea about this?
•  » » 4 weeks ago, # ^ |   +8 Yes, it's better to use things you can control and understand.When you use accumulate, the accumulative variable takes the type of the last argument. So if you pass an int, it'll be an int and you'll have overflow.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Writing 0ll in place of 0 , in accumulate function would have worked as 0 is int and 0ll is long long int , and int gives overflow. Your code ACfied
 » 4 weeks ago, # |   0 121621126Can anyone help me why I'm getting TLE ? And help me to optimize itI have guess it's java, is'nt it? T-TI used python and it barely passed with same logic and its intended logic too T-T
•  » » 12 days ago, # ^ |   0 Yeah I guess so. Same happened to me, even though my algorithm is identical to Idea 2 in the tutorial.
•  » » 11 days ago, # ^ |   0 ok so apparently buffered reader isn't fast enough, but System.in.read(); is. Check this guys solution for reference: 122226246. I copied his fasterScanner method and my solution also got accepted.
•  » » » 11 days ago, # ^ |   0 Yes, even I saw that.But that's not fastscanner its superfast scanner XD.Thanks for mentioning.
 » 4 weeks ago, # |   0 I really enjoyed problem D even though I lost a lot of time and points getting TLEs because of slow python IO (had to switch to stdIO). I'll know better next time.Anyway thanks for the nice problems.
 » 4 weeks ago, # |   0 This round sure made me value reading the problem statements properly. I hope it makes me green as well. Thanks for the difficult but interesting round.
 » 4 weeks ago, # |   0 In Problem A, using fmin() function gave me the wrong answer on the 3rd test case, and somehow then I swapped fmin() with the min() function and boom, and it was accepted! Still trying to figure out! Didn't knew these small things could be so crucial! Suggestions are welcomed!
 » 4 weeks ago, # |   0 Is the adaptive grader on problem D badly designed? https://codeforces.cc/contest/1543/submission/121656699 gets accepted even though it has //if(r == 1) return; commented out.
•  » » 4 weeks ago, # ^ |   0 It is because the adaptive grader is designed such that any solution which passes will pass only after exhausting all $n$ queries. Read the note given about adaptive grader given in the editorial. In order to pass all initial passwords, you need atleast $n$ queries, because with one query, you can pass not more than one initial password. So, even though it seems that your correct code may guess the correct password in less than $n$ queries, the correct code will use $n$ query only. So, returning or not returning doesn't make any difference.
•  » » » 4 weeks ago, # ^ |   +22 Yes, that's exactly the problem. The grader assumes that the best way to break people's solutions is by checking whether they are correct for all n possible starting passwords by always saving the "correct query" until the very end. In my opinion, having this grader for every single test case is bad design because it allows some incorrect solutions (like the one I posted) to pass. Ideally, there should have been at least one or two test cases that don't use this algorithm so that incorrect solutions like the one I posted fail.
 » 4 weeks ago, # |   +50 A few words on this round. I will refrain from commenting on floating-point stuff (related to C) because basically everyone else has already done it. :) Statements were mostly clear (that is, unambiguous), but C was a pain to read and D, I believe, could have been shortened a bit. Also in D, the wording "You don't know it, but you are quite sure that it lies between $0$ and $n−1$ inclusive." is a poor choice (you are not "quite sure", you are absolutely sure). Problem A is too mathy in my opinion. Apart from that, average problem for Div 2. I didn't like B. The observation that only the sum matters is trivial, and the fact that the individual $a_i$'s are irrelevant is the CP equivalent of a math problem with useless hypotheses. Also, I found it easier than A, but that might be subjective. C is pointless. The fact that it is solvable only under the constraint $v \ge 0.1$ makes it really uninteresting. D1 and D2 were nice and I enjoyed them, but the concept behind the problem is a bit unnatural (which is reflected in the length of the statement: I find that the most natural and beautiful problems are the ones that allow for clear, short statements). E I didn't even read. Overall, I consider this a bad round, even though there have been worse.On the other hand, the editorial is really well-written and understandable!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 deleted.
 » 4 weeks ago, # | ← Rev. 3 →   +8 deleted.
 » 4 weeks ago, # |   0 There can be a much better solution to D2. In case of k = 2, number itself is kind of k-wise xor inverse. So, if we think in terms of k-wise xor inverse of a number it would be easier to understand that solution and come to the solution as well
•  » » 4 weeks ago, # ^ |   0 How can we arrive to solution if we think in terms of k-wise xor inverse? The solution given in the editorial seems like a guess to me and then later proved with induction. Can you please tell me how to arrive at the solution by oneself?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 Let xi,k be a number such that k-itwise xor of x and xi is 0. If x was password , y is the guess made then z is new password such that x (xork) z = y Here, xork represents k-itwise xorIf we take k-itwise xor with xi,k both side we get —xi,k (xork) x (xork) z = y (xork) xi,kz = y (xork) xi,kTherefore new password is k-itwise xor of k-wise xor inverse of old password and guess.I would like to state one property before we go on to solution — (a xork b) i,k = ai,k (xork) bi,kThis can be simply proved if we think in terms of k-itsIn mth guess we will guess the number supposing original number was m-1So, the order is password — xguess — 0new password(if guess wrong) — xi,k (xork) 0 = xi,kpassword — xi,k (xork) 0guess — 1i,k (xork) 0new password(if guess wrong) — (xi,k)i,k (xork) 0 = x (xork) 0 = xpassword — xguess — 2new password(if guess wrong) — xi,k (xork) 2 password — xi,k (xork) 2guess — 3i,k (xork) 2new password — (xi,k (xork) 2)i,k (xork) (3i,k (xork) 2) = x (xork) 2i,k (xork) 3i,k (xork) 2 = x (xork) 3i,kpassword — x (xork) 3i,kguess — 4 (xork) 3i,k So, we can simply see that ith guess isif i is odd — (i-1) (xork) (i-2)i,kif i is even — (i-1)i,k (xork) (i-2)As I didn't have mathematical symbols, solutions look a litle complicated than it is.
•  » » » » 3 weeks ago, # ^ |   0 Thanks a lot. But to be honest, it still seems like a guess to me. I think I should just leave the problem for now and get back to it after some time. Thanks again.
•  » » » 3 weeks ago, # ^ |   0 For problems D1 and D2, I guess that the thinking pattern we should retain when analyzing future similar problems is: We need to finish in at most $n$ queries and the initial password is an $x$ such that $0 \leq x < n$, so we should seek for the property: "If the initial password is $i-1$ then we finish at the $ith$ query". See what happens if the initial password is $i-1$ and we make a sequence of queries $q_{1}, q_{2},...,q_{i-1}$ . For example, in the case of D1, we should notice that the password will become $(i-1) + q_{1} + q_{2} + ... + q_{i-1}$. We want to finish in the $ith$ query. So we want $q_{i} = (i-1) + q_{1} + q_{2} + ... + q_{i-1}$. Here we could guess a sequence of queries that satisfy this condition (like in the first method in the editorial) or we could just say that $q_{1} = 0$ and at each iteration make the current query and renew the prefix (like in the second method in the editorial). For me the second method is more reasonable and less magic. I noticed that D2 requires a similar reasoning but we need to manipulate the recurrence relation a bit to create a prefix that is renewable at each iteration taking care of the fact that the minus operation will not be associative nor commutative.
 » 4 weeks ago, # |   -24 Everyone be complaining about messy problem statements but the truth is TRUTHYou just haven't played NEED FOR SPEED: MOST WANTED.Prob C brought to light my misconceptions of float operations. The NFS: MW references were a joy to read and recall, despite their irrelevancy. Thank you very much for this contest!
 » 4 weeks ago, # |   0 can someone please tell me why its getting WA on C submission link — https://codeforces.cc/contest/1543/submission/121660498
 » 4 weeks ago, # |   0 D1 is annoying, same algorithms but using Python will get TLE (maybe because output is so slow) really unfair.
 » 4 weeks ago, # |   0 I can't understand the brute force implementation of problem C , i can't understand the addition of 1 and then the recursive call
•  » » 4 weeks ago, # ^ |   +3 E(c,m,p,v)=1+c*E(c-v,m+v/2,p+v/2,v)+m*E(c+v/2,m-v,p+v/2,v). I have not included the extra if/else cases here. Just initialise the recursion with 1 and continue.
•  » » » 4 weeks ago, # ^ |   0 I really still don't understand why plus 1. Can you explain a bit more?
•  » » » » 3 weeks ago, # ^ |   +5 In the definition of problem, the probability is about "count of all race until P is selected" So, select C or M means one more race. So +1
 » 4 weeks ago, # |   +1 I have solved C using doubles, but I tried to solve it again by converting it to integers after multiplying it with scale as given in the editorial. However, I am getting overflow doing that. I have already defined # define int long long. Can someone point out the error, please? My code
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 The reason of over flow is while returning the value from val function , you are returning no.>= 1e6 , which in more than 3 multiplication will lead to overflow .
•  » » » 3 weeks ago, # ^ |   +5 Yeah, thanks. It worked. Moreover, I was initializing my answer with 1e6, it should have been 1e12. I had one more doubt, I have mentioned that in this comment.
 » 4 weeks ago, # |   0 ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v)); why is there a 1+ here ? How is this accounting for the multiplication of the length/depth/no of races with the probability ? Please someone explain this to me ! This is bugging me and I can't sleep , help.
 » 4 weeks ago, # |   0 I don't understand how can anyone conclude that after i-th query the password would be x^(i-1),until he has not seen this before. does it come from god?
 » 4 weeks ago, # | ← Rev. 2 →   +2 For the first part of question E, you can find the inverse permutation s as follows.Pick any vertex V and let s(V)=0. Then send the neighbors of V to the powers of 2.In the standard n-cube, the distance of i to 0 is just the number of bits set in i. Moreover, the vertices which occur on some shortest path from i to 0 are precisely the submasks of i. In particular, if i is at a distance of >=2 to 0, then i is the bitwise or of its neighbors which are closer to 0.To find the inverse permutation, we can proceed by doing a bfs after assigning the neighbors of V. When we reach vertex v, let s(v) be the bitwise or of s(w) as w ranges over the neighbors of v which have already been seen. (Here, we should note that two vertices at the same distance from 0 in the standard cube have at least 2 different bits, so are not neighbors. Thus a neighbor is closer to the staring vertex V if and only if it has already been seen).This gives us the inverse permutation. To go back the original permutation, sort the list of i by s(i).
 » 4 weeks ago, # |   0 is this contest unrated ?
•  » » 4 weeks ago, # ^ |   0 I want to ask the same question.My rating hasn't changed, either.
•  » » » 4 weeks ago, # ^ |   0 most probably
•  » » 4 weeks ago, # ^ |   0 I wish so. May the ratings be with us.
 » 4 weeks ago, # |   0 Could anyone tell me why my rating hasn't changed?
 » 4 weeks ago, # |   0 Problem E can be found in YouTube.
•  » » 4 weeks ago, # ^ |   0 So is it unrated?
•  » » » 4 weeks ago, # ^ |   +8 Probably not.These two things are not related.
•  » » » » 3 weeks ago, # ^ | ← Rev. 6 →   0 Can you give some tips for questions like E. Others were relatively easy but I have never seen anything like E before and even after the contest its hard to understand. Any resources would be nice
 » 4 weeks ago, # |   0 Dread it. Run from it. "math" arrives all the same.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can somebody tell the time complexity of problem C in the simplest way?UPD: GOT it.
•  » » 4 weeks ago, # ^ |   0 btw I love the problem D1.
 » 4 weeks ago, # |   0 in question 3 it showed pretest passed(3) but later during system testing it showed TLE on testcase 2.How is it possible means why it then showed pretest passed???
•  » » 4 weeks ago, # ^ |   0 oh i got it it was precesion error
 » 4 weeks ago, # |   +3 Thankyou for this round, I messed up C for 1 hour due to precision errors but learned something in the process. D1 and D2 were interesting to me as well.
 » 4 weeks ago, # | ← Rev. 2 →   0 Nice round although wasn't able to solve C but got to learn new concept of precision Handling today
 » 4 weeks ago, # |   0 ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));I don't understand where the number 1 comes from in this expression
•  » » 4 weeks ago, # ^ |   0 With c probability, you'll play 1 move, plus, the expected number of moves starting from new probabilities. That's why "1 + E(c-v, m+v/2, p+v/2, v)"
 » 4 weeks ago, # |   0 Can anybody explain their thought process for D1?
•  » » » 4 weeks ago, # ^ |   0 So realizing that if x^z = y can be written as y^x = z seems to be a critical observation. How did you realize that ?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I knew that x^x = 0 and 0^z = z from the truth table of bitwise xor operator.Hence, x^z = y => x ^ x^z = x ^ y => (x^x) ^ z = x ^ y => z = x^y
•  » » » » » 4 weeks ago, # ^ |   0 Thanks man I get it now :)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Just think about D2, then restrict the solution to $k=2$.
•  » » » 3 weeks ago, # ^ |   0 Is this the reason why you failed solving D1 during the contest? Solving the problem for $k=2$ and then trying to generalize the solution seems to be much more rewarding.
•  » » » » 3 weeks ago, # ^ |   0 The logic is basically the same, the only difference when $k=2$ is that $i \oplus j = i \ominus j$.
 » 4 weeks ago, # |   -8 Where my rating
 » 4 weeks ago, # | ← Rev. 2 →   -16 Orz
 » 4 weeks ago, # |   0 Problem B explanation with code: https://youtu.be/btqQYh7FXak
•  » » 4 weeks ago, # ^ |   0 Really helpful solution
 » 4 weeks ago, # |   0 Nice Tutorial
 » 4 weeks ago, # | ← Rev. 2 →   +6 It seems like the coloring part of E is touched on in this video. It's also a great watch, with a nice application of the problem.The game mentioned in the video is also a nice, intuitive way to come up with the xor-based solution. Let's consider playing the coin game on a $n$-square board. As explained in the video, flipping exactly one coin corresponds to moving to an adjacent vertex in the (non-permuted) $n$-hypercube, with each bit corresponding to whether each coin is facing heads or tails. Let's color the vertices of the hypercube so that the state with the color $c$ corresponds to the key being under square $c$. Therefore, as we need to be able to communicate any value of $c$, we require that the set of colors of neighbors of any vertex must have all possible colors from $0$ to $n-1$, hence any solution to this coin game is equivalent to a desired painting of the $n$-hypercube.Now, what's a simple solution to the coin game (when $n$ is a power of $2$)? Let's number each square from $0$ to $n-1$. Let's define some value $v$ calculated from the state of the board that we can change to any other value by flipping exactly one coin. Well, xor of numbers of all squares with heads works here because by flipping one coin in square $s$, we flip all bits in $v$ corresponding to mask of $s$. As we can choose any mask (due to $n$ being a power of 2), we can flip exactly one coin to change $v$ to any value between $0$ and $n-1$. Therefore, we can change the board state such that $v$ is equal to the square under which the key is located.It is not difficult to see that this solution to the coin game corresponds to the coloring shown in the editorial.
 » 4 weeks ago, # |   0 Could you guys help me with TLE on D1 with java? https://codeforces.cc/contest/1543/submission/121703927
 » 4 weeks ago, # |   0 can anyone explain in problem C(solution) we are adding V/2 which rounded down always. Will it not affect the answer?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 They first scaled the input by $1e6$. Since the number of decimals is at most 4 it is therefore guaranteed to be divisible by 2, so there will not be any rounding error.E.g. $0.1234$ is scaled to $123400$ which is divisible by 2.
 » 4 weeks ago, # | ← Rev. 2 →   0
 » 4 weeks ago, # |   0 The Answer to test case 0.4998 0.4998 0.0004 0.1666 should be 5.0307188293 instead of 5.05 Since v is 0.1 minimum so the game ends in max 20 turns(since you are taking atleast v/2 from the c + m collection). If you simulate the game till 20 turns for all possible CM combinations you get 5.0307188293. The approximation I see every where of comparing with 1e-9 is not accurate.
 » 3 weeks ago, # |   0 cannot understand solution of D2 any video suggestions ?
 » 3 weeks ago, # |   0 Ok this might be a dumb question but in ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v)); // ^--------------------------------------- this why the 1?
•  » » 3 weeks ago, # ^ |   0 Read this comment.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Nvm this explained it. https://codeforces.cc/blog/entry/92582?#comment-813242I read the comment but shouldn't each call be: p + (all the cases for c) + (all the cases for m). That is, Choose p now and halt Choose c and continue Choose m and continue So E(c, m, p, v) = p + c*E(c-v, m+v/2, p+v/2, v) + m*E(c+v/2, m-v, p+v/2, v)
 » 3 weeks ago, # |   +3 In the editorial, the author JaySharma1048576 has used a scale of 1e6. However, when I am using a scale of 1e6, it is giving WA on Test 8. Code-121732306 On the other hand, when I am increasing the scale, it's giving AC. Submissions-121733647 and 121733750 Can someone tell me please, what should be the minimum scale to avoid integer overflow, as using 1e6, would have given FST in Contest?
•  » » 3 weeks ago, # ^ |   0 1e6 worked for me https://codeforces.cc/contest/1543/submission/121735506
•  » » » 3 weeks ago, # ^ |   0 Your solution is almost same as the editorial solution, by which all the solutions are checked. I am asking the reason.
•  » » 3 weeks ago, # ^ |   +7 You should take c = round(c1*xx) instead of c = (c1*xx) in your code because 0.1*1000000 may be equal to 99999.9999999..., again because of precision errors with floating point numbers. Typecasting it to int will give 99999 but it should be 100000 for which you should use the round() function. The scale of $10^6$ is completely fine in this problem because the inputs have $4$ decimal places at max.
•  » » » 3 weeks ago, # ^ |   +1 Oh, thanks a lot. Learnt a new thing today.
 » 3 weeks ago, # |   0 I am trying to do lot of problems but in current contest A tag problem to unable to built logic even after seeing hint or toutorial . Can anyone suggest me what to do !
 » 3 weeks ago, # |   +5 bruh i tried to do a O(d^2) sol for C
 » 3 weeks ago, # | ← Rev. 3 →   +3 Sorry for posting this late, but can someone please explain why 1e-10 works in the below line for a solution to Problem C, but 1e-9 doesn't? Shouldn't they both be working? if(p * level * prob <= 1e-9) return; The submissions: 1e-9, 1e-10.
 » 3 weeks ago, # |   0 The coloring part of problem E was posed here: https://codeforces.cc/blog/entry/52918
 » 3 weeks ago, # |   0 can anyone tell me where the solution to my problem C is wrong? I'm not even correct for test case 3 of the example https://codeforces.cc/contest/1543/submission/121776211
 » 3 weeks ago, # |   0 JaySharma1048576 Can you please share the code of adaptive checker for D1 & D2?
•  » » 3 weeks ago, # ^ |   +2 Interactor#include "testlib.h" #include using namespace std; int knxor(int x,int y,int k) { int z=0; int p=1; while(x>0 || y>0) { int a = x%k; x=x/k; int b = y%k; y=y/k; int c = (a-b+k)%k; z = z+p*c; p=p*k; } return z; } int main(int argc, char* argv[]) { setName("Interactor for RPD and Rap Sheet"); registerInteraction(argc, argv); int t = inf.readInt(); cout << t << endl; cout.flush(); for(int tt=0;tt x; for(int i=0;i20000000) { cout << -1 << endl; quitf(_wa,"!! Suspicious activity detected. Password entered must lie in the range [0,20000000] !!"); } else { int z; if(q%2==0) z=knxor(y,p,k); else z=knxor(p,y,k); p=knxor(y,p,k); x.erase(z); if(x.size()==0) { cout << 1 << endl; ac=true; break; } else { cout << 0 << endl; } } cout.flush(); q++; } if(!ac) { cout << -1 << endl; cout.flush(); quitf(_wa,"!! You have been blocked because you made %d incorrect attempts !! (The initial password chosen was %d)",n,*x.begin()); } } quitf(_ok,"You are genius! RPD is going to regret this."); } 
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone guide me to more problems like D2, dealing with non-binary base system. Thanks in advance !
 » 3 weeks ago, # |   0 Hi. This round was great. I have a few doubts regarding problem C. Could you please explain how the time complexity is 2^22 (Like how 20 + 2) During the contest, I used the condition (a > 0), it didn't pass the test case. But, after watching Geothermal video, I added (a > 0+1e-9) and it got accepted. Why didn't (a > 0) work? Lastly, could someone also explain why scaling factor is used? How it works? Thank you very much for your time!