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

Автор geranazavr555, 5 лет назад, перевод, По-английски

Hello, Codeforces!

We are glad to invite you to take part in Codeforces Round 568 (Div. 2), which will be held on Jun/19/2019 17:45 (Moscow time). The round will consist of 7 problems (possibly, plus subproblems). It will be rated for Div. 2 participants.

We, geranazavr555 and cannor147, are students of ITMO University. And we have recently joined the developers team of Codeforces and Polygon. We have prepared this round for more careful acquaintance with the system. We hope that you will enjoy the competition.

Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such rounds. MikeMirzayanov suggested to make this to be rated for the second division.

Many thanks to MikeMirzayanov for the tremendous work on the creation and development of Codeforces and Polygon and coordinating our work. Also, special thanks to Vshining, awoo, nooinenoojno, vovuh, Lewin, Dave11ar, T-D-K and Azat_Yusupov for testing the round.

Good luck!

UPD1:

The scoring distribution will be: 500 — 1000 — (1000 + 750) — 2000 — 2250 — 2750 — (2750 + 750). The round will last 2 hours and 15 minutes.

UPD2:

Congratulations to the winners:

  1. 2om_neek

  2. m1sch3f

  3. AreEduRoundsEducational

  4. ashutosh450

  5. LOVE_BELUGAS

UPD3:

Editorials are available here.

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

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

Another rare round with 7 problems in Div.2!

I hope the contest provides great experience to both the problemsetters and the contestants.

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

Congratulations!! for organising first time.Hope it will be a good. Thank You.

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

Hope, no problems with big numbers. Good luck for everyone!

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

Wish you the best of luck for organising your first contest

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

Initially, we had prepared the round for Div. 3. This round would have been a rare Div. 3 in which vovuh's not a setter.

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

Good luck and have fun everyone! :)

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

lol

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

Div (2.5) XD

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

Div(2.5) XD

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

Congrats for your first rated round.Hopes your hard work pays off and we can get many more round in future. Good Luck!!

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

Is div2 contest rated for div3 (<1600) participants? Can someone explain the rules.

PS: i googled it, but couldn't find the answer.

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

Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such rounds

My prediction : A, B, C, D, E are easy problems with some implementation. F is of level div2 D, and G is hard.

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

hope it will not be hard code as the last div 2

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

Codeforces Round #568 (Div. 2.5)

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

Notable points on distribution

  • 750 gap in BC
  • CDE are in similar level
  • G has 3500 points

By the way, 2 hour 15 minutes for 7 problems.. Our hands will not be able to stop during contest :(

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

Back to back rounds...yeahhhh!!!...Thanks for the effort..

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

AB — Div3
CDE — Div2
FG — Div1
Overall — (1*2+2*3+3*2)/7 = 14/7 = 2
So we are having a Div2 today with +/- error of "possibly, subproblems"

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

We need more problems!

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

Ставь класс если хочешь видеть никнейм geranazavr555 в списках проблемсеттеров чаще

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

Now there are more and more subtasks in the problems.

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

Hope pretests pass=>system test pass,becomes true in this contest.

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

Can the contest be longer? That seems like a lot of problems for 135 minutes..

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

contest is going to be interesting.i hope more 10000 people will do participate.

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

Is it a wise idea to write contest on mobile and not using paper-pencil due to power-cut?

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

It can be true that the number of participators will be greater than 10000.

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

Why was the game delayed by 10 minutes?

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

Delayed for 10 minutes!!

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

Hi. Sorry, the delay is my fault. I forgot to change the contest type from ICPC to CODEFORCES. Now it is fixed.

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

First time I have seen more than 10k participants.

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

This is the biggest contest I've ever seen on Codeforces, both tasks wise and participants wise.

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

for any one have trouble use

http://m2.codeforces.com/

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

I think it is bad to give 2750 points for problem G1

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

OMG this was the BEST contest ever! Incredible one!

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

Daaaaamn if just 2 minutes I could've tried D

edit : Nevermind it was wrong XD

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

Great round, thank you a lot!

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

You should've left it as Div 3.

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

    2 hours would have been enough too

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

    at least it doesn't contain a lot of hacks like your rounds

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

      Ye, ofc it's much better to have 6 dummy problems without hacks than nice problems with hacks

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

        yes it is better, because what is the point of solving great problem and then get hacked because of silly bug ?

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

          Maybe you shouldn't write code with bugs. (:

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

            i think even tourist sometime writes code with bugs

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

              Tourist does write code with bugs sometimes, and he every gets hacked occasionally. But do you think he goes and blames the problem setter when this happens?

              (I mean maybe he does, ¯\_(ツ)_/¯)

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

                anyway this is pointless discussion, for me i hate problems with weak cases and i think getting points by easy problems is better then getting them from hacking

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

    At least they could hide that the problems were originally for a Div 3 contest, as this hinted that it would be a speed-coding contest and put pressure on contestants (or at least me).

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

How to solve D?

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

    There are three cases:

    • Remove maximum element
    • Remove minimum element
    • Remove an element that is not maximum nor minimum

    The first two is trivial. For the third one, notice that the maximum and minimum value will not change, and you can use these two value to reconstruct $$$d$$$ (which is $$$\frac{max - min}{n-2}$$$) and then find the element you need to remove.

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

      Please don't put it like this. You make me sound so stupid for not being able to solve it. (pun intended) (T_T)

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

      For 3rd case, it should have been divided by n-2 instead of n-1, since we are assuming after deleting one element, we get the AP correct. Great approach, implemented yours way, and it became so easier to write :)

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

What was the shit about TC21 in D?

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

what is the pretest 21 of problem D :(

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

That moment when you read G1 when 10 minutes remain and you realize your strategy for the contest sucked

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

So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then trying G2? This sucks.

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

That moment when you read G1 when 10 minutes remain and realize your strategy for the contest sucked.

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

    I read and coded it in less than 8 minutes and was also wondering why didn't i read all the problems before.even problem A took me more than 8 minutes :p

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

A person who solved all the problem has lesser score than some people who solved 8 problems ...well played Codeforces!

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

So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then coding G2 again? That sucks!

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

What was problem F about? Write bruteforce? Probably C requires more thinking.

Also I don't like subtasks in codeforces format. Today correct strategy was to write G1 first, and then think about G2. It is strange.

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

Problems with subtasks are completely inappropriate for codeforces contest format. For example, today to maximize score one should probably implement a stupid solution for G1 at first and then G2.

Such problems are ok on IOI format (without penalty for wrong submissions and time) but have weird drawbacks here. Also, in most cases including one of the versions in the contest is unnecessary because only one of them contains some idea and another one is well-known optimization or oppositely an obvious realization task and could be removed.

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

    Yes, I agree. It will be fixed somehow.

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

      One suggestion that would be relatively non-disruptive and easy to implement: perhaps it would make sense to set a contestant's submission time for both subtasks to the submission time for their last accepted subtask. For example, someone who solved G1 at 1:15 and G2 at 1:45 would receive a score as if they had submitted both problems at 1:45.

      One potential drawback is that if an easier subtask is worth substantially more than a harder subtask, it may be disadvantageous to submit the harder version if you solve it too late into the contest (if doing so would cost you more points by increasing your time on the easy subtask than you would earn by solving the harder subtask). So, this would mean that contest authors would need to avoid awarding too many more points for easy subtasks than for hard ones. (I don't think this would be too problematic--in this particular contest, for example, I would say it would be more fair to award 2000 points for G1 and 1500 points for G2, or maybe even the other way around, irrespective of this potential change.)

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

    Or they can be given scores according to their difficulty. It seems really unfair to give 70-80% of score to the easier part (which is mostly about to brute-force) and remaining to the harder one.

    Like, for today's G, it should be like 750 for G1 and 2750 for G2.

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

Problem D is similar to this problem from cookoff: link

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

I don't think the solution of G1 & G2 is strongly related, not even close.

G1 can be solved by simple mask DP, but G2 is completely different (although it's still DP).

The scoring distribution for prob.G is totally a joke. G1 is too easy, and G2 deserves a higher score!

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

G1 can be done in $$$O(g*2^n)$$$ or even $$$O(g*T*2^n)$$$ with an obvious solution,those who read G1 first may get massive score which is unfair to those who read ABC first ...

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

А чё это в E тесты-примеры неправильные? Они же реально неправильные? Я вообще-то из-за этого не успел сдать! upd: Уже понял, всё правильно.

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

I solved C1 using multiset, but unable to see the pattern for C2. Any hint ?

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

    since time was never greater than 100 u can use frequency array to store the occurrence of time till i and now when you want to fail someone just start with the largest time

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

How to solve G2??

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

I don't think the order of the problems is good.Because G1 can be solved by simple mask DP,and F can be solved in O(2^26).I think F and G1 are even easier than problem D and E because problem D and E have more details to notice.And the scores of F and G1 are just the jokes.

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

I submitted an incorrect solution to both G1 and G2 initially. G1 passed the pretests but G2 didn't. I fixed the solution and resubmitted only in G2. G1 now failed systests, but I am pretty sure that the solution I have already submitted for G2 should work for G1 as well.

I think problems with subtasks create unnecessary complications in such contests. Also, its really difficult to find a fair point distribution.

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

F tests are so weak.

1 2
1 1
5 1 1
6 1 1

Can kill many solutions.

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

can't check the solution. contest is over.

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

Hi, when i read problem C2 for the first time I didn't see the small limit for the times and I implemented a solution with a Treap but I got TLE, why is that? Is the limit for N too large for a treap?

Here is my code

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

    I solved it with a treap: 55768688

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

      Interesting, the way you generate the random numbers is better somehow?

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

        It shouldn't be that much better. I'm just directly using the output of an std::mt19937_64 seeded from a bunch of sources while you're using std::mt19937 and std::uniform_int_distribution. It could be that std::uniform_int_distribution is slow or that Visual C++ is faster than G++.

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

          Mmmm, I will try it with this. But i was expecting solved the problem with Treap :c

          Anyway, thank you so much!

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

Wow, another implementationforces round, so cool (no).

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

For problem D:

TLE Code

AC Code

The only difference is a line with "break" to avoid unnecessary O(n^2) operations and getting overall O(n log n). But i just want to say i was unable to notice this fail because of really weak pretests, because it was accepted during contest...

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

    I implemented an O(n^2) solution for small values of n and a different solution for larger values of n (taking the most common difference between consecutive elements after sorting). During testing, I set it to always use the O(n^2) algorithm, but because I'm an idiot, I forgot to change the code back before submitting it and it passed the pretests. Of course, I didn't notice this until system testing. I would have probably been stuck on TC 21 though even if my solution failed the pretests since my solution for large inputs had a bug.

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

My solution to A had a misplaced semicolon after an if condition and it passed all the pretests. It also passed 40 tests before WA during system testing. link https://codeforces.me/contest/1185/submission/55757491 I don't know whether I should feel amused or sorry for myself :( I need to indent my code properly.

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

    Какой же ты быдло кодер

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

    You should turn up your compiler warnings. Visual C++ outputted this when I compiled your code: warning C4390: ';': empty controlled statement found; is this the intent?

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

      Thanks, I was using Code: blocks IDE, I don't know if it has an option for that. I will try Visual C++, I have been wanting to change my IDE for some time now.

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

Great ideas and implement! That’s what I call a good contest

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

Давайте поговорим серьезно ( я не хотел никого обидеть не надо минусить) раунд состоял из достаточно легких задач для див 2, но их было много, вроде бы компенсировали, но зачем делать контест 2 часа 15 минут ???

Let's talk seriously (I didn’t want to offend anyone, we shouldn’t offend) the round consisted of enough easy tasks for div 2, but there were a lot of them, it seemed to be compensated, but why make a contest 2 hours 15 minutes ???

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

I am user Ankit211999 and my ratings for the contest #568 Div 2 had been deducted due to the coincidence of submission Ankit211999/55756528 with kotlin_hero987/55756305. Actually, I used ideone and I didn't knew that its use was prohibited. And the submission which matched was of Problem 118A which is a basic problem and I solved two more problems after that if the submissions would have matched it would be of all the three problems. It might be the case that the style of writing code of both the coders for that basic problem might be same. I worked hard for solving those problems please return my ratings for that contest. It will not happen again!

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

in problem A no folowing test: 1 1 1 1000000000 and some code passed but in this case should be received Time limit. https://codeforces.me/contest/1185/submission/55758255

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

Свободу Дмитрию _overrated_, Kekolokol, i_love_andrei, ESCHKERE Умнову!!!1!!!1

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

C2 was more difficult than D,E,G1

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

My verdict was skipped because of similarities with someone else's code but it could be coincidence because our style of writing code could be same. I worked hard for solving those problems please return my ratings for this contest. I will try hard to make sure it won't happen again.

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

    It is not a style, it is the copied code:

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

      Yes.I have noticed the thing. there is a community belongs in our university. ZahinAwosaf is my team mate. He coded in notepad.pw and mistakenly uploaded it to online. There is a notification came to my pc and whenever I checked it..I was coping my code to upload it on my codeforces ide for submission. But whenever I wanted to submit it on my github account I have copied the wrong one(ZahinAwosaf's Code). I haven't noticed the thing as the simulation is pretty much similar and switch to next one. Even I also solved this code earlier. But due to that reason, it happens. You can impose penalty for me. I request you to give his points he deserved.

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

      Wouldn't it make more sense to keep them in the contest and let their rating drop

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

    Indians!

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

is that Div.3 rated for Blues . Thank you , very amazing contest !

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

Is there a simpler solution than treap for C2 if $$$t_i \leq 100$$$ condition is not present?

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

    I used binary search on Segment Tree (works for any ti). Wouldn't say its a simple one though.

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

    I think you can use a BIT

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

    I used a treap, but another solution (in hindsight) is to coordinate-compress the items, then run a binary search on BIT for O(N log^2 N).

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

      Can you please explain your solution. It will be helpful for me. Though treap is new for me. Btw Thanks in advance xD. :)

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

        I will explain both:

        Treap

        A treap is just an implementation of a balanced binary search tree. What we will do is have a BBST that can support insertion and another special operation for this contest, call it search. This operation takes a parameter k, and determines the number of elements in the BBST that we can 'take' such that their sum is smaller than or equal to k. The implementation of this is rather simple: if the current node we are processing has a sum smaller than k, we can take the whole node. We take smallest elements first, in order to maximize number of elements taken.

        Then, we continually add elements to the BBST, and then perform a search on $$$M - v$$$, where v is the value of the element we are considering.

        Full solution

        Coord compress + Bsearch BIT

        If we coordinate compress the components, then each element in our BIT is simply either 0 or the value of the element. In the same way, we want the largest $$$i$$$ such that the sum of the first $$$i$$$ elements is less than $$$M - v$$$. To find this, we can binary search, and use the BIT to get the sum of the first $$$i$$$ elements.

        Frankly im way too lazy to code the above, and this specific problem has a better solution because of the lax constraints. If you have any more questions dont hesitate to ask.

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

Div.3 Rated for Blue and Purple ! very good contest .

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

Editorials?

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

What is test case 30 for C2?

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

I think that the contest is perfectly fine for div 2. Perhaps a small issue was a point value for G2. It may be solved by giving to that subtask 3500 pts (and not treat this as a subtask or let G have 6250 pts in total). I believe that this affected not so many div2 participants (most of the comments to make it div3 came from unofficial contestants...).

Perhaps a bigger, but unnoticed concern were weak tests for task F.

Please take into account an objective level of difficulty. Reading all the tasks, familiarity with bitmasks dp, etc. — these are all the factors of competitive programming. Given that, I think that the difficulty of the tasks compared to the "regular" div2 rounds was the following: A B B C C D E D F

Which in my opinion makes it also a decent, regular div 2 round.

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

Can anyone please explain how to solve c2? It will be helpful for me. Thanks in advance xD. :)

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

    https://codeforces.me/contest/1185/submission/55759892

    I've personally tried to do it using multiset. If you've done C1 by summing up every $$$a_i$$$ and if it crosses M , you declare an array $$$b_i$$$ that has all the elements up to (and not including) $$$a_i$$$ , you sort that array, and then you start from the biggest value to the lowest value and see how many students do you have to kick off, and you print that value. The problem with this task in C2 is time constraints. Sorting takes O(NlogN) and the $$$b$$$ array can be massive.

    The idea is to use multiset, because multiset is like a set except you can have multiple values (and $$$a$$$ can have multiple values), and a property of multiset and set (correct me if I'm wrong) is that they're always sorted, and they sort things in logN time.

    So when you insert each "student time" into the multiset, it will get automatically sorted in logN time, so when the sum exceeds M, you can just use the highest values in the multiset and find the amount of students needed to be kicked off.

    I'm not entirely sure why my code got TLE : https://codeforces.me/contest/1185/submission/55785240

    But it worked for Radewoosh: https://codeforces.me/contest/1185/submission/55759936

    Probably because he deletes something from his multiset, I'll debug it tomorrow.

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

      In the worse case, t[i] == M for all i which means every student will only pass if everyone in front of that student failed. This makes your solution O(n^2) since for every student you iterate through the entire set of previous students.

      Radewoosh's solution works in time because he observed that if the sum of the times for the students in the multiset exceeds M, we would always have to kick someone out in order for the later students to have any possibility of finishing. Therefore, we can kick out students until the total time of the students in the multiset is less than M.

      Since the total time of the students in the set is now always less than M, that time plus the time of the current student has to be less than 100 over M. Kicking out a student decreases the time by at least 1, so we only have to kick out less than 100 students in addition to the students that we've determined will always be kicked out.

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

        Thanks, I understand it now but why does he delete the second biggest (it-- makes it second biggest right?) and not the biggest in the set ?

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

          setel.end() points to the imaginary element right after the last element in the set, so decrementing it results in the largest element.

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

            it=setel.rbegin() is the same as it=setel.end() it-- ?

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

              Yes, except that setel.rbegin() is a reverse iterator which I didn't previously know can't be easily converted into a forward iterator that std::set::erase accepts. So I was wrong and the easiest way here is to decrement setel.end().

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

Can anyone tell me how to solve G2?

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

    I don't think this is the optimal solution.

    First calculate $$$H[i][j][k][sum]$$$ , this is defined as the number of subsets with $$$i$$$ songs of type $$$1$$$, $$$j$$$ of type $$$2$$$ etc and with length sum equal to $$$sum$$$.

    We can store this in a compressed 1d array of size Q1*Q2*Q3*T where Qi is the number of songs of type i.

    Once we have these numbers we just have to iterate over all values $$$H[i][j][k][T]$$$ and add $$$H[i][j][k][T]$$$ multiplied by an appropriate coefficient $$$F[i][j][k][end]$$$. which tells us given a specific subset of songs with those quantities how many suitable rearrangements exist, that finish with a song of type $$$end$$$. ( So for each $$$H[i][j][k][T]$$$ we add the product by the three $$$F[i][j][k][end]$$$ corresponding to the $$$3$$$ values of $$$end$$$.

    These coefficients can be calculated in time $$$3*n^ 3$$$ via a normal dp.

    Be careful when calculating the $$$H[i][j][k][sum]$$$, to make it faster process all songs of type 1 first, then type 2 etc and only fill the entries $$$H[i][j][k][sum]$$$ where the values of $$$i,j,k$$$ are less than the current numbers of processed songs.

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

      How do you calculate the H values while also making sure that you don't chose the same element more than once.

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

        To do this transverse over the values i,j,k in decreasing order instead of increasing order.

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

    I guess my solution is not the official solution since it requires FFT:
    First, let $$$dp(i)(j)(k)$$$ be the number of ways that has $$$i$$$ songs of genre $$$k$$$ and the total length is $$$j$$$ minutes. It can be calculated in $$$O(n^2T)$$$. Then, we enumerate how many songs we are going to put in the playlist for each genre (in the worst case it's a loop that runs 17*17*16 times), so we are left to calculate

    $$$\sum _{i+j+k=T} dp(cnt1)(i)(0)*dp(cnt2)(j)(1)*dp(cnt3)(k)(2)$$$

    , and this is a simple fft application. To sum up, the complexity is $$$O(n^3TlogT)$$$, but in fact, it's just 4624 times of fft of size 2500, and my solution runs in 4.5s.

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

    I used some sort of meet in the middle approach (after the contest).

    I computed $$$dp12[N][i][j][T]$$$ = how many ways to select $$$i$$$ songs from the first genre and $$$j$$$ songs from the second genre so the total sum of the durations is exactly $$$T$$$, using some of the items in range $$$0...N$$$. In practice, we can ignore the first dimension, so the dp will become $$$dp12[i][j][T]$$$. The time complexity will still be $$$O(N^3*T)$$$.

    We also compute $$$dp3[i][T]$$$ = how many ways to select $$$i$$$ songs from the third genre totalling $$$T$$$ seconds, in a similar way in $$$O(N^2*T)$$$.

    In the above dp's we ignore the order of the songs, so we will also compute another dp $$$perm[i][j][k]$$$ = how many ways to arrange $$$i$$$ songs from the first genre, $$$j$$$ songs from the second genre and $$$k$$$ songs from the third genre, so that there are no consecutive songs from the same genre. The time complexity for this will be $$$O(N^3)$$$.

    Now the answer to the problem will be $$$\sum_{i,j,k \le N, t \le T}dp12[i][j][t] * dp3[k][T-t] * perm[i][j][k]$$$.

    The final complexity will be $$$O(N^3*T)$$$ and the constant should be ok, since $$$i+j+k \le N$$$ will result in a $$$1/27$$$ constant. I got AC with 120 ms or something like that.

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

 When you realized that C2 had a low score after you solved it, even D had a higher score.

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

How is that possible?

The complexity of my solution to problem G2 is $$$O(T^2n^3)$$$, and there's a lot of mod, but I got an "Accepted".

Could anyone give me an answer? Or is it just because the computer runs too fast?

My solution here:

55809647

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

    I had the same idea with you :v I think it was accepted because lots of limitations you wrote. For ex, i + j + k <= n => for (i, j, k) will cost O(...) <= O(n^3 / 27) < O(n^2 * 2)

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

      Well, I recalculated my complexity, it is $$$O\left(\dfrac{T^2n^3}{108}\right)$$$ instead of $$$O(T^2n^3)$$$, about $$$7\times 10^9$$$.

      I think it was accepted because of this:

      if(f1[i][t1]==0)continue;
      ...
      if(f2[j][t2]==0)continue;
      

      And also, the complexity of "%" is only $$$O\left(\dfrac{T^2n^2}{18}\right)$$$

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

Can someone help me with my solution. 55778971 I am getting a Wrong Answer on Test 13.

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

What is wrong with the while conditon? The value of j printed after while loop is 104 in codeforces IDE.It works fine in dev. [submission:https://codeforces.me/contest/1185/submission/55793048]

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

My submission for B in Python WA-d during contest but got accepted after the contest.

During contest: https://codeforces.me/contest/1185/submission/55760801 After the contest: https://codeforces.me/contest/1185/submission/55812461

I wasted an hour trying to find a bug and ended up performing very poorly. I think it will be fair if my rating change is reconsidered.

Also, can you please look into this and let us know why this incident occurred? Compiler seems to behave non-deterministically: here's the same solution, but WA on a different test: https://codeforces.me/contest/1185/submission/55812449

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

    You can see, your answer is empty after some iterations. It seems that the thread exited so the line is empty. Maybe the thread is killed because the computation resource is depleted? That's my guess.

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

      I was also guessing that it is related to threads, but I'm not really sure how exactly that could happen. What exactly do you mean by computation resource?

      I don't want to use threads but I don't really know how to increase the recursion limit without them. The inability to change it (without using threads) is really annoying as it renders Python useless for many problems.

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

        computation resource, I mean many submissions are judged the same time, they are competing for resource. Just a guess.

        Python is just for quick solutions for easy problems. Hard problems needs faster language.

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

          This is a pretty simple problem and my solution is linear. It seems like the platform should support it.

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

How to solve G1?

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

When will the problem setters upload the editorials?

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

Great round, guys. So, will you post the solutions?

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

Can someone please help with my solution of problem C2. It's getting TLE on TC13.

https://codeforces.me/contest/1185/submission/55818757

I have used a multiset and every element is inserted and deleted from the multiset only once.

So the time complexity should be O(nlog(n))

any help would be appreciated.

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

    For multisets, erase eliminates all the elements with value == parameter, instead of just one element which is what I guess you were trying to do. You should change erase(largest) to erase(s.begin()).

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

Can anyone help me find fault in the concept of my implementation for C2? link

I used the priority queue to get the maximum element which hasn't been extracted yet by previous elements. I am storing the sum of time taken by the just previous element. If prev_sum + input[i] <= m, the answer will remain the same as the previous element. Otherwise, I will extract elements from the priority queue and subtract it from my current sum till it becomes less than or equal to m and update the prev_sum to curr_sum.

Please ignore the commented out code. Thanks!

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

    check for:
    6 15
    1 2 3 4 10 5

    for 6th student answer is 1 (remove 5th student).

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

    your logic is OK , but here that array is not always sorted. So , it is possible that answer to ith term can be less than (i-1)th term. example:- 4 10 3 4 10 2

    See my soln i also used priority_queue. https://codeforces.me/contest/1185/submission/55817685

    i used two priority queues second one in ascending order. I think it will even work for ti<=10^5

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

      Thanks for identifying the mistake in my implementation. I scrolled through your code and got some idea. You should check out the implementation through multiset too. It is quite simple to follow.

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

      Your Code gives wrong answer for test case: 3 100 50 60 41 Your code gives 0 1 2 But it should be 0 1 1. Still your solution got accepted. Weak test cases maybe.

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

I think the score problem is totally wrong. C2&G2 should have more score.

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

Please provide the editorials.

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

Really good problems.Isn't it? Hope there will be more rounds like this(easy&many problems).

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

any editorials?

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

Editorial coming? :)

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

Could anybody show me a solution for E?Thanks in advance

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

For problem E can anyone expalin me these two test cases test case 1 —

3 5

..b..

aaaaa

..b..

why their output is (NO) and

test case 2-

bc

cc

thankyou.

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

    First case :

    in the question it is written clearly that first 'a' is written then 'b' which means that 'b' can overwrite 'a' but not vice versa. Hence answer is NO

    Second:

    ans is NO because snake('c') cannot bend

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

      But the second test case output is

      YES

      3

      1 1 1 2

      1 1 1 2

      2 1 2 2

      ... I realy didnt get this one suppose (A) overwrite (B) and then (B) overwrite (A) but then why we overwrite (C) with itself when (C) was there on that position???

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

        'a' cannot overwrite 'b'

        In question snakes are in order that first 'a' is written then 'b' then 'c', which implies a character can only be overwritten by a character after it. i.e 'e' can be over written by any character from 'f' to 'z' and cannot be overwritten by character 'a' to 'd'. Also there is only one snake of a character, so it cannot possibly overwrite itself as it cannot bend .

        But the second test case output is

        YES.....

        i guess you wanted to paste the sample test case

        b c

        b c ( which has the the above solution of 'YES') but you pasted

        b c

        c c

        (whose solution is 'NO')

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

when will the editorials come?

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

[deleted]

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

Now editorials are available.

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

I think the solution which Radewoosh wrote for problem D is incorrect. It is showing -1 for this case: 5 2 4 5 6 8 The answer should be 3. :/

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

System tests for task D are so weak...

This submission is AC: 55860779

But it couldn't pass a few different tests:

1)

4

3 5 5 7

2)

5

2 3 4 6 8

3)

5

2 5 8 10 13