### JaySharma1048576's blog

By JaySharma1048576, 4 months 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 months ago, # | ← Rev. 2 →   -102 -
•  » » 4 months ago, # ^ |   +90 No wonder you are gray.
•  » » » 4 months ago, # ^ |   -41 Video editorial of 1.A. Exciting Bets 2. B. Customising the Track
•  » » » » 4 months ago, # ^ |   +5 your video was helpful to me . thanks
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   +11 Thanks. It means a lot :)
•  » » 4 months ago, # ^ |   -94 Problem C should be rejudged with eps = 0, author took esp = 1e-9 but 0 should have been taken ideally
•  » » » 4 months 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 months 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 :)
•  » » » » » 4 months 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.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 i didnt get it can u please explain what "exactly" i need to change in my code
•  » » » » » » » 4 months ago, # ^ |   0 you can change the if (a > v) to if (a > v && abs(a-v) > 1e-6).
•  » » » » » » » » 4 months 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
•  » » » » » » » » » 4 months ago, # ^ |   0
•  » » » » 4 months 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.
•  » » » » » 4 months 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 months ago, # ^ | ← Rev. 2 →   0 Sorry... I had a mistake in my code. eps=0 also works fine.
•  » » » » 4 months ago, # ^ |   0 Did you notice the variable "scale" in the tutorial?
•  » » » 4 months ago, # ^ |   0 I like your name.(not username , but name in profile). voyager
 » 4 months ago, # |   +15 you can find the explanation for my alternative solution for E in Tutorial: Part 1- Finding the Permutation.
 » 4 months ago, # |   -17 shit that was quick
 » 4 months 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 months ago, # |   -82 speedforces
•  » » 4 months ago, # ^ |   +5 yes, speedforces for those who solve only one problem in the round.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   -20 thought I could get wholesome rivalry, sorry for being cocky:/
•  » » » » 4 months 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 months 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 months 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 months 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 months ago, # ^ |   +7 If being lucky was the criteria for codeforces rating then I think all the LGMs should buy lottery tickets immediately.
•  » » » » » » » » » 4 months ago, # ^ |   +5 And Leo Messi would be newbie.
•  » » » » » » » 4 months 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.
•  » » » » » » 3 months ago, # ^ |   0 Painful but true :").
 » 4 months 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 months ago, # ^ |   +20 Typical cheater on codeforces lol
•  » » » 4 months 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 months 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 months 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 months ago, # ^ |   +1 Another wtf submission:Submission A — 00:06 Submission B — 00:09 Submission C — 01:40 Submission D1 — 00:53
•  » » » » » » 4 months ago, # ^ |   +5 Is this some sort of hack??
•  » » 4 months ago, # ^ |   0 XD WTF!
•  » » 4 months 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 months ago, # ^ |   +7 MikeMirzayanov Please ban these type of user immediately to set an example, humble request, Please :\
 » 4 months 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 months 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 months ago, # ^ |   0 How can we learn float precision skills ? How does float work ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Here geeksforgeeks article here
•  » » » 3 months 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.
•  » » » » 3 months ago, # ^ |   0 Could you please share that task you talking about. Thank you.
•  » » » » » 3 months ago, # ^ |   0 It was in a gym contest I'll have to search. I'll share when I find it.
•  » » 4 months 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 months ago, # ^ |   0 its the same case with int and Long long int its just a bigger set of bits to work on
•  » » » 4 months ago, # ^ |   0 Yeah why? also what does adding 1e-14 do?
•  » » » » 4 months 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.
•  » » » » » 4 months ago, # ^ |   +5 The same trick doesn't work if instead of adding 1e-14 we multiply by 1.00000000001 does multiplying not increase precision?
•  » » » » » » 4 months 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).)
•  » » 4 months ago, # ^ |   0 how's it hit or miss? they said 1e-6, i used 1e-6, first try
 » 4 months 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 months 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 months ago, # |   -56 ReadingStatementsForces
•  » » 4 months ago, # ^ |   +49 In what round do you not have to read the statement? April Fools??
 » 4 months ago, # |   0 When the proofs are by induction... you know it's either hit or miss.
 » 4 months ago, # | ← Rev. 3 →   +55
•  » » 3 months ago, # ^ |   +10
 » 4 months ago, # |   +11 Thanks for detailed editorial containing hints and multiple approaches.
 » 4 months 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 months ago, # ^ |   +7 Exactly that's also my question
•  » » 4 months ago, # ^ |   -13 0 is an integer and eps is a double , that is why using epsilon prevents precision errors
•  » » 4 months 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 months 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 months 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 months 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 months ago, # |   +157 If you didn't like the contest, don't downvote the editorial. Just downvote the announcement.
 » 4 months 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 months 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 months 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 months ago, # ^ | ← Rev. 3 →   +3 Try if(0.1 + 0.2 == 0.3)cout << "Yes"; else cout << "No";  This will print "No"
•  » » 4 months 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 months 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 months 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 months 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 months ago, # ^ |   0
 » 4 months 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 months 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 months ago, # ^ |   0 Oh I see, thank you!
 » 4 months ago, # |   +15 Language of C could have been better. Otherwise good problems(specially interactive ones)
 » 4 months 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 months 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 months 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 months 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 months 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.
•  » » » » 4 months ago, # ^ |   0 Thanks!
 » 4 months ago, # |   0 Question was too much complex
•  » » 4 months ago, # ^ |   0 True
 » 4 months ago, # |   +7 Please do not downvote this blog. Some people might be unable to find the editorial.
 » 4 months 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 months 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 months 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 months 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 months 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 months ago, # |   +6 Thanks for detailed editorial containing hints and multiple approaches！ ><
 » 4 months 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 months 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 months 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 months ago, # ^ |   0 The solution has #define int long long in the template.
•  » » » 4 months ago, # ^ |   0 Sorry. My bad.
•  » » 4 months ago, # ^ |   0 he/she has defined int as long long
 » 4 months 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 months 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 months 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 months 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 months 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 months ago, # ^ | ← Rev. 2 →   0 Got it . I was thinking about the probability of occuring the event all the time. btw Thank you
 » 4 months ago, # |   0 Why is this code https://codeforces.com/contest/1543/submission/121641823 fast? Shouldn't it get TLE? Are tests bad?
 » 4 months ago, # |   +10 C can be solved with DP in O((2/V)^3) or even O((2/V)^2) https://codeforces.com/contest/1543/submission/121629108
 » 4 months ago, # |   0 Well I overkilled B with some weird implementation 121633991
 » 4 months ago, # | ← Rev. 2 →   0 nevermind, got it
 » 4 months 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 months 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 months 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 months ago, # |   0 121621126 Can anyone help me why I'm getting TLE ? And help me to optimize it I have guess it's java, is'nt it? T-T I used python and it barely passed with same logic and its intended logic too T-T
•  » » 3 months ago, # ^ |   0 Yeah I guess so. Same happened to me, even though my algorithm is identical to Idea 2 in the tutorial.
•  » » 3 months 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.
•  » » » 3 months ago, # ^ |   0 Yes, even I saw that. But that's not fastscanner its superfast scanner XD. Thanks for mentioning.
 » 4 months 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 months 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 months 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 months ago, # |   0 Is the adaptive grader on problem D badly designed? https://codeforces.com/contest/1543/submission/121656699 gets accepted even though it has //if(r == 1) return; commented out.
•  » » 4 months 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 months 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 months 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 months ago, # ^ | ← Rev. 2 →   0 deleted.
 » 4 months ago, # | ← Rev. 3 →   +8 deleted.
 » 4 months 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 months 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?
•  » » » 4 months 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 xor If we take k-itwise xor with xi,k both side we get — xi,k (xork) x (xork) z = y (xork) xi,k z = y (xork) xi,k Therefore 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,k This can be simply proved if we think in terms of k-its In mth guess we will guess the number supposing original number was m-1 So, the order is password — xguess — 0new password(if guess wrong) — xi,k (xork) 0 = xi,k password — xi,k (xork) 0guess — 1i,k (xork) 0new password(if guess wrong) — (xi,k)i,k (xork) 0 = x (xork) 0 = x password — 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,k password — 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.
•  » » » » 4 months 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.
•  » » » 4 months 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 months 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 months ago, # |   0 can someone please tell me why its getting WA on C submission link — https://codeforces.com/contest/1543/submission/121660498
 » 4 months ago, # |   0 D1 is annoying, same algorithms but using Python will get TLE (maybe because output is so slow) really unfair.
 » 4 months 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 months 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 months ago, # ^ |   0 I really still don't understand why plus 1. Can you explain a bit more?
•  » » » » 4 months 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 months 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 months 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 .
•  » » » 4 months 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 months 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 months 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 months 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 months ago, # |   0 is this contest unrated ?
•  » » 4 months ago, # ^ |   0 I want to ask the same question. My rating hasn't changed, either.
•  » » » 4 months ago, # ^ |   0 most probably
•  » » 4 months ago, # ^ |   0 I wish so. May the ratings be with us.
 » 4 months ago, # |   0 Could anyone tell me why my rating hasn't changed?
 » 4 months ago, # |   0 Problem E can be found in YouTube.
•  » » 4 months ago, # ^ |   0 So is it unrated?
•  » » » 4 months ago, # ^ |   +8 Probably not.These two things are not related.
•  » » » » 4 months 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 months ago, # |   0 Dread it. Run from it. "math" arrives all the same.
 » 4 months ago, # | ← Rev. 2 →   0 Can somebody tell the time complexity of problem C in the simplest way? UPD: GOT it.
•  » » 4 months ago, # ^ |   0 btw I love the problem D1.
 » 4 months 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 months ago, # ^ |   0 oh i got it it was precesion error
 » 4 months 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 months ago, # | ← Rev. 2 →   0 Nice round although wasn't able to solve C but got to learn new concept of precision Handling today
 » 4 months 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 months 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 months ago, # |   0 Can anybody explain their thought process for D1?
•  » » » 4 months 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 months 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 months ago, # ^ |   0 Thanks man I get it now :)
•  » » » 6 weeks ago, # ^ |   0 You are the real boss among all the people who comments, the problemsetters and the editorialist.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Just think about D2, then restrict the solution to $k=2$.
•  » » » 4 months 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.
•  » » » » 4 months ago, # ^ |   0 The logic is basically the same, the only difference when $k=2$ is that $i \oplus j = i \ominus j$.
 » 4 months ago, # |   -8 Where my rating
 » 4 months ago, # | ← Rev. 2 →   -16 Orz
 » 4 months ago, # |   0 Problem B explanation with code: https://youtu.be/btqQYh7FXak
•  » » 4 months ago, # ^ |   0 Really helpful solution
 » 4 months ago, # |   0 Nice Tutorial
 » 4 months 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 months ago, # |   0 Could you guys help me with TLE on D1 with java? https://codeforces.com/contest/1543/submission/121703927
 » 4 months 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 months 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 months ago, # | ← Rev. 2 →   0
 » 4 months 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.
 » 4 months ago, # |   0 cannot understand solution of D2 any video suggestions ?
 » 4 months 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?
•  » » 4 months ago, # ^ |   0 Read this comment.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Nvm this explained it. https://codeforces.com/blog/entry/92582?#comment-813242 I 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)
 » 4 months 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?
•  » » 4 months ago, # ^ |   0 1e6 worked for me https://codeforces.com/contest/1543/submission/121735506
•  » » » 4 months ago, # ^ |   0 Your solution is almost same as the editorial solution, by which all the solutions are checked. I am asking the reason.
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   +1 Oh, thanks a lot. Learnt a new thing today.
 » 4 months 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 !
 » 4 months ago, # |   +5 bruh i tried to do a O(d^2) sol for C
 » 4 months 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.
 » 4 months ago, # |   0 The coloring part of problem E was posed here: https://codeforces.com/blog/entry/52918
 » 4 months 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.com/contest/1543/submission/121776211
 » 4 months ago, # |   0 JaySharma1048576 Can you please share the code of adaptive checker for D1 & D2?
•  » » 4 months 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."); } 
 » 4 months ago, # | ← Rev. 2 →   0 Can someone guide me to more problems like D2, dealing with non-binary base system. Thanks in advance !
 » 4 months 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!
 » 2 months ago, # | ← Rev. 2 →   0 Hey can somebody explain the reasoning behind the following behaviour? I am converting the floating numbers to integers by multiplying them with a constant (like 10^5, 10^7 etc). Constant = 1e7, setprecision(15) (Accepted) Constant = 1e5, setprecision(15) (Rejected) Constant = 1e7, no precision set (Rejected) Constant = 1e5, no precision set (Rejected) Can you please explain why this is happening particularly in this case? I get that recurring numbers (in binary representation) don't get stored exactly due to the recurring component but we would never end up in a recurring situation since 0.0001 would get divided at most once and become 0.00005. Hence the question about why 1e5 is not enough. Is it the case that the constant multiplication of the dp terms like c * p * p *.... and so on is causing the error to seep in? How do we decide the constant to scale the floating numbers in that case short of just experimenting and seeing what works?
•  » » 2 months ago, # ^ |   0 For this problem, if you see how the values may change during the whole process, you will notice that these values may get divided twice and not once (see this comment for more details). So, taking a scaling factor of $10^6$ or greater works here. If you take a factor of $10^5$, then one of the values of $\frac{a}{2}$ may not be an integer. For example, take (0.3000, 0.1000, 0.6000, 0.2001). After choosing C, the probabilities will become (0.0999, 0.20005, 0.70005, 0.2001). Now, if you choose M, the probabilities will become (0.199925, Invalid, 0.800075, 0.2001). So you can see that the probability of P became 6 decimal places.
•  » » » 2 months ago, # ^ |   0 Oh yeah, completely missed that. Thanks! :) However I still don't understand why 10^7 doesn't work without setprecision. Any why 10^6 fails with or without setprecision.
•  » » » » 2 months ago, # ^ |   0 setprecision controls how many decimal places you want to print. By default, it is quite less and since the maximum error allowed is $10^{-6}$, you need to set it to something more than 6 decimal places.
•  » » » » » 2 months ago, # ^ |   0 Okay, that makes sense. face palm Thanks for taking the time to replying! :) Really liked the questions! For anybody else who's wondering why won't 10^6 work with setprecision: try running long double a = 1.111; int one = 1e3; int aint = a * one; // aint = 1110...  Why? Because a in binary => 1.0001110001101.... (this is non recurring terminating but has 50-ish decimal places) one in binary would be 1111101000 a * one in binary would be 10001010110.1111011001000 when type casted to int aint in binary becomes just 10001010110 (the integer part of the result) and voila! that turns out to be 1110 in decimal. Disclaimer: I don't know much about how things work closer to the metal. Please let me know if I'm making a mistake somewhere.