JaySharma1048576's blog

Codeforces Round #730 (Div. 2)
By JaySharma1048576, 3 years ago, In English

Hello Codeforces!

I am quite excited to invite you to my first ever round, Codeforces Round 730 (Div. 2) which will start on 07.07.2021 17:35 (Московское время). 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

  • Vote: I like it
  • +167
  • Vote: I do not like it

Comments Comments (268)
| Write comment?
»
3 years ago, # |
  Vote: I like it +125 Vote: I do not like it

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
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +174 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +89 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

As a tester, I like problems!

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Early Score Distribution. Nice!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

How come this blog was not on the home page.

→ Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Insane TLs because of NFS? :)

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it -71 Vote: I do not like it

Note the usual start time of the round

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it 
 .-'---`-.
,'          `.
|             \
|              \
\           _  \
,\  _    ,'-,/-)\
( * \ \,' ,' ,'-)
 `._,)     -',-')
   \/         ''/
    )        / /
   /       ,'
→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

who is Razor? tourist?)

→ Reply
»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it
Spoiler
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

Spoiler

Edit: I made it guys, thanks :3

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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!

→ Reply
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Time to revise kinematics.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

[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+

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Pink slips instead of delta?

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    So it's going to be overly difficult and unbalanced for Div 2? Thanks for the warning I guess :/

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Not really, testers traditionally brick rounds pretty hard (speaking from experience).

      → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Two "orange" testers have already said the round was very difficult for them, so don't get your hopes up...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        As a tester, this round made me feel dumb. — yash_daga

        As a Master, I am disappointed in my testing performance. — DimmyT

        I interpreted this to mean this round will be especially difficult.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pink slip from tourist

→ Reply
»
3 years ago, # |
  Vote: I like it +110 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I also NEED some SPEED for a better rating.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

→ Reply
»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

hope that won't be another MATHFORCES contest

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Good luck and have fun to everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

Proud moment for JaySharma1048576

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The pun, see you on the Blacklist, XD lmao

→ Reply
»
3 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Wishing you all high rating!

Codeforces NFS meme

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

A B will surely be speedsolving.C will decide everything

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am only +34 away from specialist.I am little nervous.But once I started from 0.I should remember that.Good luck everyone!!!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just remember that there were people with +1 away from their desired rank. Just a reminder. :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah.That's why Let's just enjoy the contest.Nothing is above than that

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if you don't think about the rating, that's when you really grow.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Somewhere there is a child in every man, that doesn't grow.

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      still +14 away

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You'll get there. Don't lose hope.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

This round is going to be Speedforces

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Even tourist is participating in this contest

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :-(

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me as well. How did >2.7k people solve it :/ Lets wait for the editorials!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

Why god why ?

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I should've skipped this contest

→ Reply
»
3 years ago, # |
  Vote: I like it +58 Vote: I do not like it

Problem Statements seem too much messy.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

segment tree is very indian

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedy MathForces,as expected!

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

C is totally a mess!!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You could convert all the doubles/long doubles into long long int/int and then do a dp after that

    → Reply
»
3 years ago, # |
  Vote: I like it +96 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Mathforces and Messforces

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That's what I did. Link You just have to be careful when converting the doubles/long doubles into integers I think.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good

      I was thinking of recursion while implementing my dp solution but i was too late.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 15   Vote: I like it -25 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 12   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I thought it was problem C as I was solving it after A,B, I immediately tried to edit it.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
← Rev. 6   Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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.net/contest/1543/submission/121640564

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

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Me entire round:

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    maybe you didn't control the condition like if(c>eps)

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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. :(

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I solved that by assuming $$$0 = 10^{-6}$$$

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain why that works?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use the function of precision:

    Code

    Here in the brackets instead of "x" you can write what decimal you want.

    → Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

All excitement for interactive went in vain.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D1 ?PLZ EXPLAIN IN DETAIL

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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)

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 this

        edit: it's most likely some floating point nonsense

        → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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...

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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...

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Writing some code without understanding how/why it works is the definition of cargo cult programming.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

→ Reply
»
3 years ago, # |
  Vote: I like it +87 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bruh, literally this changes answer from 5.0301143 to 5.0050777 ?? xD thats like 0.025 difference, yo?

    anyway goodbye candidate master

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Same error! Good lesson for comparison of real numbers XD.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Me while reading C

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    ant++,wasp---

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think when real hackers hack the codes like this they try hard to find the main code.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Me after solving A and B

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

(⋟﹏⋞)(╥_╥)

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks man, I got the solution also. Understand the problem statement seems hard than actual solution for me.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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

clear statements??? you sure?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1543/submission/121632020

why this is wrong?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    long long, while n and n-x can be regular integers, nothing is bounding n*(n-x) to be smaller than 1e9

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have defined long long as int only

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it +17 Vote: I do not like it

        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

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Thanks for the round! For anyone interested, here's a link to my screencast.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D1 : https://codeforces.net/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 ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry. I misunderstood l instead of I in his username. Both of them look so similar.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      Thanks for a round, especially for problems D and E — surprisingly simple, yet challenging and mind-bending.

      → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The user ratings hasn't been updated yet for today's content. If you see the final standings, there should be rating update tab.

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

its been 10 hours and still rating is not been changed

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Anyway, it is a good contest!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the content unrated?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "The round will be rated for participants of Division 2 (having rating strictly less than 2100)."

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    nobody got their rating changes yet, relax

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +25 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what it means by forwared from ? means copy paste?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +7 Vote: I do not like it

        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 ...

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yep. Quite similar to this solution (taking out all the ants and wasps)

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      Pure comedy gold, this needs to be framed and kept in eternity

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Hahaha cheater caught

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You didn't think Cheating was gonna get caught?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sir that's the truth whether you believe or not I don't care

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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 .

        → Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Why rating change take so long?

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

is this contest unrated?

→ Reply
»
3 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -41 Vote: I do not like it

Orz

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

This D1 solution was accepted https://codeforces.net/contest/1543/submission/121690053

My same D1 solutions were all rejected https://codeforces.net/contest/1543/submission/121633283 https://codeforces.net/contest/1543/submission/121631556 https://codeforces.net/contest/1543/submission/121634285

Is it time to move to C++? the last one even passed the pretest...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply