pitfall's blog

By pitfall, 2 years ago, translation, In English,

Hello everyone

On Monday, December 19 at 19:35 MSK held Codeforces Round # 388 for participants from the Div.2. Participants from the Div.1 may participate out of the competition.

This round was prepared by Denis pitfall Bezrukov, Alexey dalex Dergunov, Vyacheslav Slamur Muravev, Egor Petruchcho Ponomarev, Pavel craus Semushin и Andrey Shlakoblock Gaidel.

For me and Slamur and Petruchcho this will be the first round. We hope that everyone will find interesting problems.

Great thanks to Gleb GlebsHP Evstropov for his help with the contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

UPD: You will be offered 5 problems and 2 hours for solving them.
Scoring: 500-1000-1500-2000-2500

Congratulations to the winners!

Div.2:

1. just29
2. tnbt
3. el_smurfo
4. SimB4
5. skydog

Div.1:

1. I_love_Tanya_Romanova
2. W4yneb0t
3. enot.1.10
4. gritukan
5. Um_nik

UPD: Editorial available here

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

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

It is incomplete without this. ** ** *****?

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

    Yes, it is rated.

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

      Why does the guy who answers that question get upvoted? Anything can happen on CF. :/

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

      Can one please help me As Scoring: 500-1000-1500-2000-2500 But whose rank is in be 2000 to 2200 Got negative ratings Please explain

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

        Before updating your rating after the end of the round, for each participant his seed is calculated, that is the place that the participant is expected to take in this competition. Thus, two things are known for each participant — his seed (the expected place) and rank (the actual place). Depending on the difference between these two values, your rating increases or decreases. If the difference is higher, your rating changes more.

        You can read more about it here: Codeforces Rating System — Codeforces

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

    Fixed: It's held at the unusual usual time.

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

      No, it is held at the usual unusual time.

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

It would have been much better to have these contests on two different days this week instead of having 2 contests on the same day and then not having any contest till next week.

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

    If this is the time chosen by the CF management, there must be a reasoning behind it.

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

    Acctually Codeforces round 386 and 387 is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. But the Codeforces round 388 is an usual Codeforces div2 round. That's why we have 3 contest in just under 24 hours, the first 2 is like mirrors of the Olympiad and the last is the usual round.

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

Time is usuall but nember of problem isnt : (

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

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

A previous contest had very fast system checking and rating changes. Hope this one will be the same! Though it is so unusual to write contest in the morning and then on the same day at the evening =))

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

Hope I will not repeat my usual mistakes and solve first three problem ASAP. Maybe life is nicer as Blue.

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

thx a lot for these consecutive contests (#388,#387,#386,#385)...it helps our ACM team for ICPC-Tehran Region

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

Wish me luck! I'm at only 25 points of Div. 1. These 2 days of contests have favoured me.

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

Perfect time for programmers from Bangladesh :)

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

There are a great many of contests in the end of term :D

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

Expecting interesting and doable problems.Thanks Codeforces for organising so quick rounds and really appreciable work done by all the problem setters.All the best everyone!!! :)

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

Good decision the number of problems decreased to 5! (Pennyroyal_Tea this is not factoriel). thanks

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

    I guess even tourist can't solve 120 problems in 2 hours, so 5! is too much I believe.

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

Hope not to drop after doing well last contest.

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

my 3rd contest on CF in 30 hours!

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

Good luck everyone ! Hope everyone gets what he deserves !

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

and now the pleasure comes to it's end...

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

I wish this contest will be great for all of us

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

I think, this is my first time when I Submitted 3 code, all got pretests passed. I hope it stays as good. I gave up on problem D and E.

Actually 5 submission, but the other two was wrong programming language, and forgetting reading input which make it fails on the first testcase.

lesson learned, if you hardcode the problem testcase: don't use the first example.

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

    Don't give up yet!! You can do it!!

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

    Also the first time for me by solving A,B and C!All three passed :D

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

Can someone explain problem E's statement?

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

First time solved 4 problems. Hope they will all pass :D

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

Bbye Blue

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

What's the C hacking case was please?

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

    Mine was: 21 DDDDRRRRRDRDRDRDRDRDR

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

      What should be the answer?

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

        Answer is R

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

        My answer is D

        UPD: wrong

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

          Yes, it's wrong. 21 DDDDRRRRRDRDRDRDRDRDR: here first 4 D's will beat any 4 R's but one R in first R's group will stay anyway. So, after each full iteration we will have this sequence of state: 11 DDDDRRRRRRR => 4 DRRR => 2 RR, so R is winner.

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

            could you please explain test#21 of this problem? (7 RDRDDRD) i am getting R in this (correct is D).

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

      What is answer?

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

      The answer is R, isn't it?

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

      What's the correct output?

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

      What is the answer for that?

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

      Well RIP my C :(

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

Hack case for C

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

:( :( :(

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

I think I will lose around 50 points.. I checked my program for B on wrong input, thought it was wrong and resubmitted it again.. Turns out it was correct earlier.. Lost 300 points, and fell 700(!) spots on the standings... :(

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

Very interesting contest, thanks to pitfall

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

Who else tried to simulate C? Worst decision of my codeforces life -_-

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

    I got passed pretest with simulation.

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

    I did... It was passing pretests with 998ms. So I rewrote it and now I realized my rewritten solution is wrong.

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

      And I didn't even finish my first solution ;_; . Linked list and shit. I knew it was a hacking problem, so simulation felt safe. Never again would I ever again.

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

    If you simulated using a queue, it was easy and fast. (And correct, I hope)

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

      Queue didn't come to mind sadly. Sets take a lot of time to erase( from previous experience ), so I jumped to linked lists ;_;

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

    You could simulate and even afford an extra log factor(I did this and got 778 ms main tests) for total O(n lg^2 n)

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

    I used simulation and got Accepted

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

    I simulated it, but I used next array (using DSU) to avoid TLE. Which is to jump over the cells that are already deleted. 23151066 my run time is 15 ms because the complexity in total is O(n).

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

      I used simulation on input array with two pointers and bool array of deleted and got AC. You won't get TLE cause it's O(n*logn). 77ms in my case

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

    I simulated it. I used two set<int> and lower_bound in them. 23155161.

    PD.: Sorry for my horrible English.

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

    I'm simulating using list as well, (well array because python doesn't have native list, but it behave like list)

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

Solution to B could easily be found on google.

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

Seems like editorial for problem B is published even before starting the contest. :3

Link

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

Can someone explain why this interpretation of E is wrong?

Choose the segments: [2], [3], [1], [2, 3], [3, 1], [2, 3, 1]

For the first three, there is 0 chance of an inversion. For the fourth and fifth, there is 1/2 chance, so the expected value from those is 1/6*1/2*1 = 1/12. For the sixth, you can have [1, 2, 3] = 0, [1, 3, 2] = 1, [2, 3, 1] = 2, [2, 1, 3] = 1, [3, 2, 1] = 3, [3, 1, 2] = 2. So the expected value is 1/6 * 1/6 * 9 = 1/4.

Isn't the answer then 1/3?

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

    You permutate the smaller segment but the whole array still exists.

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

It didn't take me much time to solve ABC, but failed to figure out the last two

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

    I know that feel, bro. I hope we don't fall in our ranking

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

if your C solution is just deleting the first undeleted instance of opposite party (which apparently passes pretest) then it can be hacked. My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1, pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D.

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

    What should be the correct answer?

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

    How can the answer be D?

    My answer is R, btw.

    And I use the 'wrong' algorithm.

    UDP: And I passed the system test.

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

      Everyone here seems to misunderstand what he meant. He said the first undeleted instance not the next one. My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1, pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D. If he meant the next undeleted instance, he would write "pos 2 kills pos 3" and so on.

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

    My solution is just deleting the first undeleted instance of opposite party,

    and it PASSED the system test.

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

How solve E?

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

    Consider positions i and j, then element at pos-j can be less than element at pos-i only if we choose a segment that covers both i and j and then choose an appropriate permutation.
    Suppose we fix the segment, then above prob = P(for any r-length segment) = (put j before i if i is placed at pos=k) = 1/r*(sum(k=1..r) (k-1)/(r-1)) = 1/2.

    So, just calculate number of segments that cover positions i and j(for all i,j) and multiply overall by 0.5.
    1. For i<j a[i]<a[j] we have sum P=(i+1)*(n-j)/(n*(n+1)) to our final result.
    2. For i>j a[i]>a[j] we have to sum P=1-(i+1)*(n-j)/(n*(n+1)) to our final result.
    Both can be done similar to finding inversions either using divide and conquer(like my solution: http://codeforces.com/contest/749/submission/23156836 ) or BIT for O(n*log(n)).

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

    linearity of expectation
    for a pair i , j , such that i < j the probability of j become more than i is p where , so if ai < aj , add p to answer else add 1 - p to answer. To do this in O(NlogN) , use bit.

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

      Can you explain a little more? i and j affect other indices as well. Can you show that linearity is justified here?

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

No more contests? But I got used to these consecutive contests :(

They were really fun though, thanks codeforces :)

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

How to solve C without simulating it?

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

    Actually you have to simulate it, but in an efficient way. One way is to use queues, you can use, 1 for all people who is available to vote, other for people in R and other with people in D. The trick here is to realize than in every "iteration" people alive is greatly reduced.

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

I was trying D with square root decomposition. In each bucket, I maintained how many times a number is occuring in cnt[bucket][x] and tot[bucket] is the number of elements in this bucket. Finally start from last bucket and if count of numbers (given in query) in present bucket equals to the tot[bucket], then this bucket is useless and go to bucket-1. I couldn't submit and check though. Has anyone done like this?
Link to code

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

D was awesome ! However, I couldn't finish it's coding before the contest ended. I was using segment tree and storing bids in it. Was I going in correct direction ?

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

    YES :D. I use the same solution :)

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

How to solve D?

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

    i used parallel binary search but i guess its probably overkill

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

    I used the following approach.
    Let's insert every people into set. And just delete peoples in query when query comes. Now last element of set is people who won. And now you can erase last element of set and find money. After everything is done you should insert everything you deleted.

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

      Did this solution passed system tests?

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

      Sir I used the similar approach but i m getting TLE (Time Limit Exceeded)

      I inserted all auctions in a map with keys as the amounts (since they are distinct) I stored all amounts and auctioners in two arrays(named as arra,arrp) to store sequence in which the auctions were made.

      Now in each question, I deleted the k elements and on deleting each one of such k element , i check the position of this deleted auction in arrays arra and arrp .Let it be pst. Then i check if pst-1 and pst+1 have same auctioner. if yes i delete the auction at pst +1

      I m getting TLE . This is my code

      How did u check the condition if we remove an elemment its prev and next may be same How to remove right one?

      Even if we ignore that for q questions we are inserting k elements in the set or map each insertion/deletion taking log(n) time giving total time complexity of O(q*k*log(n)) where n <= 200000 and q<= n and k <= n will this approach satisfy constraints?

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

        You are deleting all of k people's bids, which can be equal to n some times if you sum the number of bids for each k peraon. This way there can be a test case with 2 people, each made 100,000 bid, and 200,000 queries asking you to delete these 2 people.. this way the complexity will be O(n*q*log(n)) which is too much.

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

          Then sir what is the correct approach?

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

            You must keep only one version of each person (only the last bid) and sort them by their last bid in a set for example. now if you remove the k people deleted, then the total complexity for all queries will be O(x * log(n)) where x is the sum of all k s which is at max 200,000. After removing the k people, the person who won is in the end of the set. To determine in which bid this guy won, you should have a vector for each person which his bids. You can do a binary search to find the answer. now before moving to the next query. Add the deleted people back to the set. also total of O(x*log(n)).

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

    i used a set to put every person's "best" bid in it. i also made sets for each individual person which contained all of their bids. Now for every query , i traversed the bestbid set from end, when i found the bestbid whose bidder is still available (to do this i used binary search on all bidders who didnt come). the bidder no can be known using this,let him be y.but the bid maybe lesser than the bestbid of this person,so i again travelled the bestbidset to find another such person who came. if his bid was x , then i have to search bid greater than x in y's bids.i used lowerbound for this purpose.i use x=0 if no x is available.

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

why does this code passess while this does not for problem B? I only used 'cout<<3<<endl' instead of 'printf("3\n")' in the pretest passed solution :/

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

    You shouldn't use printf with ios base synchronisation turned off.

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

      The order between printfs and couts has no guarantee

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

    Because you use std::ios::sync_with_stdio(false). If you use this line in your code then it's better not to use scanf/printf. It will be a mess because iostream and stdio can't sync thus the order of output won't be same as you expected.

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

      bummer i didnt know that i only saw on a blog of cf that it makes cin and cout as fast as scanf and printf and thats y i was using it just like that :(

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

C test case 21 anyone? :(

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

Extremely fast system testing...

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

Wow this system testing was faster then the time it took me to fall from expert to specialist

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

My solution C simulating statement is accepted. is there any solution without simulating?

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

In problem B, Test Case 4:

1000 1000 -1000 -1000 -1000 1000

Ans shouldn't be 3?

3 1000 -1000 1000 3000 -3000 -1000

-3000 and -1000 does make a parallelogram with other 3 points, doesn't it?

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

    Yes it does.

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

    For all case answer will be three and one can easily get the solution in google.

    A little bit changed in problem would be better.

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

Is it just me or was the system testing really really fast ????

:)

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

Hi guys,

Could anybody tell me where is the editorial for the problems? Got stuck in C.

Thank you very much!

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

So what's the real solution for C please , I'm pretty sure i'll be around 1899 because of this C haha.

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

    I used a queue to simulate..

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

    You can use set to simulate the optimal moves.

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

    The solution I used is O(nlogn). The current candidate removes the next voting candidate of the opposing party. Use std::<set> to keep track of available voters.

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

    I kept two treesets (ordered sets for c++) holding the indexes of each R and each D. starting from 0, I simulated each D skipping the next valid R, and each R skipping the next valid D. What I would do is delete them from the tree set when someone was skipped. Additionally, Tree sets allow you to query the lowest number greater than a given index in log(n) time. So my solution was O(n*lg(n))

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

    I think simulation is the correct solution. It can be proved that after each step, the total no of non eliminated voters will be at least halved. That guarantees atmost log(n) steps of the simulation. Using queues the simulation can be done in linear time. So the overall complexity is O(nlogn).

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

The pretests of C are very weak

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

When you finish your code and it gets AC just after contest ... :(

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

    lol i understand that,it happened to me twice today ... mrning and night :(

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

      that is better than not getting the solution

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

Great! Two contests and I was first in my room in both! :)

Today is definitely my lucky day...

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

What the ***k is going on C on 21!!!

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

7 RDRDDRD How the ans is D for this case ? :/

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

    R at pos 1 will ban pos 2 from voting.
    R at pos 3 will ban pos 4 from voting.
    D at pos 5 will ban pos 6 from voting.
    D at pos 7 will ban pos 1 from voting.
    Now string is RDD.
    Pos 1 bans pos 2.
    Pos 3 bans pos 1.
    So D.

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

    RDRDDRD

    INITIALLY R-1,3,6 D-2,4,5,7

    POS=1 R-1,3,6 D-4,5,7

    POS=3 R-1,3,6 D-5,7

    POS=5 R-1,3 D-5,7

    POS=7 R-3 D-5,7

    POS =3 R-3 D-7

    POS =7 R- D-7

    ANS D

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

    everyone will play optimally.

    RDRDDRD ->R.RDDRD ->R.R.DRD ->R.R.D.D ->..R.D.D ->..R...D ->......D

    hope you understand.

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

find difference between this two solutions:

http://codeforces.com/contest/749/submission/23151466 http://codeforces.com/contest/749/submission/23162519

except that they are stupid

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

    jury take a long time to check your solution , jury's problem

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

Why RE36? Problem C

link

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

can someone say why in C : 7 RDRDDRD must be D ? i traced it and found it is R

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

    R at pos 1 will ban pos 2 from voting.
    R at pos 3 will ban pos 4 from voting.
    D at pos 5 will ban pos 6 from voting.
    D at pos 7 will ban pos 1 from voting.
    Now string is RDD.
    Pos 1 bans pos 2.
    Pos 3 bans pos 1.
    So D.

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

    First two R-s kill their neighbor D-s.

    It turns to RRDRD, where the third D is about to vote. Next you expell the fourth R -> RRDD, the rightmost D is voting.

    RDD -> D wins

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

    mmm, now i see, i didn't think that killing the 1st unkilled instance would make a difference

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

In problem C, many submissions fails with test case:

8 DRRDRDRD

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

Lol...the system testing was fast so I guess CF will take its time on the rating change :D

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

nice contest!

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

Wait, what?

"Became Expert" instead of "Became Candidate Master"

"Became Specialist" instead of "Became Expert"

Update: ok, it was fixed. :-)

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

My solution to problem C

keep 4 variables how many D's are left ( cntd ) , how many R's are left (cntr) , how many D's will be removed (remd) and how many R's will be removed (remr) also keep a boolean array (ban) to know if the current char is banned or not.

now iterate over the string if you found a 'D' you check first if it is banned or not , if not you check the variable remd which is incremented when an 'R' is encountered if remd was zero this means that the number of 'D's to be removed is zero, so you survive this round and also get to vote to ban an 'R' so you increment remr (so that next time you iterate on an 'R' char you ban it and decrease remr since you already banned one 'R' )

you keep repeating this while(cntd && cntr) so you will exit the while loop whenever the number of R's is zero or the number of 'D's is zero

then its easy to determine which party have won if cntd ==0 then 'R' won otherwise 'D' have won

my submission link : http://codeforces.com/contest/749/submission/23153380

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

 pitfall Plz reply, Why am I skipped?

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

    becuase you are cheater!

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

      You sure about that?

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

        possibly because in any of your submission your code matches with someone else code if it happens even in one problem only then also your contest is skipped i guess you shouldn't try to cheat next time

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

problem D today... let's do a binary search.... ohh... let's do that again... just one more time :3

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

Guys help. my compiler shows right answer but displays another answer on judge's compiler. why is that ? am i submitting my code using the wrong compiler ? my code

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

    Is there any variable that is used uninitialized? Different compiler on different machines will assign different values to those variables;

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

    You'll see the true code from pitfall. Just wait.

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

    My compiler does not even allow it to compile, because

    error C4700: uninitialized local variable 'rf' used
    error C4700: uninitialized local variable 'df' used
    
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Variable rf is not initialized, so it gets a rubbish value which can be 0. thus rf = 0 => no while loop => !rf is true => printed answer is D.

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

I can't find bug in my code. According to other contestants my algorithm is OK, but it contains bug. Can someone help me please?

LINK: http://codeforces.com/contest/749/submission/23159913

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

    Line 59:

    long long cur = check(mid);
    if(cur + 2 <= n - mid) {
        ans2 = mid;
        l = mid + 1;
    }
    

    Cur + 2 is incorrect. There can be more than one bid of same person after mid value. Check this case:

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

      I know, but (this) second binary search just needs to find the second not deleted element. It doesn't matter if it is from the same person as first binary search. And I think, that my answer to your test case is OK (my program outputs 1 3).

      UPD: Thank you very much, now I understand what is the problem.

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

Dealing with an odd issue with problem B my solve is here https://paste.ubuntu.com/23655011/ it's showing every thing ok in my IDE but showing less output in codeforce

Input 0 0 1 0 0 1

my IDE output 3 -1 1 1 -1 1 1

codeforce output 2 1 -1 1 1

remember the order doesn't metter

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

    Same, changed set to map and got TLE(yet the output was correct)

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

std::set contest :(

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

I think there are like 5-7 players from div1 with fake accs in top10 of div2. Is this legit? Why are not such people get banned?

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

    The only important thing in this site is learning. If someone's first priority is high rating update then why should we bother? We need to concern about how much we learn new things from every contest and can apply them in the future. May be banning them is a solution but its not the best solution. Cause there will always be fake ids. So just ignore them and keep focusing on learning new things. Thanks :)

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

Missed D because of not checking if the lower_bound exceed the range. Such a disappointment :(

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

Ummm...tutorial???

:)

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

Regexing in C — 23162742 (more readable version — 23154376)

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

Can one please help me As Scoring: 500-1000-1500-2000-2500 But whose rank is in be 2000 to 2200 Got negative ratings Please explain

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

    Your rating change depends on your position in the standings not on problems scores .

    If your position in the standings was better than your expected position(you can sort the registerants in the contest by rating to get an idea of your expected position in the standings before the contest starts) your rating increases otherwise it decreases .

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

Hoping some C++ expert can help me understand this issue.
Here is my submission to problem D: http://codeforces.com/contest/749/submission/23158205

Strange behaviour
1. It fails for 2nd query on #56. If I run the code on local, I observe the 2nd query is indeed answered correctly.
2. It fails on #56 when C++ 11 is chosen, but fails on #54 when C++ 14 is chosen.

My local env:

Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin16.1.0
Thread model: posix

Mac OS sierra 10.12.1

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

Can anyone provide me the test case 54 of 749C - Voting or any shorten form of it ?

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

23166401 and 23166364 are nearly the same. Yet one passes and the other fails on testcase 10! I believe that the largest difference is the use of vector reverse in the failed submission, but how would this matter?

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

    UPDATE: I found you've reverse the relationship so what I said was wrong , now I didn't see what's wrong either.

    UPDATE2: I was stupid and compared with the wrong submission number, actually you did forget to reverse the binsearch function

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

DIV 2 PROBLEM D http://codeforces.com/contest/749/submission/23409556 http://codeforces.com/contest/749/submission/23175395 The first code gives TLE on Case 10,the second one gets accepted. Can someone help me in figuring out what is wrong in Code 1 that gives the verdict as TLE though the approaches used are same ?