### JaySharma1048576's blog

By JaySharma1048576, 4 weeks ago,

Hello Codeforces!

I am quite excited to invite you to my first ever round, Codeforces Round #730 (Div. 2) which will start on Jul/07/2021 17:35 (Moscow time). The round will be rated for participants of Division 2 (having rating strictly less than 2100). As always, Division 1 participants are welcome to participate in the round but it will be unrated for them.

The problems of this round will be themed on the 2005 video game Need For Speed: Most Wanted. You will be given 5 problems and 2 hours 15 minutes to solve them. One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round.

I would like to thank -

I tried my best to create interesting problems with clear statements, strong pretests and useful sample test cases. Make sure to read all of them. Good Luck and Have Fun. See you on the Blacklist ranklist.

The score distribution is here: $500-750-1500-(1000+1250)-3000$.

Disclaimer

UPD: Editorial

UPD: Congratulations to the winners

Div. 1 + Div. 2 -

Div. 2 -

First Solves -

A: Geothermal
B: Geothermal
C: rsabcmoi
D1: h0up1ngze
D2: Golovanov399
E: tfg

• +167

 » 4 weeks ago, # |   +125 As a true JaySharma1048576 stalker, I know he loves car racing games and there must be some non-binary search interactive problems in this round. spoilerburn out the wheels and tighten your seat belts, I know this round would be amazing
•  » » 4 weeks ago, # ^ |   -9 Indeed...appreciation for stalking skills.
•  » » 4 weeks ago, # ^ |   0 You can't be more accurate than that.
•  » » 4 weeks ago, # ^ |   -8 dude those are some next level stalking skillz
•  » » 4 weeks ago, # ^ |   0 How can someone be so accurate :)
 » 4 weeks ago, # | ← Rev. 2 →   +174 The scoring distribution definitely highlights the Need For Speed on the first few problems.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +17 I am afraid of getting my comment deleted but still I can't resist my hand. As difficulty of C is more than easy version of D . It is likely that rankings mostly depend on problem you solve :)
 » 4 weeks ago, # | ← Rev. 2 →   +89 As a tester, this round made me feel dumb. Also JaySharma1048576 and his love for interactive problems continues Context
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -31 tnks for the round :)
•  » » 4 weeks ago, # ^ |   +7 As a participant, this round made me feel so dumb.
 » 4 weeks ago, # |   +56 As a tester, I like problems!
 » 4 weeks ago, # |   +30 Early Score Distribution. Nice!
 » 4 weeks ago, # | ← Rev. 2 →   +22 How come this blog was not on the home page.
 » 4 weeks ago, # |   +39 Insane TLs because of NFS? :)
•  » » 4 weeks ago, # ^ |   +1 As a Java-main, I hope not! xP
•  » » » 4 weeks ago, # ^ |   +1 R.I.P python xd
•  » » 4 weeks ago, # ^ |   +9 C++ go brrrr
•  » » » 4 weeks ago, # ^ |   +6 assembly go bam bam
•  » » » » 4 weeks ago, # ^ |   +2 While that may be true, you can't submit assembly code on codeforces
•  » » » » » 4 weeks ago, # ^ |   +20 Then inline that assembly into C/C++.
•  » » » » » » 4 weeks ago, # ^ |   0 Genius
 » 4 weeks ago, # |   +4 SpoilerNothing much, just wishing You +ve∆
 » 4 weeks ago, # |   -71 Note the usual start time of the round
 » 4 weeks ago, # |   +7 Never solved an interactive problem in contest .i hope i solve one this time.
 » 4 weeks ago, # |   -9  .-'----. ,' . | \ | \ \ _ \ ,\ _ ,'-,/-)\ ( * \ \,' ,' ,'-) ._,) -',-') \/ ''/ ) / / / ,' 
 » 4 weeks ago, # |   +19 It's time to regain BMW M3 GTR from Razor !! :p
•  » » 4 weeks ago, # ^ |   0 kudyrtpaw
 » 4 weeks ago, # |   +4 I think C is going to be that one problem :)
 » 4 weeks ago, # |   +3 who is Razor? tourist?)
•  » » 4 weeks ago, # ^ |   -10 Right now, Benq is Razor.
•  » » 4 weeks ago, # ^ |   +19 I don't know who is Razor, but I am Sergeant Cross.
•  » » » 4 weeks ago, # ^ |   +11 Also may I ask, who is Mia ?
•  » » » » 4 weeks ago, # ^ |   +16 she is into a whole different sport now!
•  » » » » 4 weeks ago, # ^ |   0 My Love :)
•  » » » » 4 weeks ago, # ^ |   +5 She quit racing long ago.
•  » » » 4 weeks ago, # ^ |   0 Linkedin please
 » 4 weeks ago, # |   -40 SpoilerAs a tester, I need your support :)
 » 4 weeks ago, # | ← Rev. 2 →   +9 Hope I can do my best to become Specialist and break my curse in this rank. SpoilerDon't put me into the Blacklist please. :
•  » » 4 weeks ago, # ^ |   +3 all the best !
•  » » 4 weeks ago, # ^ |   0 I wanna break my curse too!! I hope it does. All the best!!
•  » » 4 weeks ago, # ^ |   0 Congratulations
 » 4 weeks ago, # | ← Rev. 3 →   0 Spoiler: ...
 » 4 weeks ago, # |   +4 Scoring distribution is giving me courage to participate in this round. I just have one confusion. Does the scoring distribution necessarily indicate that problem D is easier than problem C? Thanks for the contest!
•  » » 4 weeks ago, # ^ |   0 nope
•  » » 4 weeks ago, # ^ |   0 No.
 » 4 weeks ago, # |   +35 Time to revise kinematics.
 » 4 weeks ago, # | ← Rev. 2 →   -43 [Karavaiev][user:mcdx9524][user:Mazaalai][user:talibmohd][user:nnv-nick][user:DimmyT][user:andr0901][user:4qqqq][user:asrinivasan007][user:kassutta] Hey guys could you please tell me how do you get the opportunity to test a round as I also want to do so.I have participated in 80+ contests and my max rating is 1800+
•  » » 4 weeks ago, # ^ |   +18
 » 4 weeks ago, # |   +7 Pink slips instead of delta?
•  » » 4 weeks ago, # ^ |   +2 Was this an attempt to leak Problem C?
•  » » » 4 weeks ago, # ^ |   +1 I guess my name was not mentioned in the testers' list :(
•  » » » » 4 weeks ago, # ^ |   +1 Lol, yes. I double checked that to confirm.
 » 4 weeks ago, # |   +6 As a tester of this round, I can say problems are very interesting and new. But make sure to read all the problem statements carefully.
 » 4 weeks ago, # |   +65 As a Master, I am disappointed in my testing performance. GL to everyone
•  » » 4 weeks ago, # ^ |   +8 So it's going to be overly difficult and unbalanced for Div 2? Thanks for the warning I guess :/
•  » » » 4 weeks ago, # ^ |   +24 Not really, testers traditionally brick rounds pretty hard (speaking from experience).
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah but so do I :)
•  » » » » 4 weeks ago, # ^ |   +3 Now that the round is over, will you concede that I was right?
 » 4 weeks ago, # |   +2 Thank you for the ride. I knew you weren't blacklist material. But hey, where's your punk money now?
 » 4 weeks ago, # |   0 Sounds cool
 » 4 weeks ago, # |   +7 Last two contest were different level. Hoping that this round will give some confidence.
•  » » 4 weeks ago, # ^ |   0 Two "orange" testers have already said the round was very difficult for them, so don't get your hopes up...
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 it's rather unusual for testers to actually hint at the difficulty. Most of them are usually like it's a nice round, the problems are nice, or would like to have everyone participate.
•  » » » » 4 weeks ago, # ^ |   +18 As a tester, this round made me feel dumb. — yash_dagaAs a Master, I am disappointed in my testing performance. — DimmyT I interpreted this to mean this round will be especially difficult.
•  » » » » » 4 weeks ago, # ^ |   0 yes I meant these comments too. Nothing objectively indicates anything about the difficulty but even so such comments are rare to come from the testers :P
•  » » » » » » 4 weeks ago, # ^ |   0 Yeah I think it'll be a massacre but we'll see. I predict a few people who manage to solve 4+ problems will win big this round.
 » 4 weeks ago, # |   0 Pink slip from tourist
 » 4 weeks ago, # |   +110 .
•  » » 3 weeks ago, # ^ |   -10 I just saw errichto upvoted this. So I also upboted now.
 » 4 weeks ago, # |   +3 I also NEED some SPEED for a better rating.
 » 4 weeks ago, # | ← Rev. 2 →   +26
 » 4 weeks ago, # |   -25 After this round I hope I get a pink slip to Red rating.
 » 4 weeks ago, # |   -29 hope that won't be another MATHFORCES contest
 » 4 weeks ago, # | ← Rev. 3 →   +22 JaySharma1048576 the number $1048576$ is perfect and equal to $2^{20}$. Maybe we can expect some bit manipulation problems (or answer a binary search interactive in 20 queries), Its been a while since the last cool bit problem came :)
•  » » 4 weeks ago, # ^ |   -21 220 IQ? somewhat like 300iq.
 » 4 weeks ago, # | ← Rev. 2 →   -24 hope ,it would be amazing contest.
 » 4 weeks ago, # |   -91 hey can anyone help me with these problem link -- > linkits giving segmantation fault , so help me //SATYAM SINGH #include #include using namespace std; #define ll long long int #define pb push_back #define mod 1000000007 #define inf 1e18 #define ump unordered_map #define mp make_pair #define all(v) v.begin(),v.end() #define inpv(v,n) for(int i=0;i>v[i] #define outv(v) for(auto i:v) cout<=0;i--) #define log(args...) {string _s = #args ;replace(_s.begin(),_s.end(),',',' ') ; stringstream _ss(_s); istream_iterator _it(_ss) ; err(_it,args);} void err(istream_iterator it) {} template void err(istream_iterator it, T a,Args... args) { cout<<*it<<" = "<>v[1003]; int main( ) { clock_t begin = clock(); file_i_o(); // Write your code here.... ll n,m,k; cin>>n>>m>>k; ll ans = 1ll*n*m; mapmp; loop(i,0,k) { ll a,b,c; cin>>a>>b>>c; mp[a] = true; v[a].pb({b,c}); } ll empty = 0,p=0; for(auto i:mp) { sort(all(v[i.first])); } for(auto l:mp) { p=0; ll i=l.first; loop(j,0,v[i].size()) { if(v[i][j].first <= p) { if(v[i][j].second -p > 0) empty+=v[i][j].second -p; } else if(v[i][j].first >p) { empty+=v[i][j].second - v[i][j].first + 1; } p = max(p,v[i][j].second); } } log(ans); // code ends here !!!!!! #ifndef ONLINE_JUDGE clock_t end = clock(); cout<<"\n\nExecuted In: "<
 » 4 weeks ago, # |   -41 Binod
 » 4 weeks ago, # | ← Rev. 2 →   +9 after seeing the score distribution ,the theme for the contest Need For Speed: Most Wanted seems as a warning
 » 4 weeks ago, # | ← Rev. 2 →   0 Good luck and have fun to everyone!
 » 4 weeks ago, # |   +2 see you on the blocklist. what a nice joke along with warning.
•  » » 4 weeks ago, # ^ |   0 Everything is fun and games until your 2 liner "A" matches with someone else.
 » 4 weeks ago, # | ← Rev. 2 →   -14 Proud moment for JaySharma1048576
 » 4 weeks ago, # |   +2 The pun, see you on the Blacklist, XD lmao
•  » » 4 weeks ago, # ^ |   +2 lol
 » 4 weeks ago, # |   +86 Wishing you all high rating!
 » 4 weeks ago, # |   +4 Seriously?? Based on the theme Need for Speed!! Am so hyped up now. Let me take on Razor once again before participating in the contest.
 » 4 weeks ago, # |   -13 Hope this one has better problems than the previous one . Coz previous one just had math and constructive algo !
 » 4 weeks ago, # |   -9 HI
 » 4 weeks ago, # |   0 go green brrrrr :>
 » 4 weeks ago, # |   -7 A B will surely be speedsolving.C will decide everything
•  » » 4 weeks ago, # ^ |   -7 Don't forget D part1
•  » » » 4 weeks ago, # ^ |   -12 oh yeah...D1 will be interactive
•  » » 4 weeks ago, # ^ |   0 Now we know the answer.
 » 4 weeks ago, # |   +8 Now it's time to increase my rating...
 » 4 weeks ago, # |   0 Me after not being able to solve even 1 problem: No longer Wanted :)
•  » » 4 weeks ago, # ^ |   0 Well....this tweet DID age well :(
 » 4 weeks ago, # |   0 hope i can solve a problem today
 » 4 weeks ago, # |   0
 » 4 weeks ago, # |   0 I am getting nervous. I only want that +19. :(
•  » » 4 weeks ago, # ^ |   +1 I am getting nervous. I only want that +29. :(
•  » » 4 weeks ago, # ^ |   +13 you better not think about it and just enjoy the problems when I became expert i wasn't tying to be expert I was just trying my best
 » 4 weeks ago, # |   +1 I am only +34 away from specialist.I am little nervous.But once I started from 0.I should remember that.Good luck everyone!!!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Just remember that there were people with +1 away from their desired rank. Just a reminder. :)
•  » » » 4 weeks ago, # ^ |   0 Yeah.That's why Let's just enjoy the contest.Nothing is above than that
•  » » » » 4 weeks ago, # ^ |   0 if you don't think about the rating, that's when you really grow.
•  » » » » » 4 weeks ago, # ^ |   0 yup
•  » » » » » 4 weeks ago, # ^ |   +3 Somewhere there is a child in every man, that doesn't grow.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 still +14 away
•  » » » » 4 weeks ago, # ^ |   0 You'll get there. Don't lose hope.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah.Actually the thing is I am tired after a 30 days streak of practice.That's why after I become specialist I can give few days rest to my brain, get freshened up and plan for becoming expert.That is why I am so desperate to become specialist fast before I go on for a few days break.
 » 4 weeks ago, # | ← Rev. 2 →   -7 This round is going to be Speedforces
•  » » 4 weeks ago, # ^ |   0 Need for SPEED.
 » 4 weeks ago, # |   0 I want some jerking acceleration for the first few problems, Hope not to get crashed or thrashed-->.
 » 4 weeks ago, # |   -38 Even tourist is participating in this contest
 » 4 weeks ago, # |   +1 Need for speed got many give a wrong attempt on A. :-)C so tough that ranking is really based on Speed of A and B :-(
 » 4 weeks ago, # |   0 Am I the only one who was banging my head against a wall trying to understand the fourth problem? Great contest!
•  » » 4 weeks ago, # ^ |   0 Me as well. How did >2.7k people solve it :/ Lets wait for the editorials!
•  » » 4 weeks ago, # ^ |   0 It's just somewhat well known that a ^ x = y also means a ^ y = x, or any other rearrangement. Alternatively you can blame it on cheaters I guess.
 » 4 weeks ago, # |   +39 I just wanna know, why ???????Why god why ?
 » 4 weeks ago, # |   +9 Am I the only one who is having hard time to understand problem C
•  » » 4 weeks ago, # ^ |   0 NO...
 » 4 weeks ago, # |   -39 I love this contest.
 » 4 weeks ago, # |   +22 I should've skipped this contest
•  » » 4 weeks ago, # ^ |   -13 This thinking wont take you much further . Thats the real standing as of now you will know after the current contest instead you skip the contest. All the best :) Its near to 50 min left in the contest you can try it :P
 » 4 weeks ago, # |   +58 Problem Statements seem too much messy.
 » 4 weeks ago, # |   +93 Bad contest! No interesting ideas.
 » 4 weeks ago, # |   +4 welp, late registration, and failed to solve anything. I will hold the L for now and practice more xd.
 » 4 weeks ago, # | ← Rev. 2 →   +8 Not able to understood anything after solving problem A and B . C and D are bit mess
 » 4 weeks ago, # |   -12 better contest :))
 » 4 weeks ago, # |   0 Speedy MathForces,as expected!
 » 4 weeks ago, # |   +30 C is totally a mess!!
•  » » 4 weeks ago, # ^ |   +4 You could convert all the doubles/long doubles into long long int/int and then do a dp after that
 » 4 weeks ago, # |   +96 Props to all the contestants who can imagine a hypercube in their brain.
 » 4 weeks ago, # |   0 Any faster alternative to flush operations besides switching to c++ (for java users?) Had no idea why I was tleing until I switched to c++ real quick
 » 4 weeks ago, # |   +37 Mathforces and Messforces
 » 4 weeks ago, # |   0 I tried to wrote a DP solution for C but failed.I think we can solve this with tracking values(recursion type).
•  » » 4 weeks ago, # ^ |   +1 That's what I did. Link You just have to be careful when converting the doubles/long doubles into integers I think.
•  » » » 4 weeks ago, # ^ |   0 GoodI was thinking of recursion while implementing my dp solution but i was too late.
 » 4 weeks ago, # |   0 Is it just me or was A harder than B and D1?
•  » » 3 weeks ago, # ^ |   0 It's just you
 » 4 weeks ago, # | ← Rev. 15 →   -25 How to think for problem C and D1? How to get that idea? What's the approach?
•  » » 4 weeks ago, # ^ |   -12 lower bound on v is 0.1, so at every step at least 0.05 probability is transferred to P so 2^20 recursive calls at max as a very very loose upper bound, alternatively set like 1e-12 epsilon since only 1e-6 is needed to pass
•  » » 4 weeks ago, # ^ | ← Rev. 12 →   0 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) with a little adjustments for when c or m is 0
•  » » 4 weeks ago, # ^ |   +35 It's not very nice to edit your comment's meaning after posting, now you make all the people who replied about problem C look silly lol.For D, we have $n$ queries and $n$ possible candidates for the password, so we're able to check every single candidate, which is the maximum amount of information we could hope for on this problem. To deal with the password changing, we just need to apply the same transformation to the new queries. Let's say the original password was $x$, and now it is $f(x)$. Then if we want to ask if $x = 1$, we should instead ask $f(1)$. For D1, the $f$ function is just xor of all previously asked queries, because the inverse of xor base 2 is itself.
•  » » » 4 weeks ago, # ^ |   0 Sorry, I thought it was problem C as I was solving it after A,B, I immediately tried to edit it.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 First of all you need to know that if (a xor b)= c then (a xor c) =b.Now you can run a loop for all the possible initial passwords ie [0,n-1] and check if the password was initially x then what would be its value right now considering all your previous guesses. Which means xor this x with all previous guesses which u can store in a variable and keep updating it on each step.
 » 4 weeks ago, # |   0 In C , can someone explain me , why only adding setprecision(9) gets the same code accepted , where as without setprecision same answer is treated as wrong answer. Is there any rule for how many digits is shown after decimals if I simply print a double variable without setprecision. Also , is this feature compiler dependent?
•  » » 4 weeks ago, # ^ |   0 I am pretty sure the default precision is upto about 6 decimal places, so in problems like this you have to make sure you manually set up your precision. Had suffered a lot of WA because of that once :(
•  » » » 4 weeks ago, # ^ |   0 Exactly , thats what I use to think till now. And thats why I didn't mind writting it explicitly in the code bcz the error was asked to be kept less than 10^-6. But guess what , I think it is not upto 6 digits , because today I suffered atleast 10 times without setprecision and same code passed now.
•  » » » » 4 weeks ago, # ^ |   0 Well, precision is upto 6 significant digits not up to 6 decimal places. I got lot of WA's bcoz I thought both things meant the same.
•  » » 4 weeks ago, # ^ |   +3 because if you dont c++ can decide not to output 9 digits of precision. im not sure what are the guidelines for this but if you do the test cases there is a good chance when you actually print the numbers there will be less than 6 decimal digits, and for the answer you need at least 6 as the minimal error allowed is 10^-6
•  » » » 4 weeks ago, # ^ |   0 Yeah , correct. I missed this today and realised it so late. In the last input of Sample Test Cases , without setprecision , the compiler prints 4.26016 and misses the 6th digit. I guess , its definitely not 6 decimal points by default.
 » 4 weeks ago, # | ← Rev. 6 →   -11 C was a good problem but can anyone explain how this gets WA and this gets AC.
 » 4 weeks ago, # | ← Rev. 3 →   +6 Could anyone help me know why am I getting WA on case 3 of pretest 1? Is it an implementation error or is it some floating-point precision trick that I am missing? https://codeforces.cc/contest/1543/submission/121640564Edit: instead of if(c>v) use if(c-v>1e-6). RIP.
 » 4 weeks ago, # |   +5 What was that C? I spent a long time trying to understand that statement, please provide more clear statements next time,and also how to solve it? I didn't like any of the problems of this contest.
•  » » 4 weeks ago, # ^ |   +1 I spent more than half an hour to understand the problem C !!
•  » » » 4 weeks ago, # ^ |   +7 This round is even worse than the last one.
•  » » » » 4 weeks ago, # ^ |   +1 you are right
 » 4 weeks ago, # | ← Rev. 3 →   +19 Damn, I knew this round was going to be garbage based on the tester comments but I decided to try it anyway. RIP my rating.
 » 4 weeks ago, # |   +3 How to solve C if 0 < v < 1? Is there only math solution?Btw, my C was incorrect due to big eps, it forced me to use__float128.
•  » » 4 weeks ago, # ^ |   0 yeah, even long double didn't work for me. they should consider solutions with higher relative errors too.
•  » » 4 weeks ago, # ^ |   0 Why not using esp to eliminate precision error?
 » 4 weeks ago, # |   +82 Me entire round:
•  » » 4 weeks ago, # ^ |   0 when author wants you to guess the solution
•  » » 4 weeks ago, # ^ |   +25 Those are rookie numbers : _
•  » » » 4 weeks ago, # ^ |   +3 You gotta pump those numbers up
•  » » 4 weeks ago, # ^ |   +3 WA on test 1 because "The initial password chosen was 3", in the example test case was 2.
 » 4 weeks ago, # |   0 How to sole the problem C ?
 » 4 weeks ago, # |   0 I want to now why the third part of the sample in problem C is always a little different ?
•  » » 4 weeks ago, # ^ |   +8 maybe you didn't control the condition like if(c>eps)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Could you elaborate?Edit: instead of if(c>v) use if(c-v>1e-6)
 » 4 weeks ago, # | ← Rev. 2 →   +3 During the contest I solved D1. Then I tried to solve D2 but my solution got TLE. I changed my solution and tried again, but accidentally I sent my solution to D1 instead of D2. And unfortunately the system considered that as a resubmission. :(
 » 4 weeks ago, # |   +1 For C, i got the correct answer but relative error is more than 10^-6. How to solve this issue?
•  » » 4 weeks ago, # ^ |   +5 I solved that by assuming $0 = 10^{-6}$
•  » » » 3 weeks ago, # ^ |   0 Can you explain why that works?
•  » » » » 3 weeks ago, # ^ |   0 I was using long double and because of floating point exception even if a number was supposed to be $0$, it can be something like $10^{-16}$. So I compared it with $10^{-6}$ instead of $0$.
•  » » 4 weeks ago, # ^ |   0 same
•  » » 4 weeks ago, # ^ |   0 You can use the function of precision: Codecout.setf(ios::fixed | ios::showpoint);cout.precision(x);Here in the brackets instead of "x" you can write what decimal you want.
 » 4 weeks ago, # |   +18 All excitement for interactive went in vain.
 » 4 weeks ago, # |   0 how to solve D1 ?PLZ EXPLAIN IN DETAIL
•  » » 4 weeks ago, # ^ |   +6 dont worry buddy :)Since we can guess n times let's try guessing for each of the n possible first passwords.Obs 1: if the password is p and we're guessing the password q then the newpassword is actually p^q (^ in this case is bitwise xor)Obs 2: we can mantain all of the changes we did to the starting password before a certain point. If we guessed the numbers 1 and 2 before and the starting password is x, then the starting password was x, then it was x^1, then it became x^1^2, so we can store 1^2^.... as we go onWhat we are actually going to do is let xr be the changes we did to the starting password, then make a loop from 0 to n-1 and for each iteration we will guess xr^i. If the feedback is equal to 1, then we got it right. Otherwise, since we guessed xr, the new xr will be xr^xr^i = i. We can do that in O(N) with no problems (i assume the solution is the same for d2 but i didnt have time to debug my code for it)
 » 4 weeks ago, # |   +1 Never do P(a) > v .. while dealing with doubles ! NEVER
 » 4 weeks ago, # |   0 For problem C, to get a AC, I should have been imprecise :))
•  » » 4 weeks ago, # ^ |   0 can you elaborate
•  » » » 4 weeks ago, # ^ |   0 Okay. I was using c!=0 , m!=0 and p!=0 at various places.This was causing issues because, at the end my answer varied from the expected answer by 10^-4.I should have instead used c>=1e-6, m>=1e-6, p>=1e-6.The former fails, but the latter passes :))
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 wow, this is terrible. now im wondering if the original test cases were actually imprecise, and they thought the program would just run for a really long time if they didnt do thisedit: it's most likely some floating point nonsense
•  » » » » 3 weeks ago, # ^ |   0 Is this because c or m might be equal to 0, but because of floating point precision error, maybe it is a very small number, Not exactly equal to 0,: 1e-6 or something, so checking for inequality always results in true. I don't see why I should deliberately be ignoring 1e-6 from the values like c or m.
 » 4 weeks ago, # |   +13 How can I solve for the fractional error in the C problem (I'm having trouble with the third in sample 1, which is 5.00573 all the time)? Even with long double, the precision was not enough...
•  » » 4 weeks ago, # ^ |   +1 Yeah, i got the same issue, can we request author to consider these kind of solutions?
•  » » » 4 weeks ago, # ^ |   +13 The whole "point" of the problem is to use some stupid trick to avoid floating point error. Apart from that it's just trivial implementation.The thing is, I guess most people who used the trick are just using "cargo cult programming" and would not be able to prove the correctness of their solution.So basically it's a problem that only stupid people who know the trick, or geniuses can solve.
•  » » » » 4 weeks ago, # ^ |   0 I just assumed a good error would be 1e-8 so instead of checking if it's over 0 I checked if it's > 1e-8... And then prayed a lot that I don't FST because I would have needed 1e-7 maybe.
•  » » » » » 4 weeks ago, # ^ |   0 Exactly, you fall into the category of people who know the trick but don't know why it works.
•  » » » » » » 4 weeks ago, # ^ |   0 I mean, double has a particular precision. That's because doubles are represented internally as exponent and base as binary, with a set number of bits. Obviously you can't write any number and what can be an "finite" number (with a finite number of decimals) in decimal might be an "infinite" in binary and vice versa. That means that there is an error in representation of a number past a certain precision so you might say 1.6565*10^(-7) but actually it gets approximated as 1.656565...*10^(-7). Double guarantees just some decimals to be correct. But yeah, I wouldn't know how to pull the exact number for the error. Adding up numbers can have some effect on the error while multiplying them can have some other effects on the error. That's much more in depth than cargo cults...
•  » » » » » » » 4 weeks ago, # ^ |   0 Writing some code without understanding how/why it works is the definition of cargo cult programming.
•  » » » » » » » » 4 weeks ago, # ^ |   0 You didn't even solve C. Please give me the mathematical proof for which it would be a particular number for the threshold. Because that's literally the only thing I don't know for sure.
•  » » » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Nevermind I think it's anywhere between 1e-5 (the probabilities are given with 1e-4) and 1e-14... since double is 1e-15 and we would have about 10 additions at most so 10 times the error.
•  » » 4 weeks ago, # ^ |   +1 Assuming that precision isn't the problem (and I can't see your submission yet), you may need to do cout.precision(12) before outputting. You can also do cout << setprecision(12) but that needs (and not everyone uses bits/stdc++.h)
•  » » 4 weeks ago, # ^ |   +5 Since comparing doubles is messed up, try something like (c-v)<=1e-6 instead of c<=v
•  » » 4 weeks ago, # ^ |   0 you should not compare doubles as integers a < b || a — b <= 0.000001 instead of a <= b should work
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I changed eps from 1e-20 to 1e-9 and 5.00572993744602889486 turned into 5.00505077652118574591. Didn't submit C because of this. Isn't my solution more precise?
•  » » » 4 weeks ago, # ^ |   +3 exactly
•  » » » 4 weeks ago, # ^ |   0 1e-20 is ridiculously low. Doubles only have precision for 1e-15.
•  » » 4 weeks ago, # ^ |   +9 I got the same issue too. I think the third set of examples in question C has accuracy problems If we think that a number is Invalid, we set it to -2.0 and think that a number less than -1.0 is Invalid, we will get the answer 5.005729937446. I think this is more accurate than directly judging whether the number is greater than 1e-6.
 » 4 weeks ago, # |   0 Solution for D:Test $0$.for $1 \leq i < n$, try $2^{\textrm{ctz}(n)+1}-1$ (take the number of trailing zeros, add one to it, and test the number with that many ones in binary)How I came up with it:I tried small cases by hand, found that $"0\ 1\ 3"$ worked for $n = 3$, $"0\ 1\ 3\ 1\ 7"$ worked for $n = 5$, and then generalized the pattern.
 » 4 weeks ago, # |   +9 Is it even possible to get AC on C with bitmasking? The precision error never left me. And all the top position in standing Reds seem to have used recursion.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 https://codeforces.cc/contest/1543/submission/121654469 Yes. Sadly, I didn't submit it because I had a precision error on the third sample test.
 » 4 weeks ago, # |   +9 using double in C: relative error is like 10^3 using long double in C: relative error is like 10^4fuck me i guess
 » 4 weeks ago, # |   +11 C was the worst question ever asked on Codeforces. 1e-6 is never equal to 0. I don even understand how this question was even allowed for a rated codeforces round.
•  » » 4 weeks ago, # ^ |   +5 What do you mean by 1e-6 is never equal to 0?
•  » » » 4 weeks ago, # ^ |   -20 Why can't we take 1e-18 to be equal to 0. It's not a lesson for me, it's the stupidity of setters.
•  » » 4 weeks ago, # ^ |   +30 You should know that double numbers are dangerous. If you don't, this is a good lesson for you.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Maybe this proves something code here
 » 4 weeks ago, # |   +31
 » 4 weeks ago, # |   +87 3 things I learned after the round: Use a > 1e-9 instead of a > 0. Use a > 1e-9 instead of a > 0. Use a > 1e-9 instead of a > 0.
•  » » 4 weeks ago, # ^ |   0 bruh, literally this changes answer from 5.0301143 to 5.0050777 ?? xD thats like 0.025 difference, yo?anyway goodbye candidate master
•  » » » 4 weeks ago, # ^ |   +4 Same error! Good lesson for comparison of real numbers XD.
 » 4 weeks ago, # |   0 Does greedy colouring not work on E? Otherwise what is TC 4?
 » 4 weeks ago, # |   +53 Me while reading C
 » 4 weeks ago, # |   +17 can anyone explain this coding style.....hope everyone get what I am trying to convey
•  » » 4 weeks ago, # ^ |   +1 ant++,wasp---
•  » » 4 weeks ago, # ^ |   0 I think when real hackers hack the codes like this they try hard to find the main code.
•  » » » 4 weeks ago, # ^ |   +1 haha++ hacker_work++
•  » » 4 weeks ago, # ^ |   +1 These are just ways to bypass plagiarism. I guess by now, its a well known fact that there are telegram groups and youtube channels which leak the solutions during the contest and people like this (author of this code) just copy and do this stupidity to not get banned.
 » 4 weeks ago, # |   +8 Me after solving A and B
 » 4 weeks ago, # |   0 Every one is talking about problem C , is there any body like me who couldn't solve the problem A
•  » » 4 weeks ago, # ^ |   0 me :Dmathforces let's go!
•  » » 4 weeks ago, # ^ |   0 Me as well༼☯﹏☯༽
•  » » 4 weeks ago, # ^ |   0 For me A was much harder than B. Solved it, but wasted a lot of time and also felt really nervous waiting for system tests.And I did fail solving problem A in one of the older contests too. That's nothing to be proud about. Just shows that more training is necessary for these particular types of problems.
 » 4 weeks ago, # |   -7 I swear I'll never give any writer's first contest.
 » 4 weeks ago, # | ← Rev. 2 →   +6 Who can tell me why java8 made D1 overtime.My algorithm is the same as others.
•  » » 4 weeks ago, # ^ |   +3 Try reading bytes directly from System.in instead of wrapping it with BufferedReader and InputStreamReader.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 directly?by Scanner? I submitted the same code with C，ac .= =!!!(f**k)
•  » » » » 4 weeks ago, # ^ |   0 I think Scanner is slow, you can try with my FastReader class: https://codeforces.cc/contest/1543/submission/121654156For non-interactive problems I wrap System.in with BufferedInputStream.
•  » » » » » 4 weeks ago, # ^ |   0 wow！thank
 » 4 weeks ago, # |   -11 The problems were as bad as getting tle on test case 47
•  » » 4 weeks ago, # ^ |   +3 TLE on 47 is ok if you are tourist
 » 4 weeks ago, # |   +31 We want old codeforces back. It was used to be so much fun.(⋟﹏⋞)(╥_╥)
 » 4 weeks ago, # |   +7 I read Problem C at least 10 times.but I couldn't understand what type of probability was that?
 » 4 weeks ago, # |   +1 Can anyone who passed pretests on C tell the number of pretests on that problem?
•  » » 4 weeks ago, # ^ |   +8 I believe problems A, B, C, and D1 had 3 pretests each.
•  » » 4 weeks ago, # ^ |   +8 A, B, C and D1 had 3 pretests each, D2 had 7 pretests and E had 16 pretests.
 » 4 weeks ago, # |   +17 can anyone explain me what was problem C(problem statement) in human language, pls ?
•  » » 4 weeks ago, # ^ |   +8 you have a chance to get one of 3 things a,b and c, each with probability pa, pb, pc. if you get a or b, you keep getting more things, but when you get c you stopin addition, if you get a or b, the probability of it decreaces by v, and that ammount is distributed to the other things. for example, if pa = 0.2, pb = 0.2, pc = 0.6 and v = 0.1, if you get a the new probabilities will be pa = 0.2 — 0.1 = 0.1, pb = 0.2 + 0.1/2 = 0.25, pc = 0.6 + 0.1/2 = 0.65.i think i have a solution if you want but floating point nonsense screwed me really hard in the contest
•  » » » 4 weeks ago, # ^ |   0 Thanks man, I got the solution also. Understand the problem statement seems hard than actual solution for me.
•  » » » 4 weeks ago, # ^ |   0 This helped me too, Thanks
 » 4 weeks ago, # |   0 I just don't understand why my code for C outputs correctly on my computer but wrong on codeforces,I don't understand why 0.6*10000 on my computer is 6000 but on codeforces 5999
•  » » 4 weeks ago, # ^ |   +1 i think this is because trying to parse 0.6 into binary gives an infinite decimal, so depending on how the implementation of the multiplication is in your computer and on codeforces computers you can get either answer
 » 4 weeks ago, # | ← Rev. 10 →   -59 please make it unrated i beg u , my college exam has turned me into a punching bag why was probability explained properly in big shitty text everytime it was 1.000000
 » 4 weeks ago, # |   +58 JaySharma1048576 : I tried my best to create interesting problems with clear statementsclear statements??? you sure?
•  » » 4 weeks ago, # ^ |   0 What was unclear?
•  » » » 4 weeks ago, # ^ |   +52 Statements
 » 4 weeks ago, # |   0 https://codeforces.cc/contest/1543/submission/121632020why this is wrong?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 long long, while n and n-x can be regular integers, nothing is bounding n*(n-x) to be smaller than 1e9
•  » » » 4 weeks ago, # ^ |   0 I have defined long long as int only
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +17 my god... my dear god...1- stop using defines, it's for your own good2- if you're going to use defines, define it without conficting with existing typenamesnot only defines do strange behavior because it's litterally copypasting what it's defined in the code but there are infinitely more predictable alternatives like typedef for types, functions for things like your "TotalSum" and const int for values.Do that and your code will work, there is some evil black magic fuckery going on with it.edit: it turns out the problem was not what i said but i still stand by it. If all of the evil stuff wasn't going on, it would be obvious what to pinpoint what was actually wrong with your code because the only thing that could go wrong is the function you didn't write, accumulate
•  » » » » » 4 weeks ago, # ^ |   0 Gotcha.. Will keep this in mind
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +11 The type of the returning value of accumulate() is the type of the third parameter. In your code you used 0, which is by default an int. In this case you should use 0LL.Note that the type always depends on the third parameter only. So if A is vector long long, accumulate(A.begin(), A.end(), 0) is still wrong.
•  » » » 4 weeks ago, # ^ |   0 Ohhh damnn.. Thank you
 » 4 weeks ago, # | ← Rev. 2 →   +14 It wasn't really good. The difference between B and C was very huge. It could be better
 » 4 weeks ago, # | ← Rev. 2 →   +7 So fun contest! Cars, racing, hacking... Very thanks to the authors! It's was really cool.
 » 4 weeks ago, # |   +31 Thanks for the round! For anyone interested, here's a link to my screencast.
 » 4 weeks ago, # |   +7 Woke up half an hour before the contest , gave it , and now i think i should have slept instead.
 » 4 weeks ago, # | ← Rev. 2 →   0 I didn't put the break condition if the solution is found but the main tests passed. How is that possible ?
•  » » 4 weeks ago, # ^ |   +3 the judge is adaptative, so it will try to "change" the initial password to see if you can guess all of them. so the judge is like "let's say the initial password is 0" and you get it right, then it says "let's say the initial password was 1 instead" until you get to the last one.
 » 4 weeks ago, # |   0 No matter you think this round is interesting or not, honestly, it's a different round.
 » 4 weeks ago, # |   -6 Solved 4 Question after long time.. Expert Again!!!
 » 4 weeks ago, # |   0 cf predictor: +60 me: :D
 » 4 weeks ago, # |   0 when will hacking start?
 » 4 weeks ago, # |   0 When I implemented my solution for problem C, it printed 4.263965352 for the subtest 4 of test case 1 but it got AC when I submitted. My submission is here. I tried to run that test on AtCoder as well and it gave the same result. I even tried to run some AC codes with that test and the results were also the same. The output of that test case on Codeforces was 4.260163674, so weird. Is there any problem with the compiler?
 » 4 weeks ago, # |   0 Apart from B, I literally found every problem quite challenging :(
 » 4 weeks ago, # |   +10 Actually, for problem B it's much easier to prove that the cars have to be as evenly as possible. You can assume that array a is sorted withouth losing the generality of the problem, so when you do the sum of modules you will get a2-a1+a3-a1+..+an-a1+...+an-an-1. It's very easy to see that a1 comes with the most negative signes in front, then comes a2, then a3, and so on. So in order to minimize the total sum you need to have a1 as big as you can,..., an as low as you can. But initally you assumed that a1<=a2<=a3<=...<=an. So it's now obvious that you must distribute the cars as evenly as possible.
 » 4 weeks ago, # |   +7 poor english and bad google translation caused me fail to understand what pC was talking about
 » 4 weeks ago, # |   +3 That was fun. Sweet and viscous masochistic fun. It's becoming a painful habit without Educational Rounds.
 » 4 weeks ago, # |   +9 I think LordVoldebug is a Div1 contestant and you mean LordVoIdebug, winning the 4th place. Wow, they are the same person xD
•  » » 4 weeks ago, # ^ |   +5 Sorry. I misunderstood l instead of I` in his username. Both of them look so similar.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -6 Thanks for a round, especially for problems D and E — surprisingly simple, yet challenging and mind-bending.
 » 4 weeks ago, # |   +13 Couldn't even get A right... I suck
 » 4 weeks ago, # | ← Rev. 2 →   0 Nice
 » 4 weeks ago, # | ← Rev. 2 →   -21 These problems will make you a fan of the problemsetter JaySharma1048576 and remind you of the legendary nfs for sure..
 » 4 weeks ago, # |   -15 I loved this round, it's one of the best I've seen :)
 » 4 weeks ago, # |   0 I am newbie class with low contest rating (891), but I scored 1812 in the contest. I would have expected some rank points. Does anybody know why I am not getting any?
•  » » 4 weeks ago, # ^ |   0 The user ratings hasn't been updated yet for today's content. If you see the final standings, there should be rating update tab.
•  » » » 4 weeks ago, # ^ |   0 Can't locate that tab, but thanks for the clarification, I guess it's just a matter of time.
 » 4 weeks ago, # |   +14 its been 10 hours and still rating is not been changed
 » 4 weeks ago, # |   0 I think the problems will be better if they have no or shorter story backgrounds.Anyway, it is a good contest!
 » 4 weeks ago, # |   0 Is the content unrated?
•  » » 4 weeks ago, # ^ |   0 "The round will be rated for participants of Division 2 (having rating strictly less than 2100)."
•  » » » 4 weeks ago, # ^ |   0 Then why my rating is not changed at all?
•  » » » » 4 weeks ago, # ^ |   0 It will get updated soon. Don't worry.
 » 4 weeks ago, # | ← Rev. 2 →   -22 Why my rating is not increase or decrease in Codeforces Round #730 (Div. 2) as I solve 3 out of 6 questions with a standing of 1863. What's the criteria of rating increment.
•  » » 4 weeks ago, # ^ |   +11 nobody got their rating changes yet, relax
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +25 You did not solve bro . You cheated . Your Submission to this problem clearly has a message "forwarded from" in the first line itself . Cheaters like you should be banned .
•  » » » 4 weeks ago, # ^ |   0 what it means by forwared from ? means copy paste?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +7 his submission has this line "forwarded from" in the first line and he got a compilation error due to that . someone might have sent him the solution somewhere and he just copy pasted it and with the message he also copied and the forwarded thing that appears when someone forwards you a message in some chat apps . Hence , caught XD ...
•  » » » 4 weeks ago, # ^ |   +3 Yep. Quite similar to this solution (taking out all the ants and wasps)
•  » » » 4 weeks ago, # ^ |   +43 Pure comedy gold, this needs to be framed and kept in eternity
•  » » 4 weeks ago, # ^ |   +6 Hahaha cheater caught
•  » » » 4 weeks ago, # ^ |   0 sir I changed my device That's why it shows forwarded from . I submit this question through mobile.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You didn't think Cheating was gonna get caught?
•  » » » 4 weeks ago, # ^ |   0 sir that's the truth whether you believe or not I don't care
•  » » » » 4 weeks ago, # ^ |   +10 well, the number of skipped submissions in your submission history is the proof that u are a cheater. So please do not try to explain .
 » 4 weeks ago, # |   +31 Why rating change take so long?
 » 4 weeks ago, # |   +8 To me this round is a little bit hard compared to the previous rounds... I think
 » 4 weeks ago, # |   0 can anyone explain why on clicking my underrated contest this contest is showing up there?does it mean it is unrated?
 » 4 weeks ago, # |   0 Now its time to increase my rating...
 » 4 weeks ago, # |   0 can anyone explain why at n=1 in problem B answer is 0?
•  » » 4 weeks ago, # ^ |   +1 Inconvenience is defined as the absolute difference between each pair of subtracks. If n==1, there is only one subtrack and hence no pairs => inconvenience = 0.
 » 4 weeks ago, # | ← Rev. 2 →   0 Is the round unrated for some reason?
 » 4 weeks ago, # |   +1 Can someone please tell me if this round is unrated??
 » 4 weeks ago, # |   +2 is this contest unrated?
 » 4 weeks ago, # |   +61 The ratings have been preliminary updated. Later, I will remove the cheaters and recalculate the ratings.
•  » » 4 weeks ago, # ^ |   -12 Sorry to ask this but what are all the methods you use to identify cheaters , thank you
 » 4 weeks ago, # | ← Rev. 4 →   -41 Orz
 » 4 weeks ago, # |   0 looking at the standings, me who did not participate in this round, telling myself " dude what happened here!"
 » 4 weeks ago, # | ← Rev. 5 →   0 This D1 solution was accepted https://codeforces.cc/contest/1543/submission/121690053Is it time to move to C++? the last one even passed the pretest...
•  » »