JaySharma1048576's blog

By JaySharma1048576, 3 years ago, In English

A: Exciting Bets

Hint 1
Hint 2
Tutorial
Solution

B: Customising the Track

Hint
Tutorial
Solution

C: Need for Pink Slips

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

D1: RPD and Rap Sheet (Easy Version)

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

D2: RPD and Rap Sheet (Hard Version)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Solutions
About the Adaptive Grader

E: The Final Pursuit

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Tutorial: Part 1 - Finding the Permutation
Hint 7
Hint 8
Hint 9
Hint 10
Tutorial: Part 2 - Colouring the Hypercube
Visualise the Colouring
Time Complexity
Solution
Alternative Solution (by mshiladityam)
  • Vote: I like it
  • +181
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it -102 Vote: I do not like it

-

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

    No wonder you are gray.

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

    Problem C should be rejudged with eps = 0, author took esp = 1e-9 but 0 should have been taken ideally

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

      It's actually common to encounter precision problems, so if you didn't know it then you should learn it and get AC when you meet float problems again.

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

        Can u please check my latest solution it’s got problem c, I know I’ve done everything right except handle precision , can you tell me how to handle precision , thanks in advance :)

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

          You shouldn't just use $$$>$$$ in your code, you have to add that if the difference between two floating number is less then a certain value than it should be count as equal. That number depends but in this question as the editorial says 1e-6 should be enough.

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

        yungyao Can you provide any recourse or link, or even the keyword to search for, in order to learn how to handle precision in cases like this where this advance level of understanding is required.

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

          I learn this from my friends so I am not sure about what resources are good. I think you can just search for floating number precision problems. Anyway the point is that C++ can not handle all floating number precisely, for example 0.1 + 0.2 == 0.3 will return false, so a lot of times if the difference between two floating numbers are small enough then it should be considered same.

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

      Sorry... I had a mistake in my code. eps=0 also works fine.

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

      I like your name.(not username , but name in profile). voyager

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

you can find the explanation for my alternative solution for E in Tutorial: Part 1- Finding the Permutation.

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

I was reminded why I don't know and don't like problems which are only about doubles. Spent 2hours trying to find out why a > 0 doesn't work...

»
3 years ago, # |
  Vote: I like it -82 Vote: I do not like it

speedforces

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

    yes, speedforces for those who solve only one problem in the round.

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

      thought I could get wholesome rivalry, sorry for being cocky:/

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

        it's just stupid to write "I will beat you in the future" when you are rated 600 points lower. Just shut up and work hard.

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

          Its better to be at expert regularly giving contest than stop giving contest on becoming master once just so that you can flex .Maybe a guess or cheating.You can only become the driver of the bus of tourist,so stop putting anything related to our legend-tourist in your profile.

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

            What the hell. I stopped writing rated contests for a while even after becoming purple. I practice on hard problems exclusively during these periods, and when I feel I can jump to the next level (IM in this case) I continue writing contests.

            As for me becoming master by "fluke", in all the div2 rounds which are unrated for me I have written, I have solved 2400/2500 rated problems within the first hour. So no doubt I can maintain master if I write a contest now. But I don't want pressure of rated contests right now. Its just my personal preference.

            Your comment is incredibly insulting. You probably are a low rated div3 guy and dont know what it takes to achieve what I have. And as for the guy above, he keeps on writing "I will beat you" so I got angry.

            Peace.

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

              Yeah people like you who have achieved fcuk all in their life masquerading as all intelligent when i open CF is why i hate people so much. You just got lucky with your submissions and now act as a bl**dy know it all when in reality you are just a stupid BTech kid.

              Shut up and stop being a fcuking elitist.

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

                If being lucky was the criteria for codeforces rating then I think all the LGMs should buy lottery tickets immediately.

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

              The problems which get 2400/2500 in Div2 Rounds are not that difficult(they are around 2200 maybe) but the ones in Div1 like D1B-C(Rated <= 2400 usually) are much more harder. It usually happens with me, I frequently solve 2400/2500 in unofficial Div2s but can't get even close to a 2300 rated problem in Div1.

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

            Painful but true :").

»
3 years ago, # |
Rev. 5   Vote: I like it +33 Vote: I do not like it

https://codeforces.com/contest/1543/submission/121576639 (A)-00:08 https://codeforces.com/contest/1543/submission/121580369 (B)-00:12 https://codeforces.com/contest/1543/submission/121614790 (C)-00-58

wtf....

from the submission time we can track when solution gets leaked ... so we need to prepare even harder ..to solve before it or near that time... so that we are not at much loss...bcz anyways they wont be banned or even if they will start again this foolishness...

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

C was definitely the worst question, because it is a hit or miss. People who are used to this type of question would probably convert the doubles into integers/long long to prevent errors, but most people are gonna suffer from the terrible precision of long double. Aside from rambling, I think D2 is a pretty cool question nevertheless.

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

    Well, float precision is an important skill for competitive programmers. For people that are not familiar with these kind of problems, they will learn from this.

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

      Precision errors are unpredictable most of the time. I've seen problems where a mere change in the value of eps creates the difference between Accepted and Wrong answer on test 22 xD. For eg. changing eps to 1e-14 gives WA but 1e-10 works.

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

        Could you please share that task you talking about. Thank you.

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

          It was in a gym contest I'll have to search. I'll share when I find it.

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

    I don't get why long double gives me WA but double gives me AC. I added 1e-14 to the inputs in both cases.

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

      Yeah why? also what does adding 1e-14 do?

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

        adding 1e-14 to the numbers increases precision up to 14 digits and from here on every operation will be performed up to this precision. I'm not sure if this is what happens but this simple trick has worked for me in many such problems.

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

          The same trick doesn't work if instead of adding 1e-14 we multiply by 1.00000000001 does multiplying not increase precision?

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

            does multiplying not increase precision?

            No, multiplying doesn't improve precision. In fact, it makes precision worse.

            (Edit: Also, "adding 1e-9 or 1e-12" doesn't "improve" your precision. What it does is basically saying "if the probability is less than 1e-9, we'll assume it's zero". We need this because, for example, 0.3-0.2=0.09999999999999998 (you can check this in python).)

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

    how's it hit or miss? they said 1e-6, i used 1e-6, first try

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

This was a fun round and figuring out how eps works finally paid itself off. Also massive props for making one of the most interesting interactives on codeforces. :)

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

In C, one of my pretest answer was off by 0.002, rest were correct, so I was getting wrong answer, I usually use python, did a little bit of digging up after contest when I switched from float -> Decimal class, got the right answer :/

»
3 years ago, # |
  Vote: I like it -56 Vote: I do not like it

ReadingStatementsForces

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

    In what round do you not have to read the statement? April Fools??

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

When the proofs are by induction... you know it's either hit or miss.

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

Thanks for detailed editorial containing hints and multiple approaches.

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

In problem C, why if 0 is used in place of epsylum(very small value) in the author's solution gives a wrong answer?

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

    Exactly that's also my question

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

    0 is an integer and eps is a double , that is why using epsilon prevents precision errors

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

    The problem is that when you compare two floating-point numbers, the result of the comparasion may be wrong, because computers store numbers up to a certain precision.

    In this problem, when a certain probability becomes exactly 0, the respective variable may store a very small number due to precision issues, and you make an extra step due to that, changing the answer. You should always compare floating points with epsilon, unless the comparasion result is irrelevant.

    How to choose a proper epsilon? That is a difficult question in general, but in this problem it is easy. Let's say that you store the probability in variable a. I claim that the true value of a is always of the form $$$a= x\cdot 10^{-4}\cdot 2^{-steps}$$$, where $$$x$$$ is an integer and $$$steps$$$ is the number of steps made. It can be proved by induction on steps. Now it's easy to see that the true value is either $$$0$$$ or at least $$$10^{-4}\cdot 2^{-20} > 10^{-11}$$$. Given that precision issues are usually not greater than few least significant bits ($$$\approx 10^{-16}$$$ if you use long double), any epsilon between these numbers should work. It turns out that some other epsilons work too.

    The reference solution to this problem operates in integers, of course, and avoids these issues. It will be uploaded in the post soon.

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

Thank you, liked the problems! Although I thought A is too hard to be A, but it was fun:)

I have a question about my solutions. On my machine, the answer was printed, but in system I got WA. Here's my solution: 121640373. System said that on test 5 3 with start password 1 I tried five times and haven't guessed it, but when I was testing locally my program did. Can anyone please tell me why did it happen?

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

    Thanks to kind man in technocup chat, problem solved, I thought that a xor b = z means that b equals z xor a. And this was mentioned in the editorial, so sorry for stupid question:)

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

I know this is generally a dumb question, but I have to ask — people who solved E, how did you come up with the colouring? Is it just a matter of throwing shit at the wall and seeing what sticks?

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

If you didn't like the contest, don't downvote the editorial. Just downvote the announcement.

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

Hello everyone, please do not downvote the editorial because you did badly or didn't like one problem from the round. Round authors and testers did their best to make the round as high-quality as possible, and you can see that they even implemented feedback to give hints inside the editorial, which is really appreciated!

Thank you JaySharma1048576 for this wonderful round!!

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

How could we guess to use epsilon in problems like C? Is it some rule to have it as 10^-6? I used it as 0, but my solution gave imprecise answers for 3rd test case in the sample test case. Even, the editorial solution gives the same answer as mine if epsilon was set to 0. So, I could confirm that I was getting wrong answers only because of the precision problems. Does using 1e-6 as epsilon work for other similar problems too?

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

    I also have the same doubt. In the official solution, if we change the value of eps to 1e-17 or lower, the answer varies drastically.

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

    Try

    if(0.1 + 0.2 == 0.3)cout << "Yes";
    else cout << "No";
    
    

    This will print "No"

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

    When you must work with doubles/floats you should always test for equality with very small values such as (1e-6, or 1e-9), as opposed to 0, due to precision errors. If you compile with the -Wfloat-equal option, your compiler will automatically alert you to not test for equality with "==" or "!=" if you do in your code

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

    no 1e-6 is often too big to find equality in pb152 of PE you would find false solution if you used such an epsilon, sadly you have to use gut feeling to guess in each problem the good epsilon. By the way I got WA on test case 4 after the round I'm very angry against myself

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

Really appreciate the quick and detailed editorial, it really helps to read the editorial while the problems are still fresh in your mind (if that sentence makes any sense :P). Having said that, I do think that a disclaimer that a round is gonna be more math-centric rather than algorithm based should be given as a lot of people might only enjoy algorithm based contests, but a decent round nonetheless :)

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

In problem C official solution, epsilon = 1e-9 is being used for checking 0 equality. However, if exact 0 equality check is used in the conditions, the solution fails by 0.03 even on pretest 1 (input 3). Can anyone please explain how do we determine what equality check to use in such questions ?

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

In C, why there are precision issues, even if I set the argument to 0 explictly? I thought 0 can be represented accurately according to IEEE 754, but it seems in the function the zero becomes a small number rather than 0.

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

    It’s correct that literal zero has exact representation, but how do you deal with subtraction c - v and m - v in the writer’s solution, which can result in a tiny floating point number even when it’s zero in theory?

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

Language of C could have been better. Otherwise good problems(specially interactive ones)

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

This is to clarify why taking epsilon equal to $$$0$$$ will not work in C. Everyone know that floating point arithmetic is associated with some precision errors which is usually of the order $$$10^{-15}$$$. So, if $$$c=v$$$, ideally $$$c$$$ should become invalid but if due to some floating point precision error, $$$c$$$ becomes $$$10^{-15}$$$ and if you are comparing it with $$$0$$$, your code will treat it as still valid and this will cause a Wrong Answer. In this problem, taking any epsilon in the range $$$10^{-6}$$$ to $$$10^{-14}$$$ will work, not only $$$10^{-9}$$$. I was well aware that many participants will make this error. So, I included a test where this error arises in the samples itself (sample test case 3) so that no one gets unnecessary penalties.

Moreover, the main solution against which the solutions are checked doesn't use floating point numbers. It uses integers after multiplying the values by a scaling factor. I am providing that solution in the editorial.

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

    "In this problem, taking any epsilon in the range $$$10^{-6}$$$ to $$$10^{-14}$$$ will work"

    @JaySharma1048576, Can you please show the proof for the above statement with all the steps!! I know I am asking for more but this kind of problem is not common(at least I encountered this for the first time) so please help!
    Thanks for the great round!

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

      Epsilon should neither be too high nor too low. In general, it should be less than the lowest significant number that may affect the answer and more than the highest precision error that may occur. $$$v$$$ has $$$4$$$ decimal places at max as given in the constraints. It follows that $$$\frac{v}{2}$$$ has $$$5$$$ decimal places at max. So, at any point when there are three valid items, $$$c$$$, $$$m$$$, and $$$p$$$ can have $$$5$$$ decimal places at max. When suppose $$$c$$$ becomes invalid, $$$\frac{c}{2}$$$ gets added to the probabilities of the remaining items which can have $$$6$$$ decimal places at max. After this, the number of decimal places in $$$m$$$ and $$$p$$$ can never go more than $$$6$$$ because all the probability will now go to $$$p$$$ only involving no division by $$$2$$$. So, at any point the maximum epsilon allowed is $$$10^{-6}$$$. If you look more carefully then the $$$5$$$-th and $$$6$$$-th decimal places will always be one of $$$00$$$, $$$25$$$, $$$50$$$ or $$$75$$$. So, the maximum epsilon allowed is in fact $$$25\cdot 10^{-6}$$$. But for simplicity, I have taken $$$10^{-6}$$$. The lower limit is, however, difficult to say. Precision errors are quite random and may be as low as $$$10^{-18}$$$ or as high as $$$10^{-15}$$$. But since double data type uses $$$52$$$ bits for mantissa, atleast $$$15$$$ decimal places of accuracy is guaranteed. So, anything greater than $$$10^{-15}$$$ must be fine for epsilon.

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

Please do not downvote this blog. Some people might be unable to find the editorial.

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

I'm kinda disappointed at problems in this round, cuz I feel they're not so relevant to Algorithm or something fun but more revelant to English Reading and Code Implementation.

  • Problem A and B are not bad but the easy problems don't really effect the quality of a round.
  • Problem C and D are just annoying implentions with no algorithm.
  • Isn't Problem E just a well-known problem since a famous youtuber 3 Blue 1 Brown has talked about it? Although 3B1B doesn't give solutions directly, this problem is anyway standard.
  • As for English Reading, the statement is unnecessary long and lack of logical relationship, I can't get the key info fluently at all. Everyone prefers short and clear statements, or at least a longer but logically reasonable statements, instead of these.
  • Idk why author addes "You beat xxx" or "You race with xxx" in beginning, when xxx just doesn't appear in any part of the following statement. I can't see any logical relationship between this character and the problem.
  • And tbh some elements in the statement like Cash Slip, Impound Strike Release Marker and Pink Slip of Rival's Car is extremely confusing, at least for me. I spend time looking up what does these words mean and thinking how they're revelant to the following statement but it just turns out that I'm wasting time.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I hadn't seen any problem like E before. Btw if setters never use something similar to "known" problems then will they even be known for most div2 participants?

    I mostly agree with the rest though.

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

      Well, fair enough. What I concern is, cuz it feel like a repeated problem in a sense, especially cuz it's not so relevant to a certain algorithm. I'm kinda worried about situations like someone easily solve it if he learned it before, when others with more experience in algorithm maybe can't get the point in a short time.

      Btw, to author if you're seeing, I don't mean to be negative to your efforts >_<, I respect all people contributing to CF. Just want to give some suggestions to look forward to your better problems. >_<

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

        Sure. I am not blaming you for anything. I am taking your feedback positively and I will try to improve the statements next time.

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

Thanks for detailed editorial containing hints and multiple approaches! ><

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

Hi! Guys you don't have to downvote the editorial because Author and coordinator and testers did their best to create this contest and dear Author made a great and complete editorial ! Afterall Good job everyone.

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

In problem A, the input constraints for a and b are 0 to 1e18. Many participants used int type variables to read a and b have verdict as Accepted. Is it because the main tests do not contain tests which are greater than INT_MAX. Example: 121578546

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

Problem C was not at all good; first and foremost, its language was as terrible as it could be. It was difficult to follow, and the variables used to describe the test cases were unclear. Simple and precise language can also be used to create a nice and fascinating problem.

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

A: good idea, gcd(x, y) = gcd(x — y, y) B: intuitive, greedy C: implementation D: try 0~(n-1) with previous change

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

Can anyone give the reason why 1 is added in the recursive solution given in the editorial of problem C in the line given below

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

    else you would get as whole answer 0, you must count future race and this particular race (which is the 1), hope I'm clear

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

Why is this code https://codeforces.com/contest/1543/submission/121641823 fast? Shouldn't it get TLE? Are tests bad?

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

C can be solved with DP in O((2/V)^3) or even O((2/V)^2) https://codeforces.com/contest/1543/submission/121629108

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

nevermind, got it

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

Is it preferable to avoid using accumulate to find sum of vector in C++,as in problem B using accumulate to
find the sum of vector, solution gets failed on pretest 2,but when I switch to find sum in usual way it get passed. Does anyone have any idea about this?

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

    Yes, it's better to use things you can control and understand.

    When you use accumulate, the accumulative variable takes the type of the last argument. So if you pass an int, it'll be an int and you'll have overflow.

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

    Writing 0ll in place of 0 , in accumulate function would have worked as 0 is int and 0ll is long long int , and int gives overflow. Your code ACfied

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

121621126

Can anyone help me why I'm getting TLE ? And help me to optimize it

I have guess it's java, is'nt it? T-T

I used python and it barely passed with same logic and its intended logic too T-T

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

    Yeah I guess so. Same happened to me, even though my algorithm is identical to Idea 2 in the tutorial.

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

    ok so apparently buffered reader isn't fast enough, but System.in.read(); is. Check this guys solution for reference: 122226246. I copied his fasterScanner method and my solution also got accepted.

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

I really enjoyed problem D even though I lost a lot of time and points getting TLEs because of slow python IO (had to switch to stdIO). I'll know better next time.

Anyway thanks for the nice problems.

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

Is the adaptive grader on problem D badly designed? https://codeforces.com/contest/1543/submission/121656699 gets accepted even though it has //if(r == 1) return; commented out.

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

    It is because the adaptive grader is designed such that any solution which passes will pass only after exhausting all $$$n$$$ queries. Read the note given about adaptive grader given in the editorial. In order to pass all initial passwords, you need atleast $$$n$$$ queries, because with one query, you can pass not more than one initial password. So, even though it seems that your correct code may guess the correct password in less than $$$n$$$ queries, the correct code will use $$$n$$$ query only. So, returning or not returning doesn't make any difference.

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

      Yes, that's exactly the problem. The grader assumes that the best way to break people's solutions is by checking whether they are correct for all n possible starting passwords by always saving the "correct query" until the very end. In my opinion, having this grader for every single test case is bad design because it allows some incorrect solutions (like the one I posted) to pass. Ideally, there should have been at least one or two test cases that don't use this algorithm so that incorrect solutions like the one I posted fail.

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

A few words on this round. I will refrain from commenting on floating-point stuff (related to C) because basically everyone else has already done it. :)

  • Statements were mostly clear (that is, unambiguous), but C was a pain to read and D, I believe, could have been shortened a bit. Also in D, the wording "You don't know it, but you are quite sure that it lies between $$$0$$$ and $$$n−1$$$ inclusive." is a poor choice (you are not "quite sure", you are absolutely sure).
  • Problem A is too mathy in my opinion. Apart from that, average problem for Div 2.
  • I didn't like B. The observation that only the sum matters is trivial, and the fact that the individual $$$a_i$$$'s are irrelevant is the CP equivalent of a math problem with useless hypotheses. Also, I found it easier than A, but that might be subjective.
  • C is pointless. The fact that it is solvable only under the constraint $$$v \ge 0.1$$$ makes it really uninteresting.
  • D1 and D2 were nice and I enjoyed them, but the concept behind the problem is a bit unnatural (which is reflected in the length of the statement: I find that the most natural and beautiful problems are the ones that allow for clear, short statements).
  • E I didn't even read.

Overall, I consider this a bad round, even though there have been worse.

On the other hand, the editorial is really well-written and understandable!

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

deleted.

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

There can be a much better solution to D2. In case of k = 2, number itself is kind of k-wise xor inverse. So, if we think in terms of k-wise xor inverse of a number it would be easier to understand that solution and come to the solution as well

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

    How can we arrive to solution if we think in terms of k-wise xor inverse? The solution given in the editorial seems like a guess to me and then later proved with induction. Can you please tell me how to arrive at the solution by oneself?

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

      Let xi,k be a number such that k-itwise xor of x and xi is 0. If x was password , y is the guess made then z is new password such that

      x (xork) z = y         Here, xork represents k-itwise xor

      If we take k-itwise xor with xi,k both side we get —

      xi,k (xork) x (xork) z = y (xork) xi,k

      z = y (xork) xi,k

      Therefore new password is k-itwise xor of k-wise xor inverse of old password and guess.

      I would like to state one property before we go on to solution —

      (a xork b) i,k = ai,k (xork) bi,k

      This can be simply proved if we think in terms of k-its

      In mth guess we will guess the number supposing original number was m-1

      So, the order is

      password — x
      guess — 0
      new password(if guess wrong) — xi,k (xork) 0 = xi,k

      password — xi,k (xork) 0
      guess — 1i,k (xork) 0
      new password(if guess wrong) — (xi,k)i,k (xork) 0 = x (xork) 0 = x

      password — x
      guess — 2
      new password(if guess wrong) — xi,k (xork) 2

      password — xi,k (xork) 2
      guess — 3i,k (xork) 2
      new password — (xi,k (xork) 2)i,k (xork) (3i,k (xork) 2)
      = x (xork) 2i,k (xork) 3i,k (xork) 2
      = x (xork) 3i,k

      password — x (xork) 3i,k
      guess — 4 (xork) 3i,k

      So, we can simply see that ith guess is
      if i is odd — (i-1) (xork) (i-2)i,k
      if i is even — (i-1)i,k (xork) (i-2)

      As I didn't have mathematical symbols, solutions look a litle complicated than it is.

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

        Thanks a lot. But to be honest, it still seems like a guess to me. I think I should just leave the problem for now and get back to it after some time. Thanks again.

»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Everyone be complaining about messy problem statements but the truth is

TRUTH

Prob C brought to light my misconceptions of float operations. The NFS: MW references were a joy to read and recall, despite their irrelevancy. Thank you very much for this contest!

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

D1 is annoying, same algorithms but using Python will get TLE (maybe because output is so slow) really unfair.

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

I can't understand the brute force implementation of problem C , i can't understand the addition of 1 and then the recursive call

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 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). I have not included the extra if/else cases here. Just initialise the recursion with 1 and continue.

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

      I really still don't understand why plus 1. Can you explain a bit more?

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

        In the definition of problem, the probability is about "count of all race until P is selected" So, select C or M means one more race. So +1

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

I have solved C using doubles, but I tried to solve it again by converting it to integers after multiplying it with scale as given in the editorial. However, I am getting overflow doing that. I have already defined # define int long long.
Can someone point out the error, please? My code

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

    The reason of over flow is while returning the value from val function , you are returning no.>= 1e6 , which in more than 3 multiplication will lead to overflow .

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

      Yeah, thanks. It worked. Moreover, I was initializing my answer with 1e6, it should have been 1e12. I had one more doubt, I have mentioned that in this comment.

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

For the first part of question E, you can find the inverse permutation s as follows.

Pick any vertex V and let s(V)=0. Then send the neighbors of V to the powers of 2.

In the standard n-cube, the distance of i to 0 is just the number of bits set in i. Moreover, the vertices which occur on some shortest path from i to 0 are precisely the submasks of i. In particular, if i is at a distance of >=2 to 0, then i is the bitwise or of its neighbors which are closer to 0.

To find the inverse permutation, we can proceed by doing a bfs after assigning the neighbors of V. When we reach vertex v, let s(v) be the bitwise or of s(w) as w ranges over the neighbors of v which have already been seen. (Here, we should note that two vertices at the same distance from 0 in the standard cube have at least 2 different bits, so are not neighbors. Thus a neighbor is closer to the staring vertex V if and only if it has already been seen).

This gives us the inverse permutation. To go back the original permutation, sort the list of i by s(i).

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

is this contest unrated ?

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

    I want to ask the same question.

    My rating hasn't changed, either.

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

    I wish so. May the ratings be with us.

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

Could anyone tell me why my rating hasn't changed?

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

Problem E can be found in YouTube.

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

    So is it unrated?

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

      Probably not.These two things are not related.

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

        Can you give some tips for questions like E. Others were relatively easy but I have never seen anything like E before and even after the contest its hard to understand. Any resources would be nice

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

Can somebody tell the time complexity of problem C in the simplest way?

UPD: GOT it.

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

in question 3 it showed pretest passed(3) but later during system testing it showed TLE on testcase 2.How is it possible means why it then showed pretest passed???

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

Thankyou for this round, I messed up C for 1 hour due to precision errors but learned something in the process. D1 and D2 were interesting to me as well.

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

Nice round although wasn't able to solve C but got to learn new concept of precision Handling today

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

ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));

I don't understand where the number 1 comes from in this expression

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

    With c probability, you'll play 1 move, plus, the expected number of moves starting from new probabilities. That's why "1 + E(c-v, m+v/2, p+v/2, v)"

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

Can anybody explain their thought process for D1?

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it
    Pretty long answer, open if you wish
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So realizing that if x^z = y can be written as y^x = z seems to be a critical observation. How did you realize that ?

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

        I knew that x^x = 0 and 0^z = z from the truth table of bitwise xor operator.

        Hence, x^z = y => x ^ x^z = x ^ y => (x^x) ^ z = x ^ y => z = x^y

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

      You are the real boss among all the people who comments, the problemsetters and the editorialist.

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

    Just think about D2, then restrict the solution to $$$k=2$$$.

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

      Is this the reason why you failed solving D1 during the contest? Solving the problem for $$$k=2$$$ and then trying to generalize the solution seems to be much more rewarding.

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

        The logic is basically the same, the only difference when $$$k=2$$$ is that $$$i \oplus j = i \ominus j$$$.

»
3 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Orz

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

It seems like the coloring part of E is touched on in this video. It's also a great watch, with a nice application of the problem.

The game mentioned in the video is also a nice, intuitive way to come up with the xor-based solution. Let's consider playing the coin game on a $$$n$$$-square board. As explained in the video, flipping exactly one coin corresponds to moving to an adjacent vertex in the (non-permuted) $$$n$$$-hypercube, with each bit corresponding to whether each coin is facing heads or tails. Let's color the vertices of the hypercube so that the state with the color $$$c$$$ corresponds to the key being under square $$$c$$$. Therefore, as we need to be able to communicate any value of $$$c$$$, we require that the set of colors of neighbors of any vertex must have all possible colors from $$$0$$$ to $$$n-1$$$, hence any solution to this coin game is equivalent to a desired painting of the $$$n$$$-hypercube.

Now, what's a simple solution to the coin game (when $$$n$$$ is a power of $$$2$$$)? Let's number each square from $$$0$$$ to $$$n-1$$$. Let's define some value $$$v$$$ calculated from the state of the board that we can change to any other value by flipping exactly one coin. Well, xor of numbers of all squares with heads works here because by flipping one coin in square $$$s$$$, we flip all bits in $$$v$$$ corresponding to mask of $$$s$$$. As we can choose any mask (due to $$$n$$$ being a power of 2), we can flip exactly one coin to change $$$v$$$ to any value between $$$0$$$ and $$$n-1$$$. Therefore, we can change the board state such that $$$v$$$ is equal to the square under which the key is located.

It is not difficult to see that this solution to the coin game corresponds to the coloring shown in the editorial.

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

Could you guys help me with TLE on D1 with java? https://codeforces.com/contest/1543/submission/121703927

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

can anyone explain in problem C(solution) we are adding V/2 which rounded down always. Will it not affect the answer?

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

    They first scaled the input by $$$1e6$$$. Since the number of decimals is at most 4 it is therefore guaranteed to be divisible by 2, so there will not be any rounding error.

    E.g. $$$0.1234$$$ is scaled to $$$123400$$$ which is divisible by 2.

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

The Answer to test case 0.4998 0.4998 0.0004 0.1666 should be 5.0307188293 instead of 5.05 Since v is 0.1 minimum so the game ends in max 20 turns(since you are taking atleast v/2 from the c + m collection). If you simulate the game till 20 turns for all possible CM combinations you get 5.0307188293. The approximation I see every where of comparing with 1e-9 is not accurate.

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

Ok this might be a dumb question but in

ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));
//                ^--------------------------------------- this

why the 1?

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

In the editorial, the author JaySharma1048576 has used a scale of 1e6.
However, when I am using a scale of 1e6, it is giving WA on Test 8. Code-121732306

On the other hand, when I am increasing the scale, it's giving AC. Submissions-121733647 and 121733750

Can someone tell me please, what should be the minimum scale to avoid integer overflow, as using 1e6, would have given FST in Contest?

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

      Your solution is almost same as the editorial solution, by which all the solutions are checked. I am asking the reason.

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

    You should take c = round(c1*xx) instead of c = (c1*xx) in your code because 0.1*1000000 may be equal to 99999.9999999..., again because of precision errors with floating point numbers. Typecasting it to int will give 99999 but it should be 100000 for which you should use the round() function. The scale of $$$10^6$$$ is completely fine in this problem because the inputs have $$$4$$$ decimal places at max.

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

bruh i tried to do a O(d^2) sol for C

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

Sorry for posting this late, but can someone please explain why 1e-10 works in the below line for a solution to Problem C, but 1e-9 doesn't?
Shouldn't they both be working?

if(p * level * prob <= 1e-9) return;

The submissions: 1e-9, 1e-10.

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

The coloring part of problem E was posed here: https://codeforces.com/blog/entry/52918

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

JaySharma1048576 Can you please share the code of adaptive checker for D1 & D2?

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

Hey can somebody explain the reasoning behind the following behaviour? I am converting the floating numbers to integers by multiplying them with a constant (like 10^5, 10^7 etc).

Can you please explain why this is happening particularly in this case? I get that recurring numbers (in binary representation) don't get stored exactly due to the recurring component but we would never end up in a recurring situation since 0.0001 would get divided at most once and become 0.00005. Hence the question about why 1e5 is not enough.

Is it the case that the constant multiplication of the dp terms like c * p * p *.... and so on is causing the error to seep in? How do we decide the constant to scale the floating numbers in that case short of just experimenting and seeing what works?

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

    For this problem, if you see how the values may change during the whole process, you will notice that these values may get divided twice and not once (see this comment for more details). So, taking a scaling factor of $$$10^6$$$ or greater works here.

    If you take a factor of $$$10^5$$$, then one of the values of $$$\frac{a}{2}$$$ may not be an integer. For example, take (0.3000, 0.1000, 0.6000, 0.2001). After choosing C, the probabilities will become (0.0999, 0.20005, 0.70005, 0.2001). Now, if you choose M, the probabilities will become (0.199925, Invalid, 0.800075, 0.2001). So you can see that the probability of P became 6 decimal places.

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

      Oh yeah, completely missed that. Thanks! :)

      However I still don't understand why 10^7 doesn't work without setprecision. Any why 10^6 fails with or without setprecision.

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

        setprecision controls how many decimal places you want to print. By default, it is quite less and since the maximum error allowed is $$$10^{-6}$$$, you need to set it to something more than 6 decimal places.

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

          Okay, that makes sense. face palm Thanks for taking the time to replying! :) Really liked the questions!

          For anybody else who's wondering why won't 10^6 work with setprecision: try running

          long double a = 1.111;
          int one = 1e3;
          int aint = a * one; // aint = 1110...
          

          Why?

          • Because a in binary => 1.0001110001101.... (this is non recurring terminating but has 50-ish decimal places)
          • one in binary would be 1111101000
          • a * one in binary would be 10001010110.1111011001000
          • when type casted to int aint in binary becomes just 10001010110 (the integer part of the result)
          • and voila! that turns out to be 1110 in decimal.

          Disclaimer: I don't know much about how things work closer to the metal. Please let me know if I'm making a mistake somewhere.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! Can somebody help me understand in sequences from solution at problem C like: (1+expectedRaces(c-v,0,p+v,v)) how that +1 helps in finding the right answer? I mean I understood the idea of calculating the answer and how that solution works, but that +1 scares me. I tried simulating on paper but with no results:(

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C is brutally brute implementation. I just gave it to chatgpt it spitted out solution in 1 sec