Odin-'s blog

Codeforces Round #478 (Div. 2)
By Odin-, 7 years ago, In English

Hello codeforces!

I'm glad to announce that codeforces round #478 for the second division will take place on Tuesday, May 1st 17:05 MSK. First division participants can also take part out of competition.

Great thanks to Nikolay Kalinin (KAN) and Fudail Hasan (fudail225) for helping me prepare the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform, Many thanks for Amr Mahmoud (RetiredAmrMahmoud ) Tameem Zabalawi (timo14z), AmirReza PoorAkhavan (Arpa), Alexey Ilyukhov (Livace), Hag Ahmad (Reckt), Nikita Bosov (FalseMirror) and Andrew Rayskiy (GreenGrape) for testing the round.

You will be given five problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!

I hope you'll enjoy my round. I wish everyone good luck and high rating!

UPD1: problem scores: 500 — 1000 — 1500 — 2000 — 2500

UPD2:

Congratulations to the winners

1- kmjp

2- TangentDay

3- Llamap.

4- E869120

5- kevinsogo

Div.2 winners:

1- Llamap.

2- amarDhcuMoS

3- phongthan

4- Nirma_Sucks

5- MagolorSoul

UPD3 : Tutorial is out!.

Tags 478
  • Vote: I like it
  • +238
  • Vote: I do not like it

Comments Comments (137)
| Write comment?
»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Yeah! 3 contests in 3 days!

[Can I go back to Purple again?]

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -42 Vote: I do not like it

is it round #473 ? thanks :D..updated :)

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

I smell math problems :\

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

I love math, but is it rated?

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

A Syrian contest :D

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

It's a good gift in my birthday "Codeforces Round".

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

Codeforces is just a gift that keeps on giving :)

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

I wish everyone high luck and good rating!

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

    It is not possible for everyone with high luck and good rating.

    Bcs someone will be a bad rating, for this reason, someone will be good rating :D :D :D

    So your statement will be definitely false.

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

When does the system test begin? :)

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

    UPD: It is system testing now!

    Maybe it will be like Round #464？

    After the round, the following sequence of events will happen: system testing of Round #464, system testing of Educational Round #38, rating updates for the Educational Round, rating updates for Round #464, in that order. Ratings for Round #464 will be updated for participants who were in div. 2 prior to the Educational Round.

    But I hope the system test of Edu Round will come before the Round.

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

      I think they decrease open hacking phase time just in order to begin system test before Round 478 :)

      ( Sorry for my poor English.

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

KAN no math test please, this isn't high school

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

There is a little mistake. In second sentence you wrote «round #473»

Upd: fixed

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

    Come on, he pointed out a valid mistake in the announcement. Stop downvoting him.

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

The scoring distribution will be published soon = u will know when the contest will start prove me wrong..

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

3*

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

Today i will get atleast(-100) in my rating.

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

    Ratings are not everything. We should give our best in every contest and keep learning :D

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

May god save me in my exam tomorrow.

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

When will the rate changes appear?? Im dieing over herew

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

with the system testing of educational round, i am back to purple. now if i attend this round whether my rating for this round will be discarded or this round rating will be updated first and then the educational round rating will be applied compared to this rating.

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

    This has happened before and the rating changes of both contests were based on the rating before edu round.
    You can actually hit orange if your rating is ~1900 and you are top 10 in both div 2 contests.

    Edit: Looks like they fixed it this time.

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

So much Love xD :D

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

No more dynamics in Competitive Programming please :(

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

this is shit

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

what a bullshit geometry contest :/

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

This is pure shit :)

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

If you mix some shit, geometry, physic and implementation it will be great contest, isn't it?

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

The comment is hidden because of too negative feedback, click here to view it

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

    Why don't you prepare a round then instead of bitching?

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

From my point of view (tester’s, not author’s) this contest is well designed and properly balanced. Yeah, I personally hate hard geometry (but there’s only one such problem here and it is E, so it isn’t supposed to be solved by many, what’s wrong then?), but I can assure you that there are things I loathe much more — haters, for example. Most of you haven’t even committed anything to codeforces — how dare you speak this way?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -55 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    People's lives should not be a part of a joke!!

    Keep your comments out of CF

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

Honestly the last two problems are really great, but its not good to see them in the same round, i just withdrawed the round when i saw the shapes...

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

    I did nothing for 3/4 of the contest because of the geometry. I think 1 problem of geometry is fine if there are other problems of which to think about.

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

      You can't just quit a problem because it has X Y input or happening in plane and say its geometry About 350 people solved it And its just some pen/paper linear equations

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

What a Round of codeforces. UPD: This Round Has very less amount of hacks :D :D :D

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

    Some people managed to get successful hack. Example: ZeroTwo

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

      Yea. But Why Hacks list is null?

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

        There have been 9 hacks in this round. Go here and select Any Problem -> Hacked on the right side and hit apply button

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

        In the hack list, you can see just your hacks. It is not like educational rounds.

        But you can do like latvian said.

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

          Oops! I am really don't know this.

          Thanks for your information.

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

Can anyone give me a hint with D? :)

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

    I guess it's hashing

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

      Can you clarify your point?

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

        Well, two points collide if (Vy2-Vy1)/(Vx2-Vx1) = a, so we need to calculate how many of points satisfy this, but there is also case when Vx2=Vx1. I am missing something probably, but idk what

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

          After that you can map every point with a*Vx-Vy and do something, but there are some collisions i guess...

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

            Nvm there is correct solution below this

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

    Btw what is Test 8

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

    For collision for two ghosts (let their indexes be i and j), we should have xi + t * VXi = xj + t * VXj and

    a * xi + b + t * VYi = a * xj + b + t * VYj

    After simplying we get

    xi - xj = t * (VXj - VXi)

    a * (xi - xj) = t * (VYj - VYi)

    and dividing second to first

    a = (VYj - VYi) / (VXj - VXi)

    So, we need to find count of indexes i and j such that slope of them equals to a. It can easily done by compression and something like two pointers or BIT.

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

      We can use only maps =) here

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

        Of course, but my teacher MR. MSHus (a.k.a. computerbox) taught me to overkill everything. He's the best teacher in the world so my account is named for the honor of him. WORLD NEEDS TEACHERS LIKE MSHus (a.k.a. computerbox).

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

          How i can be your teacher my friend ? :) Maybe are you my fan number one ?

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

            MR. HACIYEV is so shy and modest man so he considers all of his students a friend. MAKE WORLD GREAT AGAIN WITH TEACHERS LIKE MSHus (a.k.a. computerbox)!!

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

      Another condition is that VXi ≠ VXj.

      Also, . So C++ map and inclusion-exclusion is enough.

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

    Problem can be simplified by mapping the line y = ax + b to the X-axis using a shear. Now all ghosts are on the X-axis. Two ghosts can collide only if they have same Vy, so group them by Vy. If two ghosts have same Vy the problem reduces to 1-dimensional case where two ghosts always collide except if they have same Vx. And that's it.

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

      I was thinking about rotating the line to X-axis, but I didn't know enough geometry and had to go for dinner :P SAD!

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

        Using a rotation instead of a shear should also work theoretically but the floating-point error devil would probably not let you slip by :P

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

    Finally understanding the solution. Wonder why I spent my time thinking of some complex geometric scenarios.

    Thanks all of you! :D CopeCope, BFF, mochii, xuanquang1999, meooow.

    (Sorry for the late reply, I was forced to sleep like, immediately after the contest ended :-P )

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

What is the 4th test in E?

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

test 4 in D?

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

What is the idea behind D ???

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

what is pretest 3 in B

never mind...got it :(

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it
    Wrong content
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That's not a valid test case. From statement: "is either zero or odd"

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

        Oh sorry, you are right.

        I'll edit my comment.

        Thanks :)

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

    Something like 49 0 0 0 0 0 0 0 0 0 0 0 0 0.

    My mistake was to forget about setting to 0 the cell which is used for getting stones.

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

I, for one, thought this was a pretty cool contest and am happy to see someone writing geometry problems. Personally, I think that CF has the best platform of all the competitive coding sites. The main problem I have with CF, though, is that the problems tend to be very narrow in scope (segment tree, basic number theory, dp and graph problems cover like 90% of the div 2 tasks that along with the "non-algorithmic" implementation/greedy/simulation). Geometry is such a rich area of algorithms and there are so many cool algorithms that you can build problems around that I feel like we often miss out on a lot of cool problems by almost never having geometry questions. So thank you, Odin-, for writing a contest with some cool geometry problems, because, in my opinion, CF could benefit from having more of those.

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

Problem C , WA test 8

http://codeforces.me/contest/975/submission/37819859

why!! :(

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

Should all participants in competitive programming know about torque/equilibrium formula or have a bad time to figure out what happens when "one point is fixed... blahblah?"

I really want to see problems only using computer science/engineering knowledges. What's the point of giving the problem with 90% physics + 10% implementation?

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

    I agree with this. There should be a more specific description about when the object is considered 'balanced under gravity'.

    Otherwise, saying that the contest is geometry bullsh*t because of not realizing that D doesn't require geometry knowledge is just nonsense (I'm not targeting you).

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

    There are no hard physic formulas at all. All you need to solve the problem: 1. When "one point is fixed... blahblah?" center of mass moves to point directly below the fixed point. 2. The center of mass of rectangle = weighted mean of the centers of mass of triangles (0, i, i+1)

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

      For you, it may be easy physics. For me(and maybe some other contestants), it's not. In Korea, there's no class about torque in mandatory school class. Is it about computer science? No.

      That's why this problem is nonsense.

      How about chemistry? biology? "Print the year when World War II occured."? I believe this problem is same with those cases.

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

        In the solution there is no use for torque, angular velocity, Friction force ... etc because those are advanced physics topics. from the sample tests you can develop an idea how things work. I mean it is very obvious from the first sample that the polygon rotates around (2,0) and its center of mass will be right under the pivot (2,0).

        Maybe you are not familiar with center of mass of a geometrical shape. I think you just have to read about it. Its very useful and easy. Center of Mass

        I hope that now you know about these stuff and maybe in ICPC you can solve some problem that use the same physical principals.

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

          err, that's exactly the problem. People need to know about the center of mass to solve the problem. This will give an unfair advantage to people who are well verse in physics compare to those that are not. Also, people who are familiar with physic may also know shortcut to the solution(maybe using torque or something). I think the argument here is that a CP contest should not involve any physics at all.

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

            Actually you can figure it out from observing how the polygon in the sample rotate.

            Anyway, Now you know.

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

              I know it in the first place, this is about people here who are not well verse in physics.

              So you are telling me I can discover what a center of mass is just by an example? How do I know if it's a coincidence of something?

              I think you are ok with this because to you it is common knowledge. But the problem is common knowledge across the world is different. Suppose now I change the question to I have X and Y chemical, which form Z chemical(basically some chemistry stuff), and I give you their mass and equilibrium constant, and ask for their final mass(I might be wrong, I forgot my chemistry). This may be a common knowledge to me, but it might not be the case to others. And the key point of solving such problem is on the chemistry, and not idea.

              I think the least you can do is to put such information in the problem. I have nothing against it as I barely do contest anyway, just trying to express what I see people are feeling.

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

                Hmm, It is math! incenter of a triangle is well known in math. you can use it to find the centroid of a polygon.

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

    Actually it's not about torques, it's about fact that equilibrium point is the one in which potential energy is minimized and that we can use only center of masses to calculate system's potential energy. That would be enough to solve the problem and I consider it as common knowledge.

    The most hard thing is probably determining center of masses for solid body... But, at least in Russia, it is covered in many algorithm resources, like famous e-maxx.ru.

    I'm not sure that all participants should know it, but I think that problem is totally fine. As well as problems in which you have to deal with discrete analysis, number theory, general algebra, linear algebra, mathematical optimization and numerical analysis.

    If we extend your point of view, we can say that problems which need 90% combinatorics and probability theory + 10% implementation are bad. Is it so? I doubt that. So why would it be ok to make a problem based mostly on advanced maths but to make a problem based on basic physics is bad?

    P.S. If we go further, this question seems to correlate with what is participant's aim in competitive programming. If you're here just to compete and earn high results, then yeah, it would be better for you if contests had strict syllabus restrained to mostly theoretical computer science and some basic maths. But my main purpose is to study new designs, so I highly appreciate problems that involve some new and unusual ideas and concepts.

    So... To consider if some problem is ok for contest or not, we should start with defining the purpose of contest itself. For div. 2 contests I believe educational part is more important than competitive, so in this particular case it's just perfectly ok.

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

      it's about fact that equilibrium point is the one in which potential energy is minimized and that we can use only center of masses to calculate system's potential energy. That would be enough to solve the problem and I consider it as common knowledge.

      common knowledge? I guess common knowledge in different region is quite different, this is really the first time I heard of this, and I did physic until Pre-University(A-level)

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

        It's the same as "1. When "one point is fixed... blahblah?" center of mass moves to point directly below the fixed point."

        And yes, I hope It's common knowledge.

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

    Can you provide definition of "computer science/engineering knowledge"? Are math-heavy problems fine in such case? To avoid writing long comment here, I'd just say that I pretty much agree with adamant.

    On a side note, I also find both D and E being ugly. But that's a matter of taste.

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

Wow look at this solution someone wrote a case hackme for n=696

http://codeforces.me/contest/975/submission/37804303

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

Great contest, loved it. Really short solutions, I've got 60 lines in total for A-D and only 100 in E.

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

Problem B, Test case 10... It took half hour for me to pass that test. Probably it requires using long, not integer. Since a possible sum of stones like 13*10^9 can not be stored in int. Sad contest for me :(

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

In problem E, what if we have 3 points: (0, 0), (1, 1), ( - 1, 1) and fixed point is (0, 0)?

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

    this equilibrium is not stable so it should rotate.

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

I would like to report BorisYeltsin and vammadur for using unfair means. He hacked vammadur whose code was clearly written to be hacked. I am not sure if it is the same person but it seems very fishy. Have a look at his submission 37804303

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

    Seems they are not the same person, vammadur just solved A to get minus hacks, and also wrote this case to get hacked to lose more points. Congrats, BorisYeltsin, for using this opportunity :P

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

    If it is the same person, I wonder how he could arrange both his accounts to be in the same room.

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

      you just need enough accounts and enough tries.

      But for this case it's not, he seems to be doing this a few contests ago.

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

Can anyone help with me C?

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

    Your code is brute force... Please use binary search to get index till which person is killed. For c++ you can use lower_bound() as well as upper_bound() for inbuilt binary search.!

    Cheers

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

    Problem C can solve with binary-search as follows:

    • Let s be the value of how many arrows did warriors hit after last reset.
    • Let ci be a1 + a2 + a3 + ... + ai : How many arrows are needed to fall i-th warrior.
    • In p-th minute, if enemy shoot kp arrows, s will be as follows:
      • If s + kp is no less than a1 + a2 + a3 + ... + aN, all warriors fall -> reset. So s will be 0.
      • Otherwise, s will be s + kp.
    • For each query, you should know "How many warriors killed". You can binary-search by ci.

    Here is my code: Code
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did my binary search but still got TLE. Anyone else uses python for C? I assume python is too slow for this?

    37819860

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

      It is very likely because of the high amount of I/O in the problem. You can try to find some optimised IO implementation somewhere like there are for Java.

      Also, Python has inbuilt binary search (bisect module). Maybe it will offer better performance than your implementation.

      lastly, you can choose PyPy as your language — it is compatible with Python2. PyPy is compiled down to native code and is hence faster.

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

        I tried the bisect module, it indeed runs faster and my code got accepted. Haven't really explored some other IO options, will check them later I guess. PyPy runs slower for some reason, I have no idea.

        Anyway good to know, thanks!

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

Same problems, same submission times, but not the same ranking, unfortunately. :(

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

Wow ! Quick sys test (Y)

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

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

Hi, I got pretest 8 passed for problem C and my code number is 37815677. But I got a TLE on test 8 while system checking. I submitted the same code again (37820871) and its showing AC for the same code. Can someone please provide me a satisfactory response for the same.

I even compared the two codes on codeforces in the compare section and they were termed as identical. If it was some system bug, my code should be re-evaluated and given an AC.

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

)

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

Hey, guys. Can anyone tell what is wrong with my C solution? I decided with the help of the dynamics is preserved how much damage to kill of the i-th warrior and how much total damage of the arrows, until they kill everyone.

Solution: 37817808

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

    Next test give you a wrong answer: Input: 5 6 3 4 5 6 7 1 1 1 1 1 Your Answer: 5 5 4 4 4

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

I'm not sure if the rating changes is not correct.

But I'm just asking you, please, to ensure from it.

Within the contest, when my rank was a little more than 700, the "Rating Changes Predictor" told me that my rating will change by +30, and now after the end of the whole system test my rank is 609, but my rating changed by +29!

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

    I solve 3 tasks and my rating was decreased.

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

      To be honest, as I know, the change of someone's rating depend on his/her rank, not just on the number of the solved problems.

      And the rank depends on the score, which depends on the solved problems, the time he/she sends the last correct submission for a problem and the number of distinct failed submission (except the failed submissions on the first test).

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

Can someone please tell me why my solution of C gets TLE? I am doing binary search on the prefix sums.37821182

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

is it legit that 80% of div2 winners created their accounts 1-2 days ago? The last guy looks suspicious tho

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

It seems that the contests will not be too frequent then. :D

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

Maaaaaaaaaan, I am falcon now. Thank yall codeforces.

→ Reply