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

Автор pitfall, 7 лет назад, По-русски

Всем привет!

В понедельник, 19 декабря в 19:35 MSK состоится Codeforces Round #388 для участников из второго дивизиона. Участники из первого дивизиона могут принять участие вне конкурса.

Для вас раунд готовили: Денис pitfall Безруков, Алексей dalex Дергунов, Вячеслав Slamur Муравьев, Егор Petruchcho Пономарев, Павел craus Семушин и Андрей Shlakoblock Гайдель.

Для меня, Slamur и Petruchcho это первый рейтинговый раунд. Надеемся, что все пройдет хорошо и каждый участник найдет для себя интересные задачи.

Выражаем благодарность Глебу GlebsHP Евстропову за помощь в подготовке раунда и Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

UPD: Вам будет предложено 5 задач и 2 часа на их решение.
Разбалловка: 500-1000-1500-2000-2500

Наши поздравления победителям:

Div.2:

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

Div.1:

1. I_love_Tanya_Romanova
2. W4yneb0t
3. enot110
4. vintage_Vlad_Makeev
5. Um_nik

UPD: Разбор доступен по ссылке

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

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

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

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

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.

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

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

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

    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.

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

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

Time is usuall but nember of problem isnt : (

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

Контест от самарских троллей, это должно быть интересно!

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

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

Hope so we will enjoy :)

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

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

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

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

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

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

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

After many contests, the number of problems are now 5 =))) We have a usual contest, with usual time, usual number of problems, and usual duration =))

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

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

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

Perfect time for programmers from Bangladesh :)

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

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

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

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

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

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

Исправьте: "Участиники* из первого дивизиона"

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

Hope not to drop after doing well last contest.

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

my 3rd contest on CF in 30 hours!

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

Good luck everyone ! Hope everyone gets what he deserves !

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

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

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

I wish this contest will be great for all of us

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

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.

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

Can someone explain problem E's statement?

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

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

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

Bbye Blue

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

What's the C hacking case was please?

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

Hack case for C

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

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

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

Very interesting contest, thanks to pitfall

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

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

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

    I got passed pretest with simulation.

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

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

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

      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.

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

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

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

    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)

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

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

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

      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

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

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

    PD.: Sorry for my horrible English.

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

Solution to B could easily be found on google.

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

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

Link

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

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?

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

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

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

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

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

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.

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

    What should be the correct answer?

  • »
    »
    7 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    How can the answer be D?

    My answer is R, btw.

    And I use the 'wrong' algorithm.

    UDP: And I passed the system test.

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

      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.

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

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

    and it PASSED the system test.

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

How solve E?

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

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

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

    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.

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

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

They were really fun though, thanks codeforces :)

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

How to solve C without simulating it?

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

    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.

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

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

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

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 ?

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

How to solve D?

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

    i used parallel binary search but i guess its probably overkill

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

    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.

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

      Did this solution passed system tests?

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

      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?

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

        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.

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

          Then sir what is the correct approach?

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

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

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

    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.

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

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

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

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

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

    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.

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

C test case 21 anyone? :(

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

Extremely fast system testing...

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

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

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

Хороший контест, и задачки интересные

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

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?

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

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

:)

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

Мне тут рассказывали, что я не умею оценивать div.2 раунды. Дак вот, по моим неадекватным критериям это один из самых интересных div.2 раундов на CF. Спасибо. Все 5 задач были интересные и крутые.

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

Hi guys,

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

Thank you very much!

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

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

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

    I used a queue to simulate..

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

    You can use set to simulate the optimal moves.

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

    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.

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

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

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

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

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

The pretests of C are very weak

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

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

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

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

Today is definitely my lucky day...

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

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

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

    everyone will play optimally.

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

    hope you understand.

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

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

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

Why RE36? Problem C

link

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

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

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

    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.

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

    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

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

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

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

In problem C, many submissions fails with test case:

8 DRRDRDRD

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

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

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

nice contest!

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

Wait, what?

"Became Expert" instead of "Became Candidate Master"

"Became Specialist" instead of "Became Expert"

Update: ok, it was fixed. :-)

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

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

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

 pitfall Plz reply, Why am I skipped?

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

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

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

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

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

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    My compiler does not even allow it to compile, because

    error C4700: uninitialized local variable 'rf' used
    error C4700: uninitialized local variable 'df' used
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

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

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

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

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

      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.

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

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

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

std::set contest :(

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

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?

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

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

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

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

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

Ummm...tutorial???

:)

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

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

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

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

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

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

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

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?

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

    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