geranazavr555's blog

Codeforces Round #568 (Div. 2)
By geranazavr555, 6 years ago, translation, In English

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.

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

Comments Comments (217)
| Write comment?
»
6 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Another rare round with 7 problems in Div.2!

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

→ Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Lol, I can see the scar of the previous contest.

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

    try python. Some problems are easy if implemented in python. Especially problems does not constrain strictly on complexity.

    → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Wish you the best of luck for organising your first contest

→ Reply
»
6 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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.

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

Good luck and have fun everyone! :)

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

lol

→ Reply
»
6 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Div(2.5) XD

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

    It's a Div.3, but rated for blue and purple ones. Doesn't happen every day :)

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

      It seems it turned out to be a typical Div. 2 round with a greater number of problems. I hope that everyone in Div.2 will find interesting problems for him/her.

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

    → Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

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

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

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

    Yes.

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

      Thanks for your reply, but any idea on why it is mentioned "it will be rated for div2 participants" in above contest description?

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

        div_x_participants = ∑( i=x -> i=3 ) div_i_participants

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

          Wrong answer on test 1

          Input
x = 1
Output
1 + 2 + 3
Answer
1
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +62 Vote: I do not like it

            Successful hacking attempt!

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

            My fault, since I'm just a poor div2 participants, this is totally extracurricular knowledge for me QAQ

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

          So if x = 1 + 2(div1 + div2)?

          → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Codeforces Round #568 (Div. 2.5)

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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"

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

We need more problems!

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Now there are more and more subtasks in the problems.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

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

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Why was the game delayed by 10 minutes?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Delayed for 10 minutes!!

→ Reply
»
6 years ago, # |
  Vote: I like it +162 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

First time I have seen more than 10k participants.

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

for any one have trouble use

http://m2.codeforces.com/

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

OMG this was the BEST contest ever! Incredible one!

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

Daaaaamn if just 2 minutes I could've tried D

edit : Nevermind it was wrong XD

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Great round, thank you a lot!

→ Reply
»
6 years ago, # |
  Vote: I like it +235 Vote: I do not like it

You should've left it as Div 3.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    2 hours would have been enough too

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

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

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

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

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

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -9 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -12 Vote: I do not like it

            i think even tourist sometime writes code with bugs

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

              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, ¯\_(ツ)_/¯)

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

                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

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

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    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.

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

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

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

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

      → Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

What was the shit about TC21 in D?

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

    same question...

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

    I think this is a test-case where the whole array forms an arithmetic progression and either the largest element's position is not n or the smallest element's position is not 1.

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

      I don't think so.

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

        Maybe this is not your problem. But I got WA on pretest 21, and my mistake was that in case that the array already forms an arithmetic progression, I was printing n (then fixed it to print the position of the largest element before sorting).

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

          Wasted an hour on this bug, thank you for explanation :)

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

          Ohhh. Same mistake.

          Thanks.

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

          I was printing 1.

          :(

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

          I was thinking of this bug for literally an hour and forty five minutes during the contest and was not able to get it as I was not giving any test cases related to it thinking that it was obvious.

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

    Try this

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

    exactly ???

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

what is the pretest 21 of problem D :(

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Screencast with commentary

→ Reply
»
6 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

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

    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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +188 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +205 Vote: I do not like it

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.

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

    Yes, I agree. It will be fixed somehow.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

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

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

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem D is similar to this problem from cookoff: link

→ Reply
»
6 years ago, # |
  Vote: I like it +103 Vote: I do not like it

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!

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

    what if, G2 Pass, G1 Fail.

    Like jtnydv25 solutions.

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

    I agree. I think it would be more reasonable to award 2000 points for G1 and 1500 points for G2, or maybe even the other way around (1500 for G1, 2000 for G2).

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G2??

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Well, your situation has nothing to do with point distribution or anything. You just did something stupid :)

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +37 Vote: I do not like it

F tests are so weak.

1 2
1 1
5 1 1
6 1 1

Can kill many solutions.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I solved it with a treap: 55768688

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

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

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

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

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

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

          Anyway, thank you so much!

          → Reply
»
6 years ago, # |
  Vote: I like it +82 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

https://youtu.be/HDDgJPKuSf0

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1185/submission/55757491 I don't know whether I should feel amused or sorry for myself :( I need to indent my code properly.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -13 Vote: I do not like it

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

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

    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?

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

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Давайте поговорим серьезно ( я не хотел никого обидеть не надо минусить) раунд состоял из достаточно легких задач для див 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 ???

→ Reply
»
6 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Well, since you said it will not happen again, we'll reconsider.

    → Reply
»
6 years ago, # |
  Vote: I like it -20 Vote: I do not like it

C2 was more difficult than D,E,G1

→ Reply
»
6 years ago, # |
  Vote: I like it -50 Vote: I do not like it

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.

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

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -80 Vote: I do not like it

      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.

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

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -123 Vote: I do not like it

    Indians!

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

      Dude his profile say he is from Bangladesh.
      Get your facts corrected before making any assumption.

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

      Trump Supporter btw you are from Mexico strangeee....

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

      Firstly look at your self dude

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

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

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

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

    I think you can use a BIT

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

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

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

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

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

        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.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

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

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

Editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case 30 for C2?

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

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.

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

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

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

    https://mirror.codeforces.com/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://mirror.codeforces.com/contest/1185/submission/55785240

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

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

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

      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.

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

        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 ?

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

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

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

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

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

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

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

Can anyone tell me how to solve G2?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

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

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

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

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

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

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Well, to be honest, the complexity of my solution is $$$O(n^3T^2)$$$, but my solution suns in 733ms.

      55809647

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

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

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

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

    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)

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

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

      → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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://mirror.codeforces.com/contest/1185/submission/55793048]

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

During contest: https://mirror.codeforces.com/contest/1185/submission/55760801 After the contest: https://mirror.codeforces.com/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://mirror.codeforces.com/contest/1185/submission/55812449

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

    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.

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

      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.

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

        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.

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

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

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G1?

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

    Straight forward bitmask DP. dp[mask][prv] gives the number of ways to arrange a subset of the given songs where prv is the genre of the last used song. Complexity $$$O(n*2^n)$$$

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

When will the problem setters upload the editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

https://mirror.codeforces.com/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.

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

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

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

    check for:
    6 15
    1 2 3 4 10 5

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

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

    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://mirror.codeforces.com/contest/1185/submission/55817685

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

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

      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.

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

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please provide the editorials.

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

any editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Editorial coming? :)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    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

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

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

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

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

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the editorials come?

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

[deleted]

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Now editorials are available.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

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

    Yes the answer is 3. Earlier I thought that the array consists of 6 elements.

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

      How? If we delete 3rd element, it's a arithmetic sequence.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply