AIM Tech Round 5 (rated, Div. 1 + Div. 2)
By zeliboba, 6 years ago, In English

Hi, Codeforces!

AIM Tech Codeforces Round 5 will take place on Aug/27/2018 19:35 (Moscow time).

The round is prepared by AIM Tech employees: Kostroma, riadwaw, Edvard, yarrr, zemen, Errichto, malcolm, gchebanov, VadymKa and zeliboba.

Round will take place during Petrozavodsk Summer Camp, which is sponsored by our company.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces and problem coordinator Nikolay Kalinin (KAN). Many thanks to Golovanov399, Arterm, winger for round testing!

Our company specialises in proprietary trading, the key concepts in our work are big data, low latency and high frequency. Our team mainly consists of graduates from the Moscow State University (MSU) and Moscow Institute of Physics and Technology (MIPT). You could read more on our website aimtech.com.

Participants of combined round will be given 8 problems and 2:15 to solve them.

Last three problems have almost the same difficulty, so we advise read all of them.

Prizes from round 502 in memory of Leopoldo Taravilse will be distributed in this round.

Top-25 will get 100$ each, following 46 will get 50$ each.

Scoring 500-750-1250-2000-2500-3250-3250-3500

We wish you good luck and high frequency rating!

Thank you for participation, congratulations to the winners!

  1. LHiC
  2. jqdai0815
  3. bmerry
  4. Um_nik
  5. Egor
  6. Benq
  7. tqyaaaaang
  8. DearMargaret
  9. Marcin_smu
  10. Swistakk

Editorial

Short editorial by bmerry

Information about prizes and analysis will be published later.

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

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

Last year AIM Tech round 4 was my first ever round on CF

I didn't do too well then D:

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

    hi neko_nyaa

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

    could you please tell us what you do to improve your skills in competitive programming and get this level (rating) in only one year ? please don't just say practice . tell us what kind and type and of practice

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

      you need a lot of luck

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

        Luck?

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

        It's not about luck. It's about hard work.

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

          when going from 1400 to 2000 it is about luck and some work. hard work begins from 2000

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

      4 years of green ..

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

        that's because you did't learn anything while solving contests and reading editorials.

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

          Wow that's unnecessarily harsh.

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

            1) harsh but true 2) you also don't have any progress

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

              3) You're an asshole.

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

      Solving a lot of problems that you can't solve initially, of course.

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

        i doesn't help. if you don't know how to solve a problem, there is no profit. if you know how to solve a problem, there is still no profit. maybe there are some problems that can help you, but they are not frequent, maybe 1 or 2 of 100

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

      try solving 100+ questions on spoj in users sort mode.. I bet u would definitely gain something. best of luck!

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

    Heck, how far have you been for a year. I'm pretty much jealous if you ask. :D

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

    I think got some trouble in recent rounds. With many small mistakes and feel very tired then coding. Maybe I should rest for a while? Or are there any way to improve skills to prevent such small mistakes?

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

    I hope I can promote fastly like you,you are brilliant！

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

And we people thought only vovuh used the copy pasted part... knock..knock

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

This round is special for me as last AIM Tech Round was the highest rating change for me ever!

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

    Wow! Didn't expect that! Very very interesting! Perhaps you could tell us a bit more about that? I'm sure everyone's eager to know!

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

      You know how when you get rating increase on CF it asks you if you want to share it? They should make it so there's an option to auto-generate a blog post about your huge gains

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

        I never meant to boast about it (Its not even worth boasting anyways). Just felt good to share it.

        Agreed that it doesnt make much sense.

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

Just curious, why prizes for Top-71? (i.e. why 71 people?)

I meant, if all winners got , so the winner count would be 48 people — ain't that number be nicer? :D

(Or at least my perspective in pretty numbers has been weird all the time :D )

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

    LOL

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

      Oh, you got upvotes for the lol and he got downvotes for what makes you lol .. weired community T_T

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

        That's why I rethink 10 times before commenting anything on Codeforces.

        P.S.: I didn't think twice before commenting this.

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

          Thinking implies there actually is logic.

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

        Welcome to the club :D

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

        LOL

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

        Well I expected my downvote storm :D

        Still, don't even think that made one of the setters LOL :D Like, my jokes have been ill all the time :D

        UPD: Got upvoted a lot, while the upvote counts of most other comments have barely increased. Okay what logic is behind this... :D

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

        it is coming back up now, i guess someone had to say it :p

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

    Perhaps they noticed majk's comment. It got quite a bit of upvotes.

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

    Initially we wanted to award $100 to the top 25 and $50 to the following 50, but the contributions in the campaign weren't enough so we made it the following 46.

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

      "We"? Weren't you in the same room as mine, as a participant? :D

      (I'm just curious :D )

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

        By "We" I mean me and Leo's friends, not the contest organizers. I have nothing to do with organizing the contest itself, and didn't know any info more than what everyone else knew before the contest.

        Anyway, I was sure that I have no chance being in the top 71. :)

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

          Well, still good to know then. ;)

          Tried to hack your solutions twice, and both failed miserably. Shame on me. :D

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

=A=

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

    I want to become expert this year as well :)

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

    What is good in not being hacked?) It's better to be hacked with a chance to resolve then to fail the system testing

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

      it is better to solve task without mistakes so no one can hack you

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

        Sure, I just claimed that hacks are not what we should be afraid of: incorrect solutions are.

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

      Unless it is a hash collision hack

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

it is too late in China this round. half past midnight makes me give up this round.

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

Interesting terms of agreement this round... XD

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

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

@MikeMirzayanov since rated and $, i have to ask about server stability issues?

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

I hope this round won't be like that 1vldm8

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

How will the prizes be distributed? Is it bitcoin like round 502?

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

Its my first aim round. Apparently there will be a lot of hacking. Good luck)

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

a short note :

unfortunately because of u.e.e (university entrance exam) in Iran i can't participate in contests for almost 10 months !

It's very upsetting and i'm very sad because of it Right now !

i hope that i'll participate in the first contest after u.e.e. in july 2019 !

btw i'll prepare a round when i'm back :)

bye bye codeforces, until july !

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

    memesacredgames.

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

    Does the exam last 10 months?

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

      Many countries has very harsh university entrance exams as the most important or even the only criterion for entering good universities. High school students must intensively review and practice for a long period to prepare for it. For example, that is also the case in China, Japan and Korea.

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

        you forgot india

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

          Just list some countries I know. There are definitely many more. I don't know how it goes in India.

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

    Good luck!

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

Really Interesting problemset

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

Why the strange and unusual bounds?

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

    We tried hide reason why restriction in G is unusual

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

Note to self for next year's AIM Tech Round: do not go into hacking :D

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

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

Problem C

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

    No.

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

      Yes.

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

      Exactly this one, only in 2D.

      I'm wondering whether round coordinators were different for these 2 rounds otherwise it's hard to explain why they didn't notice 99% match of these problems.

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

    lol, I was wondering why it was taking me so long to solve

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

    xd indeed

    the drawback from different coordinators

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

    Hi, so to me seems like a notorious coincidence.

    To be serious, it's a pity nobody from authors' team is regularly solving Div. 3 contests. Probably next time we would check several previous contests to avoid such inconvenient situations. Sorry for that.

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

    I went with that method as well. Unfortunately, problem C wasn't enough. There was/is some point important to note, without which it will throw WA as it did with my case.

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

what the hell is test 8 on problem C >_< ?!

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

How do you solve C? I used amortized search for n log n but it seems highly suspicious

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

    What's wrong with just doing it in n log n? It's simple and works.

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

      well, it uses randoms, therefore I am suspicious

      UPDATE: it passed

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

        Oh, my n log n doesn't use randoms, It just splits the intervals like a segment tree (the code is pretty self-explanatory): 42165548.

        How do you get a randomized solution to this problem? :Dd

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

          idk but apparently it's blazing fast:

          https://mirror.codeforces.com/contest/1028/submission/42169784

          155ms pretests

          Only thing I'm worried about is correctness

          Basically I aim to find two disjoint rectangles because we know that the points in one of them will have the answer. To do this I just search until I reach a disjoint area in the sequence, then I know that the pair must be in the first X rectangles, where the X rectangle given causes them to be disjoint. Then I randomize and continue searching. Hopefully most of the time each random ends up discarding a lot of rectangles.

          Then I just exclude one of these rectangles at a time and get the answer

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

            I think that's randomized O(n) right? There's a 25% chance that both end up in the first half of the prefix, so even if you only halved the prefix when both were in the first half, you'd get:

            S(n) = n + 3/4 * S(n) + 1/4 * S(n/2)

            Which means:

            S(n) = 4n + S(n/2)

            Which is O(n). (shuffling a prefix takes linear time to its length).

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

              Thank you for your insight! I'm not good with complexity so I'm going to have to do more reading lol

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

    O(n) solution: precalculate intersections of all prefixes/suffixes of rectangles. If the intersection doesn't actually exist, then you have a rectangle with a low x/y higher than its high x/y, which you can easily check for. You can then brute force all possible n-1 rectangle combinations.

    42180099

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

    I don't know why you're using nlogn or randomization. Isn't it enough to just find intersection of first i rect and last n-i-1 rect and see if it's not empty

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

In problem D, how to deal with ADD orders after the last ACCEPT?

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

    It's just 'count of them + 1', because all the numbers are different.

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

    if they're in between the clamps (confirmed buy/sell offers), multiply by the number of adds + 1

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

    Thanks all.

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

How to solve problem D?Can someone explain?

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

    Observe that if there are no "ACCEPTS" then answer is simply #("ADD") + 1 since you can partition the prices at any point. Also note that "ACCEPT" only restricts the segment where you can partition. This should be easy to implement. Take care of cases where once you "ACCEPT" your value you know that minimum and maximum of your restricted segment is in which direction.

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

What is pretest 17 in G? I get TLE in the test, even though my code precalculates everything, so the runtime should be the same for every test. 42181918

Locally everything takes like 0.05 seconds so I'm rather baffled.

EDIT: The pretest is just the value M. I had a indexing mistake that caused the code to ask more than 5 queries sometimes. Fixing it gives AC: 42189394

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

How to solve E?

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

    Find any point where val[i] < val[i+1]. Set ans[i+1] = val[i+1]. Then, for j = i, i-1, ..., i+2, set ans[j] = ans[j+1] + val[j]. Then, in order to ensure the value is large enough, if ans[j] < 1e9, set ans[j] = ans[j] + 1e9 * ans[j+1].

    It's easy to verify that this works. 42175007

    Special cases are val[i] = val[j] != 0 for all i && j, in which case you answer NO, and val[i] = 0 for all i, in which case you just print a bunch of 1's.

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

    If all elements of b equal, then there are two cases: b0 = 0 and b0 ≠ 0. b0 = 0 is trivial. For b0 ≠ 0, it can be proved that answer does not exist.

    Otherwise, find any position k in b such that bk > bk - 1. Assign ak = bk. Then, construct the array a backward from k - 1 to k + 1. For position i, we need to find ai such that:

    • ai = x * ai + 1 + bi with x can be any non-negative integer.

    • ai > bi - 1.

    Since ak + 1 > bk, it followed that .

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

      I wonder why should we find the position that $b_k>b_{k-1}$？Could you please explain it?Thanks a lot!

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

        We choose such a position so that we can assign ak = bk and having the condition ak > bk - 1 satisfied.

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

In B.I submitted a wrong code got WA in pretest 1.When I checked the Correct Answer.It was like this. 55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555....

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444...

Then got AC.I think it is not right to give correct logic corresponding answers

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

    Maybe, for the constructive problems, the admins should implement the system specifically for those to show the checker logs only (Yup, that means the checker should only answer if the outputted answer suits the criteria and not give any clues to the model solution).

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

      Or to show the examples as usual...so you don't need to check answer...as usual

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

        I quite doubt that idea to be possible, as the output in the sample is force-shown by a feature in Polygon, and I don't think it'd synchronize well with the judging protocol.

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

    I think we should stop showing answers for pretests during the contest, just show your output and checker log.

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

    Yeah we've also noticed this during the contest and for new submissions only the answer same as in the statements (with no hints) is shown. I think it is sometimes useful to show correct answer and checker comment, we just forgot to check that in the system it shows the same answer as in the statements.

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

How to solve C?

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

    read maximal intersection 506div.3

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

    We need to find any point which lies in n-1 rectangles out of the given n rectangles. There can now be n cases. The first case will be considering all rectangles except 1, second case will be all rectangles except 2 and so on until index n. We can now create two arrays. First array will store the intersection area start and end of all the rectangles before an index. Second array will store the intersection area start and end of all the rectangles after that index. This can be done by: arr1[1]={start[1],end[1]}; for i=2:n arr1[i]=intersection(arr1[i-1], start[i], end[i]); /// Intersection returns both start and end area // of intersection region. arr2[i]={start[n], end[n]}; for i=n-1:1 arr2[i]=intersection(arr2[i+1], start[i], end[i]);

    We can now for all rectangles check whether rectangles on left and right intersect or not.

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

    http://mirror.codeforces.com/blog/entry/61450?#comment-454356

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

Statement of problem D was so annoying -_-

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

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

I noticed that it's possible to see output of the author's solution and verdict of the checker for tests from the statement during previous rounds and at the time I already thought that it's pretty strange.

In the round today it actually gives an obvious clue of the solution. The algorithm might be — send a solution with hardcoded answers to the tests from the statement, look at the output of the author's solution, get the idea and implement a similar solution yourself.

What do you think about this? Seems like Test Protocol should be hidden in order not to give such a clue to contestants.

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

    I think it should hide jury's answer and showing contestant's output only.

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

      I think even this is unnecessary. You can see the output for a given sample by running your solution on this sample on your machine.

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

        Sometimes, the output on local machine is different from the output on Codeforces judge (because of different compiling environment or buggy code lead to undefined behavior).

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

          Then you can see it in the "Custom Invocation" tab :)

          But KAN already answered above that "I think it is sometimes useful to show correct answer and checker comment" so it seems like admins have the same opinion as yours.

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

    See my answer here. It was just a bug that an answer different from one in the statements is shown.

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

quickforces

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

That moment when the last problem was made just for you.

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

In problem C, for pretest 4, it showed correct output on my IDE and on some online IDEs also. But I got WA on that pretest. Can anyone please let me know what error did I do?

Code : http://mirror.codeforces.com/contest/1028/submission/42181202

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

    1) check your computer's power 2) try restarting

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

      But online IDEs also give correct output -_- You can run it on your device to check it -_-

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

    Looks like in some compilers (like ideone) sort doesn't work correctly in your case for some reason...

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

    Sorry, of course sort always work correctly...

    Maybe I've found the problem. It's with idx: it's "-1" on Codeforces and "4" on ideone before the last erase. I believe this happens because in the second for(i = 1; i < n; i++) you take both p2[i-1].first and p2[i+1].first.

    Then p2[n].first and undefined behaviour. Ideone say !f(...p1[n].first, p2[n].first, ...) is true and Codeforces say it's false.

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

looks like the 'guy' 000000 cheated again. If it was a normal round, then i wouldn't care, but this round has prizes for top contestants, and this account is on top!

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

Codeforces Show the answer of problem A During the contest !

When you get a wrong answer, The jury answer is the Write answer and it's different from the answer included in the problem statement...

when i got pretest passed, The jury's answer became the same as the problem statement !

ops !

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

H can be solved in O((27 + log(N)) * 7 * N + Q * log(N)), where 7 is just the max number of distinct prime factors of a number in the given range, right? 7 seconds seems like a huge time limit for that.

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

    You can do preprocessing in O(n·7·27) and then answer queries in O(7).

    The preprocessing should give you all the information about answers for all intervals. So, for every left end L of an interval, and every possible answer a (0 ≤ a ≤ 14), find minimum possible R such that [L, R] has answer a. Then you don't need trees or binary searches.

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

      Yeah, this is way better than what In had in mind. I was thinking about iterating over L in reverse and updating answer for <= 14 suffixes using lazy propagation, which is really silly.

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

To my surprise, this solution for B passed system test!

How weak test data!

solution

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

    How is it weak? Maximum is 1129, and your least sum is 1200

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

      My solution for B was very complicated. Probably this is the distance from masters and me.

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

    It is right!

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

    The test data is not weak. It's just your solution that is correct :-)

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

    I don't think it's strange.

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

    the problem itself is weak, not the test data

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

    Wow never expected my solution to be posted by others for whatever reason

    It is my honor

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

How to solve E? Is there any theory to it?

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

    It's more of a joke rather than an actual problem xD. Basic idea is if 0 ≤ a < b, so with a little bit of care we can make work something like ai = ai + 1 + bi for most values of i.

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

      Why do you think that it's a bad problem? Isn't the solution required clever observation?

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

        I do not necessarily claim it is a bad problem. What I tried to say is that once somebody starts dealing with this problem, based on general impression and its points value, he thinks it should be some complicated number theory, but it turns out it is just naive construction based on simple trick. I definitely felt trolled hard when I came up with the actual solution.

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

    If they're all equal, then it's impossible (unless they are all 0, in which case a constant sequence works).

    Otherwise, find some i where b[i]>b[i-1]. Set a[i]=b[i], and then work backwards — set a[j]=b[j]+ka[j+1], for the smallest k that makes this expression bigger than b[j-1]. Make sure you're careful with the wraparound, and that's all.

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

      What is the thought process to reach this solution? I find that there are some problems where the solution seems so simple but before I see it I feel stuck in a fog.

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

        One idea that might be helpful to get this solution (it was for us): if not all the numbers were equal initially, then at least one of them didn't change (e.g minimal number)

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

      If we start from the maximum value, we can set k=2 first time and k=1 everywhere else

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

        What do you mean here? Can you please elaborate?

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

          I mean the solution from the editorial.

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

      Thx!

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

So I have to ask: are all strange input numbers just an elaborate setup for M bounds in problem G?

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

How to solve F?

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

    Let O be the origin. For each query A(x,y) we want to calculate a) number of points which lie on line OA and b) number of pair of points which are symmetrical with respect to OA. The first one is easy. To calculate the second, two points B and C are symmetrical to OA iff OB = OC and AB = AC. If the first condition is already satisfied, let D be the (unique) point such that OBDC is a rhombus, then AB = AC iff O, A, D is collinear.

    After that we only care about pairs of points that have the same distance to O. For each pair, we add the corresponding D, then for each query A we want to know the number of points D which lie on OA (which is easy). The whole problem can solved just by bruting those points, as the number of integer solutions for x*x + y*y = r is not that large (based on some results which I didn't remember).

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

      Some useful link:

      In summary, if the prime factorization of r is with and , then the number of positive integer point with distance to the origin is .

      I don't know what is the worst case with the given constraint (r ≤ 2 * 1129042 ≈ 2.6 * 1010, but as you said, it won't be large.

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

        I think this becomes clearer if you think about it in terms of Gaussian integers rather than Pythagorean triples. If you use that is a UFD, has a multiplicative norm N(x + iy) = x2 + y2, and the classification of Gaussian primes, you should find that the number of arbitrary integer solutions to x2 + y2 = r (r ≠ 0) is either 0 or , where bi are the exponents in r of primes of form 4k + 1. (Here 4 is the number of units, i.e. 1, i,  - 1,  - i, and bi + 1 comes from the fact that there are two Gaussian primes with norm pi, and you need their exponents in x + iy to add up to bi, so there are bi + 1 choices.)

        The formula with the sum seems weird to me, since it doesn't always give integer values, and even for r = 5 it gives 1 instead of 2.

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

Does anyone know what D's fourth sets of data are?

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

Anybody knows what the 14th test in A can be? It seems tat a lot of sources failed there...

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

Can someone explain to me why this submission fits TL in 982ms but this submission don't (>2000ms)
They look same for me.
And with same compilers.

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

    maybe slow io speed

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

    Maybe one of: optimization pragmas, fast reading, fluctuation, cool 9-wheel fidget spinner drawn as a comment.

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

    I ran dkirienko's solution 4 times and here're the results:

    42183675 — GNU C++14, without IO speed-up: 1715 ms;

    42183758 — GNU C++17, without IO speed-up: 1731 ms;

    42183820 — GNU C++14, with IO speed-up: 920 ms;

    42183861 — GNU C++17, with IO speed-up: 950 ms.

    By IO speed-up I mean these 2 lines:

    ios::sync_with_stdio(false);
cin.tie(nullptr);

    Takeaways:

    1. Always write these 2 lines when using std::cin.

    2. GNU C++14 is faster than GNU C++17.

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

      The amount of slow down for the same code seems to be very small, 16 msec and 30 msec for without and with IO speed up, respectively. However, if a new C++17 feature is used, then the performance comparison is simply unfeasible.

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

        The slowdown of 16ms and 30ms is for GNU C++14 vs. GNU C++17.

        The difference between solutions with and without IO speed-up is almost 2X.

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

          Yes, that's right. But, I am not sure if this 2X slow down factor will be the same for another code or not, even though the absolute maximum difference did not exceed 30msec.

          On the other hand, some of the GNU C++17 new language features that were mentioned in that blog few months ago may be worth using in competitive programming, provided that the slow down is tolerable if it exists persistently.

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

My solution for D, is giving TLE on pretest 4

It seems to me that it is QlogQ. Can anyone check? I've inserted/erased each element O(1) times in a set

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

On problem C, after implementing rocket science for an hour, realised that solution is just one those four points: let x1, x2, and y1, y2 be the maximum two values of left x-coordinates and bottom y-coordinates of rectangles. Just checking these four combinations suffice.

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

    sad reacts only :(

    Codeforces should provide facility to react on comments

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

Wait a minute, for problem D:

"At every moment of time, every SELL offer has higher price than every BUY offer."

Does that count for BUY and SELL offer that is accepted (removed from the order book)?

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

sadly, I find that 2014CAIS01 's solution to problem C 42167254 and D 42181490 is very similar to applese 's solution. C: 42162949 D: 42177578 . only template changes. C and D in this round is not easy to be such same. Please check it. @ zeliboba

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

last prize wowoowoooowow

i don't know if i do it intentionally or not :p

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

    At least I haven't taken 72 place. (my place is 73) :(

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

      Look at some sexy numbers ;p

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

        Err calm down Satan, you're too much involved with the mortal realm :D

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

        flibia is also 6 letter word...hmmmmmmmmmmm...........

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

      But now I see you are 72 place exactly :p, and muratt is not the last prize.

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

In prob D, what is answer for this test:

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

I'm really surprised my C solution passed 42175706

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

Hey guys, looks like the C checker mistakenly rejected my solution (42172602) with a weird error:

The answer 6053 7212 seems to be correct, see 42163884 for example.

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

Regarding Problem C, I searched the net for answer for the problem, "Intersection of N axis aligned rectangles", and all I found was stuff on BSTs and KD Trees. But it was easily done using 4 multisets, 2 for lower x vertices and lower y vertices, sorted in descending order, and 2 for higher x and y vertices, sorted in ascending order. After making all multisets, the intersection can simply be given by top element of all multisets. Is this implementation different than the ones using KD tree structure, or the same as multisets are also basically Red Black trees?

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

    Intersections of rectangles with coordinates((x1,y1),(x2,y2)) is rectangle ((max(x1),min(x2)),(max(y1), min(y2))). So you just need to calculate prefix and suffix mimimums/maximums for this problem.

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

      I was wondering if maximum intersection area of n-1 rectangles from given n rectangles could also be done by the same method. I think it would be max area after removing any of the rectangle which have a max(x1) or a max(y1) or a min(x2) or a min(y2), right?

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

        You just need to calculate prefix and suffix mimimums/maximums for this problem and you can easily try to remove every rectangle. Because we can compute the intersection of first x and last n-x-1 rectangles.

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

I got TLE in C by using cin/cout instead of scanf/printf :ccc

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

    ios::sync_with_stdio(false); is your friend.

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

    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    add these code and don't use scanf/printf/getchar/putchar/puts, if you want to use cin/cout and also want them as fast as possible.

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

any suggestion on how to improve coding skills please??

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

    Upsolve previous codeforces contests, not kidding, thats how I improved my coding skills. The first three questions of any Div 2 contest must be done, either by self, or by learning from the editorial after you've given up. The first three problems for a number of previous cf contests, and your skills will improve greatly.

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

      and how did you cope up with the new algo learnt??

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

      its too tough to implement on harder problems

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

        I know some problems can be hard to implement even after studying the editorial or the solution code. But the first three problems of Div 2 contest are doable. And the community is here to help you out if you dont understand. And regarding coping up with the new algo learnt, that just comes after practice. You dont need to cram the new concept, just try implementing it yourself after studying the algo, and look for problems on similar concept, and thats it, now that concept is engrained in your brain. For instance those who had solved Problem C of #506 were easily able to solve today's problem C. So you would automatically realize problems with similar algo if you had solved a similar problem before. So keep practicing and Best of luck :)

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

    Personal experience: I did like, hardcore coding all the time, killing off every problem I could from the Codeforces problemset (even the easiest ones).

    Of course, just solving problem is not enough — still it helps a lot in making your typing speed and typing instincts increase, and also make yourself familiar with some methods, styles, and also avoid some kind of bugs you might frequently jump into before.

    Along with solving problems, I read other books as well. For international's sake, I'll recommend two competitive programming books only: one from NUS' Halim, and one from CSES (Finland)'s Antti Laaksonen. I do read a lot from a local algorithm wiki as well (it is quite helpful for me, yet it's in Vietnamese only, so I can't recommend that one :D ).

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

Congratulations to all the winners! As mentioned in the post, each of the top 25 contestants will receive $100, and the following 46 contestants will receive $50. The prizes will be delivered using Amazon gift cards or Bitcoin. I'll contact each of the top 71 contestants through Codeforces to coordinate the prizes delivery.

The prizes in this round are in memory of Leopoldo Taravilse (ltaravilse).

http://mirror.codeforces.com/blog/entry/60157

https://www.gofundme.com/in-memory-of-leopoldo-taravilse

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

wow i have 211 rating now

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

I have a small piece of advice to those using set/multiset in C++.

When looking at submissions to the problem C today and in previous div. 3 round I noticed that the following pattern happens quite often:

auto it = my_set.end();
it--;
auto max_elem = *it;

Instead of writing this code, you can use a reverse iterator. In short, there's an iterator which points to the last element of the set (i.e. the biggest one):

auto max_elem = *my_set.rbegin();
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Nice, didn't know that. But I can share another tip — prev and next functions. We can access last element through

    int last_elem = *(prev(my_set.end()))

    but usages of these functions extend of course to more than this. I used them in D, where I needed to take previous and next element in set.

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

    Of course, not if it needs to be compared with a forward iterator. Then you can still shorten the notation to *(--end(my_set)).

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

Can someone explain the solution of Problem G?

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

    Let f(q, l) be the largest value h such that if you know the answer is in [l, h) then it can be guessed within q queries. If q=0 then h=l. Otherwise, we can use k=min(l, 10000) in the first guess a_1, a_2, ..., a_k. We need a_1 <= f(q-1, l), then a_2 <= f(q-1, a_1 + 1) and so on. To get h as high as possible, we should of course make these equalities. Finally, h = f(q-1, a_k + 1). Some optimisations are needed to allow f(5, 1) to be evaluated quickly (hint: if l >= 10000 then it is just 10001-ary search, and q = 1 has a simple closed form), but you end up with f(5, 1) being exactly M+1.

    You can use basically the same procedure as above to actually construct each guess.

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

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

Just out of curiosity, why were all the constraints on this contests not round numbers ? :)

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

When the Editorial will be published?

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

Can someone provide an editorial?

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

    Here's my short version:

    A: Run through rows from the top until you find one with at least one 'B'. Do the same for the bottom. Average the two row numbers to get the middle row. Now find the last and last 'B' in that row, average them to the get the middle column.

    B: There are lots of constructions that will work. I used a=999...999, b=999...999000...001 so that a+b is a power of 10.

    C: I had an overly complicated solution, but as many others have pointed out, all you need to is incrementally compute the intersection of the first i rectangles (for every i) and the last i rectangles (for every i), and then you can combine a prefix and suffix to get the intersection of all but the ith rectangle for any i. As soon as you find such an intersection that isn't empty, output a corner of it.

    D: Keep track of a lower bound for the best sell and an upper bound for the best buy. If an ACCEPT is for more than the best sell or less than the best buy, it's a contradiction. If it's for a value between the bounds, multiply by 2 because it could be either. After an ACCEPT, the price above it is the new best sell and the price below it the new best buy. If you get to the end and there are G prices which could be buy or sell, multiply by G+1.

    E: This one has been discussed quite a lot in previous comments so I'll skip it.

    F: The trick is to notice that two points can only be mirror images if they have the same distance from the origin, and for any given distance there aren't very many points at that distance. So we keep the points bucketed by distance. Also keep track for each possible line (identified by the ratio x:y in lowest form) of how many points don't need to be duplicated. That's going to be 1 for each point on the line, and 2 for each pair of points symmetric about the line. Adding or removing a point takes time proportional to the size of the bucket.

    G: See http://mirror.codeforces.com/blog/entry/61450?#comment-454479

    H: Firstly, we can divided out all squares from the a_i, since they make no different. Thus, each a_i is then a product of unique primes. If we want to transform a_i and a_j so that their product becomes a square, the cost is the number of primes that appear in one but not the other. Each a_i can have at most 7 primes (2*3*5*7*11*13*17*19 is too big), so at most 128 factors. Sweeping left to right, keep track of dp[f][k], the rightmost a_i so far that can be expressed as f times exactly k other primes. To add a new a_i, consider each factor f it has and the number d of primes in a_i/f; then consider pairing it with dp[f][k] for each k to get a potential solution. That's probably not that clear, but see my solution (http://mirror.codeforces.com/contest/1028/submission/42197383) for more.

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

      Thank you!

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

      Hey bmerry , I am unable to understand your H, please help me and elaborate more... especially this line , " the rightmost a_i so far that can be expressed as f times exactly k other primes"

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

        I think it's exactly the same DP array as in the official editorial. Does that help?

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

          Editorial also did not explained that thing in detail. Please explain just that one thing... What does states of dp denotes..

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

            Let's say the array values we've processed so far are 3, 42, 210, 70, 100, 14. What is dp[7][2]? It is the rightmost position which contains 7 times 2 other primes. 42=7*2*3, 70=7*2*5 are the candidates, and 70 is the rightmost, so dp[7][2] is the position of the 70. 210=7*2*3*5 and 14=7*2 are not candidates because they have the wrong number of primes, and 3 and 100 are not candidates because they're not divisible by 7.

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

              Thanks man for precious time. Got that.. People like you keeps coding alive.. Thank you very much.

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

any editorials is there ??

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

Why did you change points for the round? (it was + 121 became + 120) ( Sorry for my english, I just was not in England)

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

    Maybe because of some cheat issues?

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

      I mean,two persons’ solutions are very similar.So they unrated.The”rating changes ”changes.

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

      Huh, but why then so quickly issue a rating?

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

    Same thing happened to me. Checking for cheaters is usually done before the rating change is issued, so I don't think that's the reason. It would be nice if the administrators told us if the copying system is failing, or if it was updated in some way. At least let us know if we should expect more random rating drops.

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

hj

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

What's about prizes?

→ Reply