Vladik's blog

By Vladik, 6 weeks ago, translation, In English

andersen

Hi Codeforces!

I am glad to announce and invite you to Codeforces Round #678 (Div. 2), which will be held on Oct/24/2020 17:05 (Moscow time). A couple of weeks ago, we held Codeforces Round #675 (Div. 2) based on the tasks of the [contest:297213], and this time we want to offer you to solve the best 5-6 problems of the finals.

Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.

This is the second year that Andersen has been holding the competition, which is primarily intended to support students of regional Universities in Belarus and Ukraine (starting this year). This year, 60 students from regional universities in Belarus and Ukraine will take part in the finals of the competition.

  • The authors of the round are: Aleksey aropan Ropan, Yuri hloya_ygrt Shilyaev, Andrei andrew Mishchanka, Alexander AleXman111 Krivosheev and me.
  • The round was coordinated by Nikolay KAN Kalinin and Ildar 300iq Gainullin.
  • The round was tested by: Boris ReD_AwHiLe Serenkov, Yahor kefaa2 Dubovik, cckk4467 and rafaelgo2.
  • And, of course, thank you very much Mike MikeMirzayanov Mirzayanov for creating the polygon and codeforces platforms.

Thanks a lot for your contribution to the preparation of the round!

Good luck to everyone in the upcoming competition! :)

UPD: The editorial was posted.

Congratulations to the winners of div 2:

  1. kuticpcer
  2. SevenDawns
  3. Its_Gumball
  4. iamgqr
  5. rishant_m

as well as div 1 winners:

  1. jiangly
  2. dorijanlendvaj
  3. vepifanov
  4. krijgertje
  5. darkkcyan

Thank you all for participating!

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual time + Comments on Scoring Distribution

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Stay hydrated!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +126 Vote: I do not like it

    Why do I get the strange idea that some people just copy what I say?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Last time I saw you was orange and setting great contests. Congrats on getting grandmaster :)

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Everyone beware!, Comment section hijacker is in the house! (why not hit 200 with this one ?)

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I wanted to see if a green warrants less upvotes than a red :P (which it does, as expected)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Well it doesn't help that people remember that Monogon wrote it first already

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

        Hey, he was a tester when he left the comment. I think, big part of it was tester appreciation.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        You forgot that people are less likely to upvote something if you're the 2nd person to say it and that it's more important that the comment poster was monogon than that the comment poster was red.

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

      They are copying your strategy to get contribution points.

»
6 weeks ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

Last time the contest was nice. Hoping the same this time as well.

»
6 weeks ago, # |
  Vote: I like it +96 Vote: I do not like it

Clashes with El Clasico

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I have a question to ask the author. Compared with other div2 competitions, the questions in the last preliminary round are already considered difficult. Are the questions in the finals more difficult than the preliminary rounds?

»
6 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Codeforces Cotest at 8:05pm El Clasico at 8:00pm What will you choose!

»
6 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

El Clasico at 20:00.Is it possible to reschedule the contest!!

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

So I can't watch the El Clasico.

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

clashes with ieeextreme

»
6 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

I actually have a college assignment due today, can this round get rescheduled to tomorrow?

»
6 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

scoring distribution?

»
6 weeks ago, # |
  Vote: I like it -66 Vote: I do not like it

Is it rated?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    It is clearly mentioned in the bold letters in the post that "**It is rated for the participant with rating lower than 2100**

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You forgot to bold..

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I selected that B (Bold)option from the cf editor but it didn't work.Can you please help with this?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is clearly mentioned in the bold letters in the post that It is rated for the participant with rating lower than 2100

»
6 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

El classico or codeforces round 678??

»
6 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Me, but I am not proud of it

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      Well I'm not proud, I'm just trying to make my contribution to 0 but got downvotes xD

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it -16 Vote: I do not like it

        I can totally understand you bro....I had -76 contribution on my other account once and had no hope of becoming it positive but now it is 70+ (+146) -> I got it in only two weeks..You have to be smart...not just comment anything..

        But again I am not proud of it..

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          You are talking as if upvote count is some kind of a measure of your skills.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this time is good for me.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No Ronaldo No Like

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

when someone asks about score distribution:

downvoters be like****:Today we will make your contribution hit a century in negative axis.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait if its rated till 2100 then the actual level of questions will be Div 1 I am not sure

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

Codeforces : There is a contest at 17:xx MSK.

Random user : The round clashes with 17:xx MSK. Is it possible to reschedule the contest?

»
6 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

score distribution ?

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

Score Distribution Vladik ???

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be dynamic scoring?

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

queueforces

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Why such a long queue for submission?

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

what is the problem with prob A. you guys are changing prob statement while contest is going on. time to say goodbye to this contest....:)

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Getting unexpected error on submission for B.

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

getting unexpected error. can't submit b. what is happening????

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Getting unexpected error while submitting B. Please fix!

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

not worth the frustration. going to eat dinner instead

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

unable to submit solution :(

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

This round should be unrated. Unexpected errors, long queue etc...

»
6 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

I don't mind long queues, atleast everyone is on the same disadvantage. But this unexpected error puts people who solved the problem first on a disadvantage. Please make this unrated.

»
6 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

Wow! I wonder how the good idea of making this round "RATED" even the submit was delayed for about 10 minutes LOL

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    How about make another Rated Round with 10 munutes delay together? It seems very good idea to make great round!

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I am not sure but I think it is taken care of bcoz for problem B some people who have submitted after me have gotten more points thus compensating for the 10 min delay.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +139 Vote: I do not like it

    I've read the logs — the issue with the unexpected error during code submit was fixed in less than 5 minutes.

    Queues also were fixed quickly. Plus the longest time to judge was only 459 seconds (most submissions which faced a queue were judged much faster).

    Are you sure that less than 5 minutes of such a breakdown plus some queues at the start are worth sacrificing a month of work of problem writers?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      What's wrong with semi-rated?

      TL;DR 5 minutes makes a huge different for greens/greys.

      Personally, I made 5 attempts on problem B which probably took around 10 minutes longer becuase of queues. Since I only solved A and B (like a lot of greys and greens), this change made a huge difference.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        What does semi-rated mean? How would that be implemented? Does the leaderboard change? Do the ratings get calculated against the ratings of people who drop out as well?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          All rating changes get cut in half.

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

      Testing round 17 before global round 11 seems a better idea for most of the contests.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      MikeMirzayanov Do you think people just kept hitting submit button for 5 mins straight or magically knew when the error was fixed and submitted in the very next moment? Even if the error was only for 5 mins, it has cost more time than that for most people. I'm sure there were some people who got frustrated seeing the large queue and left the contest as well.

      And about your question, 5 mins of breakdown + queues affect people a lot, especially during the beginning, so yes, it is indeed worth it.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        MikeMirzayanov, I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Now, I definitely agree that the setters did a lot of hard work, but at the same time, the starting five minutes of the round are much more valuable for a newbie/pupil. So, you should make this round semi-rated. I think it's a good compensation for both the setters and the participants. And, note that-regardless, this round will be unrated for me. So, I am actually unbiased over here.

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

I dont wanted to say this but In codeforces nowaday contests is just for speed test like even newbie like me can solve 2-3 task while previous contest used to be tricky and we needs to think for sometimes....Please we need lesser but better contest,,,I know downvotes is coming since newbie has commented..

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -36 Vote: I do not like it

    Instead of conducting many contests under Div2 and setting easy problems. Better Codeforces should conduct more contests as they are doing now, but the contests must be distinguished between Div 2 and Div 3 perfectly.

    Because it is sometimes disgusting to wait for Div 2 contest and the finding Div3 or Div4 level problems in the contest :(

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      Lol mate, you've solved only 2 in this contest. Big words, though.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm talking about all contests nowadays, not this one in specific:)

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

      Well it certainly does not contain Div3 or Div4 level problems(looking at your own submissions (you manage to solve only 2 in div3/4..certainly not)). The problems are great and balanced but the contest would have been better if there were no queueforces, delays etc.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    See the thing is A is cakewalk, B is easy constructive, C is cool and enjoyable and D seems tricky...perfect for a Div2 contest.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I don't understand your point at all. You solved only 2 problems this contest, and took 30 minutes to do so. Didn't you need to think? What's bad about you solving 2 problems out of 6? Are you lacking challenging problems?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it -71 Vote: I do not like it

      I left the contest cause when I submitted problem it goes in long queue for 2-3 min and by the way 3rd was comparatively too easy than div2 3rd used to be earlier(I solved 3 unofficially)....and not specific for this contest from last 3-4 contest,it is coming same ,like first 2-3 problem are below 1000 level which really hurts sometimes if for any reason u submitted 1st slightly late....I just love this site but also hope that questions level should be balaanced...I dont care whether its constructive or algorithmic....

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        You didn't even solve more than a single problem in your last 3 contests(2 were div 2) and now you are bullshitting this.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it -37 Vote: I do not like it

          Its codeforces bro....U can't comment from your main id to decrease ur contribution....Actually u know what this type of contest are really good for pupil and newbie cause they get a good gain in rating...but fact is if for some reason u gets delayed nd ur ranking is below 1900 being expert ur rating is going to decrease drastically thats why I was telling questions needs to be more balanced

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +28 Vote: I do not like it

            Don't expect people to listen to you after writing from an alt xd

            U can't comment from your main id to decrease ur contribution

            If you understand your comment is good, write from main account. If it's bad, don't write it. If it's good but you would get downvoted anyway, then for sure contribution system is broken so don't worry about your contribution. So no reason to use an alt.

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

    Bro see the difficulty level this was a perfect div2 contest. A require some brain as always it involves.

    B trick of just using 2 and 3 as prime numbers.

    C good problem gives you deep intuitions of Binary search . The way the binary search used was brilliant.

    D. DFS problem with a lot of insights and mathematics of finding averages and numbers.

    E Another cool problem involving a lot of thinking.

    F No idea.

    Also see the balance between the number of submissions. '

    A perfect Div2 contest must look like this only!

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but do u think nowadays contest is going good for high rated specialists or experts....If by luck u get late in even one of top 3 then ur rating is going to fall....I can see from ur case also....

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know what you want ratings or practicing those hard problems If your option is first think once again!

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so rating fall doesnt affect u..Rating seriously provides a motivation ..By the way I want to ask u,Isnt is better to judge candidate on the level of their skills rather than how speed he solved....some newbie could have solved first two qsns very fast and some coders let it be u take time in A isnt u get demotivated and panic on seeing ur rank to be 7000 for a moment...Isnt it better having question level something lik 800-1000-1300-1700-....

»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

I would be happy to have a like/dislike button for contests. So I could click there instead of writing bad comments.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    The blog under which you are commenting itself has a upvote/downvote button. Why don't you use that

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Agreed, perhaps a rating for problems as well since a contest may be made of problems written by different writers. This will give feedback to the writers on what people find interesting (and what they dislike), and also help people prioritize better problems during practice.

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    Traverse the array from 1 to r and maintain a segment tree of the last position of X. For each ar[i], find min(lpos(1),lpos(2),...,lpos(ar[i]-1)). If this is > lpos(ar[i]), then ar[i] will occur in the final array.

    Corner case : For 1 to occur in the final array, there must be a non-1 element in the array.

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

    Didn't solve it during contest, but if you could find subarray mex queries in time $$$F(n)$$$ then to find if mex $$$x$$$ is possible for any subarray, consider all pairs of consecutive positions where $$$x$$$ lies, say $$$i_1, i_2$$$ for one, then you need to check if $$$mex(a[i_1 + 1, i_1 + 2..., i_2 - 1]) == x$$$. Since there are atmost $$$O(n)$$$ such pairs you can solve the problem in $$$O(n F(N))$$$.

    One way to solve subarray queries is using Mo's algorithm and keep elements not in current segment in a set, giving $$$F(N) = \sqrt{n} \log n$$$

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the idea behind C?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you can just keep track of the recursion and calculate how many numbers you can pick for position middle.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks but can you elaborate more? what do you mean by recursion?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Put x in position pos, and assume the array is decreasing before x and increasing after x (so it's in sorted order, with x in its spot). Now run the binary search and see how many numbers of this array it accesses. Say there are "l" numbers that it accesses that are less than x, and "r" numbers that it accesses that are greater than x.

    Then it suffices to find l numbers < x and r numbers > x to place in their correct positions. Then can rearrange the other numbers however. It follows the answer is $$$\dbinom{n-x}{r}\cdot r! \cdot \dbinom{x-1}{l}\cdot l! \cdot (n-r-l-1)! $$$

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

    hint for n = 6

    1 1 1 1 1 0
    0 1 1 1 1 1
    1 0 1 1 1 1
    1 1 0 1 1 1
    1 1 1 0 1 1
    1 1 1 1 0 1
    
    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      OR Just

      1 1 0 0 0 0
      0 1 1 0 0 0
      0 0 1 1 0 0
      0 0 0 1 1 0
      0 0 0 0 1 1
      1 0 0 0 0 1
      

      in any value of n

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        For those who are interested, here's our short video with some logic that could have lead to this solution

        Video link

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

D, anyone stuck on pretest 7?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got runtime error on test 5?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah! Have u figured it out?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did for a while, then got stuck on pretest 4 on later submissions >:(

    Some things I fixed to get AC (no clue which caused the WA):

    • Only add single direction edge from $$$p$$$ to $$$i$$$ instead of adding it in both directions and storing parents of nodes (this shouldn't have made a difference but it did)
    • Depending on how you calculate the answer, intermediate calculations can overflow long long, so I switched to __int128.
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pretest 7 was when there is only one child of 1. After correcting my mistake in this case my solution passed pretests

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does there exist an easier way to find subarray-mex-queries (i.e, given $$$l, r$$$, find mex of $$$a[l...r]$$$) other than Mo's?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    The answer is the maximum of ceil(sum/sz) for each node. Sum denotes the sum of all a[x] in the node's subtree, and sz denotes the number of leaves inside node's subtree.

    I don't have a rigorous way to show this but this informal explanation is sort of intuitive if you think about it.

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

      Damn I got it at the end of contest but couldn't code...This problem was a bit confusing, I had to read it again and again.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see your logic, but can't we just simulate the process using bfs and keeping track of updated a[] values ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see. I will try to prove it myself before tutorial.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Proof :

      This an obvious lower bound. We just need to show that this can be constructed.

      Let us show this by induction on subtrees. This is obviously true for a leaf. Now let's show that we can create a root node, and join subtrees that this condition can still be satisfied.

      Let us move all the values on the subtrees to their leaves in the optimal arrangement. Now consider where the people in the root node go.

      Let's say the maximum value of a leaf in the optimal arrangements of the subtree is $$$m$$$. This is also equal to $$$max(sum(v)/leaves(v))$$$ for all immediate children $$$v$$$ since we are showing by induction. We can add to the leaves with smaller values until we reach $$$m * leaves(u)$$$. If we reach this point, that means that $$$sum(u)/leaves(u) >= m$$$. Now we can put the values one by one, and reach the optimal arrangement.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach problem C?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Lesson Learnt from this Contest: Long Queue and Submit button not working doesn't guarantee you an Unrated Contest

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Since when the problems are so difficult? last time I participated was like 6 years ago. :(

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

    I feel contests are getting harder and since lockdown, the competition has increased substantially i.e from around March onwards.

    The level of difficulty has certainly increased( I find old problems of same rating to be easier and I think thats also because of how many people are doing that during contest and it's position) since the competition and no. of participants has increased a lot.

    But anyways, with some practice you will be well off.

    Were the problems more Data structure/algorithm oriented earlier?

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

In D, my O(n*log(U)) solution kept TLEing until I changed long longs to int.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think test case of C is designed to attack O(nlogn) solution

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wouldnt it give WA when sum will exceed int bounds?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant variables that would not overflow, ex. n, p

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just gave up and wrote the $$$O(n)$$$ solution after my $$$O(n \times log(U))$$$ solution got TLE twice.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If I submit a solution which passes the pretests and again after sometime I submit another solution to the same problem which again passes the pretests, then my last correct submission on the problem is considered or the first correct submission ?

»
6 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

RIP queue

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I forgot to print newline in my first submission of problem B and the solution was in the queue. Expecting WA on pretest 1, I submitted again but both passed and I got a resubmission penalty. Can anything be done about it?

first submission: 96543626

second submission: 96544467

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i dont think so.

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

    Yeah happened with me for C, got a resubmission penalty and last submission was considered so overall a good negative in total score.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Man… I did B in 13 minutes and I resubmitted after two hours a better solution, just to make sure it will pass the official tests. I didn't know that only the last submission counts. Now instead of +25 I get -60.

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

Can someone explain why i am getting Runtime error in pretest 3 of problem C

My solution 96588906

Thanks in Advance :)

»
6 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

The problem E is a problem of 2013 ICPC Hangzhou online.

http://acm.hdu.edu.cn/showproblem.php?pid=4747

BTW,I'm in Hangzhou now so I am familiar with this problem.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?? need hint and ovservation.thanks in advance.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about the order of the binary search. Every position in the array has a distinct binary search order. By tracing the direction of the B.S., you can reconstruct possible values for each "middle" position.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just stimulate a binary search and check the path that binary search follows in there and count smaller and bigger for x during that simulation. After that its simple PnC .

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

    in binary seach we make jumps from mid to val that we need..., so when ever we come to some point. we just need to check weather to jump forward or backward.

    to jump foreward we need to put some value at that cell that is less than x. choices that we have is n-x for this cell in array. to jump backward we need to put some value at that cell that is greater than x. choices we have is x-1.

    now if you make two jumps forewards, choices to put values in those cells are n-x for first cell and n-x-1 for next cell. total choices are (n-x)*(c-x-1)

    after you fill and calculate all cells where you jumped. the permutation of remaining cells doesn't matter. you can permute all the rest of cells.

    eg 4 1 2

    we jump to 2 (4+0/2).

    val[2] == 1(x) [it is given value at 2 is 1]

    choices that we have to fill jumping indexes is 1 (only 1 was filled no other choice).

    ans = 1 * fac(3), [3 is number of cells whose value doesn't matter]

    ans = 6

»
6 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

[DELETED]

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

    its strange because as i checked it doesn't ouput correct on the test below

    16 927

    59 72 10 90 73 72 75 47 30 59 90 16 76 82 48 28

    it outputs NO while the correct answer is YES|:

»
6 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

O(n^2) solution didn't work for E ? I thought that for n = 10^5 , it should be fast enough

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it won't pass because you can probably do 2*10^8 low level operations per second in cpp.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n^2 for n=10^5 would mean 10^10 operations which gives TLE.

»
6 weeks ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

sorry

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

    Hmm. So 10 minutes of queue affected your chances at trying ABC, and therefore you couldn't solve them? Don't talk bs man.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can we solve D using binary search??

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

    I tried using binary search. But got various results except AC.

    My idea : Binary search on the minimum no. of citizens bandit can catch

    So, basically i fix the answer and check if its valid or not.

    https://codeforces.com/contest/1436/submission/96583528

    UPDATE : I understand that its failing because of overflow.

    Each leaf can take atmost 2e14 citizens. So, we carry forward 2e14 to 1e5 nodes. So, the value goes to 2e19 which leads to overflow.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you can. 96579469

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is your valid function of binary search?

      valid in the following sense:

      lo=0,hi=n;
      while (lo<hi) {
        mid= lo+hi/2;
        if (valid(mid)) lo=mid;
        else            hi=mid;
      }
      ans=lo
      
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello there, can anyone help me with approaching problem C? I'm a newbie so please bear with me.

Here was my idea but seems like something is wrong here:

for example, for the testcase 123 42 24,

to reach 24th position, we need to go via 61st, 30th, 15th, 22nd, 26th, 24th positions.

And we can have 41(<42) numbers on position 61, 40 on position 30, 81(>42) on position 15, 80 on position 22, 39 on position 26, and 1 on position 24(i.e. 42) and the rest of the numbers shuffle in remaining positions. Therefore, 117!*39*40*41*80*81 % (1000000007) should be the answer.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We will go like this 61 30 15 23 27 25 24

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, if you use the pseudo code provided, the positions are 61, 30, 15, 23, 27, 25, 24.

    Second, if a position is to the right of pos, you should use numbers that are greater than x, since you want to go to the left. Similarly, if a position is to the left of pos, you should use numbers that are less than x, since you want to go to the right.

    So the answer is actually 116! * 81 * 80 * 79 * 78 * 41 * 40 Check.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn! Probably miscalculated due to frenzy. I was right all along. Wasted 30 mins on this :( Anyways thanks a lot for explaining!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well tbh I didnot read your approach but I will try to explain it to you easily....

    Notice that we only need to constrain logN number of positions. This is because in binary search there are logN steps to reach target each step follows a specific sequence of path to reach the target. This sequence of path is determined by the classic BS alg as given in problem.

    Now if your target pos is greater then mid that implies the element at mid must be less then x(inorder for BS to go right) and vice versa.

    Count the number of such positions where the element is constrained to be less then x and vice versa.

    Answer can be found using simple combinatronics.

    Here is my submission :

    C
»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

In problem E, why doesn't DSU work? I kept getting WA on TC 3.

Edit: Nvm, I found my mistake.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Honestly, I don't like Problems which are directly dependent on slight variations of standard algorithms. For problem C, I always update right as middle-1 and not middle itself. So during the entire contest, I tried debugging but couldn't figure out that it was a simple misreading of the Problem statement.

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

    But you should just follow the recursion given by the code in question.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Just because you don't implement an algorithm the way it's written on the problem doesn't mean it isn't standard. Using [l, r) instead of [l, r] is not a "variation of standard," it's just another way to implement it.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      I agree it was my mistake to misread. My point is different people implement standard concepts in different ways. So I personally dislike those Problems where the authors implement their version of the standard concept and we're forced to work accordingly. Anyways, lesson learned!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong with my code on problem D . wrong answer on testcase 7

96592768

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When I want to submit my code, it says you did not register for the contest. Did I really forget to do that or is it just a system problem?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1436/submission/96590709 problem c ,error on pretest 3. i dont know where is the error,any suggestion?? what i did is

a! * b! * c! * d * e a=total moves to get to required position that is pos using binary search b=moves where mid < pos c=moves where mid > pos d=bC(x-1) e=aC(n-x)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check for n = 1.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The idea behind all of this is a bit math-y, but division and modulo don't play well together. Take for instance (6/2)%4, the correct answer is 3. However, if I first take the modulo of the numerator, then of the denominator, and then calculate, I get 2/2 = 1, which is not correct.

    In func, when you have

    for(long long i=1;i<=x;i++)
    {
        ans*=(n-i+1);
        ans/=(i);
        ans%=mod;
    }
    

    a similar problem may happen. You base your code in the fact that ans * (n-i+1) is divisible by i. This may be true if you didn't have a modulo, but since you modulo every step of the way, it may be the case where this isn't true and you end up with an incorrect answer.

    To calculate (nCk), use Pascal's Rule, nCk = n-1Ck + n-1Ck-1 or multiplicative inverses instead.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted 30 minutes in C just to realise in the end that my code was failing at n = 1 .

(Sad reacts only)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello!
Can someone please help me, I don't understand what is wrong with my solution:
https://codeforces.com/contest/1436/submission/96569147
My approach is to get 2 as the sum on all rows and columns

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

    Since the problem is multi-test, you should reset any global variables before/after each test case. For instance, n=4 leaves you with

    1 1 0 0
    0 1 1 0
    0 0 1 1
    1 0 0 1
    

    if I'm not mistaken, but if the next test case is n=6, you're left with

    1 1 0 0 0 0
    0 1 1 0 0 0
    0 0 1 1 0 0
    1 0 0 1 1 0
    0 0 0 0 1 1
    1 0 0 0 0 1
    
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

weak pretests on C, stupidly missed an obvious mistake and it passed.

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

Damn My B will FST as I mistakenly saw n<100 .!

Passed but how?

Wasnt there n=100 as test case

by the way big case for me.

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

https://codeforces.com/contest/1436/submission/96589733 Can anyone tell what is wrong in this? Problem D using binary search

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

FSTs on C incoming!!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lets have a good night's sleep then before rating changes.

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

Is it just me who thinks that A & B were too easy for Div2?

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Disappointed as this contest had less number of pretests and the pretests were weak!!

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

FSTforces. Cool problems though.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I am not claiming that the round should be unrated, but let me tell you one thing

For A, i checked if the sum of the array is a multiple of m , it passed the pretests and later i got hacked and lost 350 points

For C, i submitted and got Runtime Error on test 79....So yeah sad contest for me!

Cheers all! Kinda sad a good contest was turned into a worst one(for me)!

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

hi guys. right now my solution for c is in queue, if my problem c got accepted you all can downvote this comment so hard!!. but if my solution got failed please upvote(it will make me feel better). and i think its funny to do such things. you will probably see more of these comments from me XD

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 10 in C ??!!! I dont see why my solution would fail :(..Anyways I fastforced A and B so my rank went up lol.

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

    Their binary search algorithm is really dumb, if you look at the code in the problem their algorithm keeps going even after it finds middle...

    If it's any consolation, I and many others FST'd for the same reason :(

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

      OMG! I didnot even look at the algorithm and just assumed it was a normal BS(Binary search). But turns out their BS was actually BS(Bu*lsh*t).

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1 I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Yeah run these permutation against their algorithm....

          1 3 2 -> L : 0 and R : 3 and MID : 1

          It should stop here XD..but it still goes on due to stupid L.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is no such thing as "normal BS" Obviously bs can go different paths depending on the implementation.

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

          By normal BS.. I meant the one which usually stops when an element is found and doesn't go around frolicking.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Funny thing
            Because I always write BS that "goes around frolicking" instead of stopping when the element is found.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Good for you.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                well, ok, it does not really frollic. But it does not stop. The point is that there are different implementations and should've written the answer for the given implementation, not for the one in your head.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n=1 i think

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

This pretests...

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

Damn, I failed systest in D because I said $$$10^9*10^5 = 10^{13}$$$, and also in E because I used a segment tree of size $$$n$$$ instead of $$$n+1$$$. If this contest was rated for me, I would be drowning with my own tears :P

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

One test Case , One Damn test Case and more then 1000 people got their rank dropped by 1000+....

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I understand that the authors worked very hard for preparing this contest, but the issues are really too big to ignore at this point.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I completely agree, Most of the FSTs could easily be resolved if only the verdict was WA instead of pretests passed.

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

What a blood bath in Problem C!

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I've never seen a contest with pretests this bad for almost all problems

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The thing is this contest is a "based contest" .. I just wonder what happened with the people who gave this in official time

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is a based contest?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Problem in this contest were from a official competition mention in the title of this blog and hence we say that this contest was based it. Moreover It was a final man.. RIP My C "pretest passed" :/

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          its funny how every one made same mistake of stopping iteration on stisfying mid rather than both limits.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It even funny that not only we both but many many many people did same ......

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, "based" contests, contests with some names in titles and contests with specific sponsors often have their peculiar features. While not all of them are perfect, they add some diversification to rounds

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Why mathforces...

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Not expected such bad pretest! Good contest turned worst , long queue, bad pretest ...

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope they don't make the round unrated. Even if it had some problems.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Goodbye color, hope to cya soon...

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

weak pretest for DIV2 B

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

While I agree that the contest had its problems, I don't think that "weak pretests" should ever be considered a serious issue.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm biased because I have a positive delta, but I agree. There were 5 pretests on C and 7 on D. Pretty obvious pretests are weak.

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

    You are saying that cause you didn't Failed any problem on ST

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

      I always say that. Not only in this contest.
      I believe people rely on pretests too much and it is their mistake

      It is true that I haven't failed on ST. In fact I have only failed on ST once for all 50+ contests I took (yes, I was sad when it happened, but it never came to me to ask to make the round unrated because of that). What does it mean? Probably I think about corner cases more then others, I dunno

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

        Agreed on that. But, we are wanting to make this contest reason due to a bigger reason other than having weak pretests. I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Understand that we are talking about this issue. Don't trivialize it by talking shit about weak pretests. I understand that you might get to CM after this round, because you didn't FST. But, don't lose your conscience and start acting like an asshole. Apologies if I sounded too rough, but I am calling like I see it. And by the way, this round(rated or unrated) is the same for me either ways. So, I am actually unbiased over here, unlike you.

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

          So, I am actually unbiased over here, unlike you.
          I left the contest out of frustration

          Yeah, totally unbiased.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Well, I am unbiased in terms of this round being unrated for me regardless. I don't have anything against the setters. I thought the problems were still nice. My problem lied in the technical issues that transpired. Anyway, if you still feel like giving a nice sarcastic comment, feel free to do so, brother! :)

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

i know i was stupid to break when i found the match , but man the pretests for "C" just sucked.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you get why the answer to test10 is 0 ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      my code failed on testcase 10 but i don't know why. I this its answer should be 2 not 0

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yea I just did, change the break statements in your submission and then see the magic

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        check their binary search. you've put if mid==pos, return; which is not the case actually acc to problem.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got it

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

in third question for testcase 3,3,1 my output is 2 why is it wrong there are two possibilities for 3 at pos 1 1. 1 3 2 2. 2 3 1

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The pseudocode they have given in the problem is a bit different. It does not find 3 at position 1 in the possibilities you mentioned.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

why is answer to this case 10 : "3 3 1" 0 .. Cant we have 2 3 1 and 1 3 2 ? Clarify where am I going wrong

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Elements at both index 1 and 2 are processed before the search stops. So, arr[2] must be greater than arr[1] to direct the search to the middle. However, this is not possible since 3 is the largest number in the permutation. So the answer is 0.

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

    For the case of 2 3 1. First, it will set l = 0 and r = 3. Then, it will set mid = 1, check it, and update l to 2 since a[mid] is equal to 3. For the next iteration, mid=2, check, and l will be updated to 3 since a[mid] equal to 1, which is less than 3. Then, the loop is over, check a[l-1] you will get 1 instead of 3.

    The same scenario happens for the case of 1 3 2.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes sir I just realized that I am so dumb that I put a break statement there. Oh man I am so dumb :(

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

    Anyway, the pseudocode itself use the right-exclusive style of indexing (I don't know the usual term, but I always call it that way), which instead of pointing the element, the index is used to point the room divider (barrier between two element). That's why in the beginning it sets l = 0 and r = a.size(). This way of viewing array is useful for the case of splitting array, so instead of being confused of using mid - 1, mid, or mid + 1, you can directly use left to mid and mid to right.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Someone explain for C testcase 10, why for 3 3 1 the solution is 0 ? for this case mid will be at 1, so after putting 3 in 1, we can arrange the remaining elements in 2! ways i.e 2, since the other elements don't matter. So why 0?

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Pretest Sucks a lot. I lost two problems.

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

idk if this was on purpose, but thx for nice time limit in D. My binsearch solution got 1341 ms.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved B very late. Any suggestions for me?

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1. I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0-based indexing

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The binary search is given in the question is slightly different ;_; The loop will run two more times and final value of left will be 3.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same doubt !!?

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Did anyone fail in Test Case 52 in problem C? Can someone explain me why am i failing this testcase

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I failed 51 because I forgot to take mod after 1 step. I think I am retarded.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C: can anyone explain test case 3 3 1 my code is giving 2 but the answer is 0.

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

    So there are two permutations
    1 3 2
    2 3 1
    Regardless of which one you consider bs will pick at 3 and move the left pointer forward So you have left=2, right=3 Then you check arr[2] (1 or 2) and bs tells you the answer is on the right, where it does not exist

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

why in c problem for test case 3 3 1 output is 0 ?

It should be 2 , Am i right?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am just feeling dumb, as I didn't submit A even after solving it, assuming that I sumbitted it and rushed to B.

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

This contest should be unrated. I did not like it. In the starting, it took a lot of time to know the verdict. I submitted 2nd question thinking that it will be right and moved forward to 3rd question as getting the verdict was taking a long time. When I solved question 3 after then I came to know that I have already got WA on 1st pretest. This wasted my 10 minutes !! Even after then I successfully passed pretests of 3rd, but in the final checking, it gave WA on test 10. Pretests were weak and few, may be to reduce the load on the server. That's not a good idea. Completely disappointed after giving this contest!! RIP RATINGS !!

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

Did anyone else's D fail on test 78? If so what was the mistake you were making? My Submission

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Input 3 3 1 Participant's output 2 Jury's answer 0

Can someone please explain this test case to me, because I feel 1 3 2 and 2 3 1 are good but the jury's answer is 0

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is for question D

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

    It seems like its for question C.

    If you see original pseudocode implemented on the statement, you can know that you should not get out of while if pos == mid.

    Neither am I know why did author implement binary search like that... but that's the reason.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry it's for question C

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

Can someone help me find out the problem with my submission to Problem A? My submission 96540614 is failing on test case 29.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you think this is true?

    1.0f + 1.0f == 2

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, it is.

      See this.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1/3 can't be expressed exactly in decimal system it can be expressed exactly in a system with radix 3. Similarly, Binary also stores some decimals only to some level of precision.They should be avoided whenever possible, here there is an alternate way. The sum asked is simply the sum of all elements in array.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem A have a possible arrangement such that the sum is not m but it is still ok ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Still wondering what was the reason for queue

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

For those who are interested in problem B analysis here's our short video with some logic that could have lead to a common solution.

Video link