Блог пользователя JaySharma1048576

Автор JaySharma1048576, 5 лет назад, По-английски

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 -

  1. Geothermal
  2. Golovanov399
  3. SSRS_
  4. uwi
  5. tfg

Div. 2 -

  1. h0up1ngze
  2. olmrgcsi
  3. nicalvarez
  4. LordVoIdebug
  5. islingr

First Solves -

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

  • Проголосовать: нравится
  • +167
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

spoiler
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +174 Проголосовать: не нравится

The scoring distribution definitely highlights the Need For Speed on the first few problems.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +89 Проголосовать: не нравится

As a tester, this round made me feel dumb. Also JaySharma1048576 and his love for interactive problems continues Context

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +56 Проголосовать: не нравится

As a tester, I like problems!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

Early Score Distribution. Nice!

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +22 Проголосовать: не нравится

How come this blog was not on the home page.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +39 Проголосовать: не нравится

Insane TLs because of NFS? :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится
Spoiler
»
5 лет назад, скрыть # |
 
Проголосовать: нравится -71 Проголосовать: не нравится

Note the usual start time of the round

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Never solved an interactive problem in contest .i hope i solve one this time.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится
 .-'---`-.
,'          `.
|             \
|              \
\           _  \
,\  _    ,'-,/-)\
( * \ \,' ,' ,'-)
 `._,)     -',-')
   \/         ''/
    )        / /
   /       ,'
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

It's time to regain BMW M3 GTR from Razor !! :p

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

I think C is going to be that one problem :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

who is Razor? tourist?)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -40 Проголосовать: не нравится
Spoiler
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

Hope I can do my best to become Specialist and break my curse in this rank.

Spoiler

Edit: I made it guys, thanks :3

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +35 Проголосовать: не нравится

Time to revise kinematics.

»
5 лет назад, скрыть # |
← 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+

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Pink slips instead of delta?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +65 Проголосовать: не нравится

As a Master, I am disappointed in my testing performance. GL to everyone

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Thank you for the ride. I knew you weren't blacklist material. But hey, where's your punk money now?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Last two contest were different level. Hoping that this round will give some confidence.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Pink slip from tourist

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +110 Проголосовать: не нравится

.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I also NEED some SPEED for a better rating.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +26 Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -29 Проголосовать: не нравится

hope that won't be another MATHFORCES contest

»
5 лет назад, скрыть # |
← 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 :)

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

after seeing the score distribution ,the theme for the contest Need For Speed: Most Wanted seems as a warning

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Good luck and have fun to everyone!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

see you on the blocklist. what a nice joke along with warning.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -14 Проголосовать: не нравится

Proud moment for JaySharma1048576

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

The pun, see you on the Blacklist, XD lmao

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +86 Проголосовать: не нравится

Wishing you all high rating!

Codeforces NFS meme

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

A B will surely be speedsolving.C will decide everything

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Now it's time to increase my rating...

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am getting nervous. I only want that +19. :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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!!!

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -7 Проголосовать: не нравится

This round is going to be Speedforces

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I want some jerking acceleration for the first few problems, Hope not to get crashed or thrashed-->.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -38 Проголосовать: не нравится

Even tourist is participating in this contest

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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 :-(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only one who was banging my head against a wall trying to understand the fourth problem? Great contest!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +39 Проголосовать: не нравится

I just wanna know, why ???????

Why god why ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Am I the only one who is having hard time to understand problem C

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

I should've skipped this contest

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +58 Проголосовать: не нравится

Problem Statements seem too much messy.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +93 Проголосовать: не нравится

segment tree is very indian

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

welp, late registration, and failed to solve anything. I will hold the L for now and practice more xd.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

Not able to understood anything after solving problem A and B . C and D are bit mess

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Speedy MathForces,as expected!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

C is totally a mess!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +96 Проголосовать: не нравится

Props to all the contestants who can imagine a hypercube in their brain.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +37 Проголосовать: не нравится

Mathforces and Messforces

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I tried to wrote a DP solution for C but failed.

I think we can solve this with tracking values(recursion type).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is it just me or was A harder than B and D1?

»
5 лет назад, скрыть # |
← Rev. 15  
Проголосовать: нравится -25 Проголосовать: не нравится

How to think for problem C and D1? How to get that idea? What's the approach?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -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

  • »
    »
    5 лет назад, скрыть # ^ |
    ← 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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

  • »
    »
    5 лет назад, скрыть # ^ |
    ← 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 :(

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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.

»
5 лет назад, скрыть # |
← Rev. 6  
Проголосовать: нравится -11 Проголосовать: не нравится

C was a good problem but can anyone explain how this gets WA and this gets AC.

»
5 лет назад, скрыть # |
← 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.me/contest/1543/submission/121640564

Edit: instead of if(c>v) use if(c-v>1e-6). RIP.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
← 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +82 Проголосовать: не нравится

Me entire round:

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I want to now why the third part of the sample in problem C is always a little different ?

»
5 лет назад, скрыть # |
← 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. :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

For C, i got the correct answer but relative error is more than 10^-6. How to solve this issue?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

All excitement for interactive went in vain.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how to solve D1 ?PLZ EXPLAIN IN DETAIL

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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 on

    What 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)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Never do P(a) > v .. while dealing with doubles ! NEVER </3

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For problem C, to get a AC, I should have been imprecise :))

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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...

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    Yeah, i got the same issue, can we request author to consider these kind of solutions?

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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.

      • »
        »
        »
        »
        5 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          5 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится

          Exactly, you fall into the category of people who know the trick but don't know why it works.

          • »
            »
            »
            »
            »
            »
            5 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 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...

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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 <iomanip> (and not everyone uses bits/stdc++.h)

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится

    Since comparing doubles is messed up, try something like (c-v)<=1e-6 instead of c<=v

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    you should not compare doubles as integers a < b || a — b <= 0.000001 instead of a <= b should work

  • »
    »
    5 лет назад, скрыть # ^ |
    ← 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?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Solution for D:

Test $$$0$$$.
for $$$1 \leq i \lt 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.

  • »
    »
    5 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Well, the main idea is "if the answer was 1 and we asked query 0 how will our answer change?" and based on that we make this query. In D1 the x^z=y and x^z^(y^z)= y^(y^z) and x^y=z so we can simply calculate the next number based on the query we just asked. I found 2 approaches to this problem. -The first one is to get the prefix xor of asked queries and change the checking number based on that number. -Second one is changing queries based on the last query. if we asked if the answer was X last turn, this turn we will check if the answer is X+1 and the query is basically the change between X and X+1 which is X^(X+1).

    And on problem D2 I upgraded the second approach and made it work in base K. To solve D2 first we have to be able to do xor operation on base K. And see that after an odd number of queries the query we have to ask is inverted. for example, base=5, and the number we have to ask in query is 12341 in base 5 we have to ask query 32103 instead of 12341.

    the solution is here: https://pastebin.com/embed_js/eDqDVUWQ

    Sorry for my English, it might be bad. (It's not my first language)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

using double in C: relative error is like 10^3 using long double in C: relative error is like 10^4

fuck me i guess

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +87 Проголосовать: не нравится

3 things I learned after the round:

  1. Use a > 1e-9 instead of a > 0.

  2. Use a > 1e-9 instead of a > 0.

  3. Use a > 1e-9 instead of a > 0.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does greedy colouring not work on E? Otherwise what is TC 4?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +53 Проголосовать: не нравится

Me while reading C

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

https://codeforces.me/contest/1543/submission/121580369

can anyone explain this coding style.....hope everyone get what I am trying to convey

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Me after solving A and B

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Every one is talking about problem C , is there any body like me who couldn't solve the problem A

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

I swear I'll never give any writer's first contest.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

Who can tell me why java8 made D1 overtime.My algorithm is the same as others.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -11 Проголосовать: не нравится

The problems were as bad as getting tle on test case 47

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

We want old codeforces back. It was used to be so much fun.

(⋟﹏⋞)(╥_╥)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

I read Problem C at least 10 times.but I couldn't understand what type of probability was that?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone who passed pretests on C tell the number of pretests on that problem?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

can anyone explain me what was problem C(problem statement) in human language, pls ?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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 stop

    in 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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +58 Проголосовать: не нравится

JaySharma1048576 : I tried my best to create interesting problems with clear statements

clear statements??? you sure?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    5 лет назад, скрыть # ^ |
    ← 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

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      I have defined long long as int only

      • »
        »
        »
        »
        5 лет назад, скрыть # ^ |
        ← Rev. 3  
        Проголосовать: нравится +17 Проголосовать: не нравится

        my god... my dear god...

        1- stop using defines, it's for your own good

        2- if you're going to use defines, define it without conficting with existing typenames

        not 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

  • »
    »
    5 лет назад, скрыть # ^ |
    ← 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.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +14 Проголосовать: не нравится

It wasn't really good. The difference between B and C was very huge. It could be better

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +7 Проголосовать: не нравится

So fun contest! Cars, racing, hacking... Very thanks to the authors! It's was really cool.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Woke up half an hour before the contest , gave it , and now i think i should have slept instead.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Problem D1 : https://codeforces.me/contest/1543/submission/121622589

I didn't put the break condition if the solution is found but the main tests passed. How is that possible ?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

No matter you think this round is interesting or not, honestly, it's a different round.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Solved 4 Question after long time.. Expert Again!!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

poor english and bad google translation caused me fail to understand what pC was talking about

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

That was fun. Sweet and viscous masochistic fun. It's becoming a painful habit without Educational Rounds.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

I think LordVoldebug is a Div1 contestant and you mean LordVoIdebug, winning the 4th place. Wow, they are the same person xD

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Couldn't even get A right... I suck

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

its been 10 hours and still rating is not been changed

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think the problems will be better if they have no or shorter story backgrounds.

Anyway, it is a good contest!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is the content unrated?

»
5 лет назад, скрыть # |
← 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

Why rating change take so long?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

To me this round is a little bit hard compared to the previous rounds... I think

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain why at n=1 in problem B answer is 0?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can someone please tell me if this round is unrated??

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

is this contest unrated?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +61 Проголосовать: не нравится

The ratings have been preliminary updated. Later, I will remove the cheaters and recalculate the ratings.

»
5 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится -41 Проголосовать: не нравится

Orz

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

looking at the standings, me who did not participate in this round, telling myself " dude what happened here!"

»
5 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how do you test or debug interactive problems? I've written soln for D2 but no idea what's wrong or how to start looking for the bug.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    I used something like this for debugging my D1 and D2 solutions (a mostly untested conversion from D language):

    C++ code snippet

    If I pass interactive_judge function pointer to the solve function, then it uses stdout/stdin as required by the codeforces platform. But if I pass simulated_judge function pointer to it, then everything gets tested locally and can be debugged just like any other non-interactive problem.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

So this contest proved to be one of the worst contest.LOL