Zlobober's blog

Codeforces Round #433 (based on Olympiad of Metropolises)
By Zlobober, 7 years ago, translation, In English

Hi everybody!

These days Moscow is conducting the 2nd International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Almaty and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401).

We are very grateful to MikeMirzayanov for Polygon system that made it possible to conveniently hold a simultaneous statement translation process into lots of languages. As a good friends of Codeforces platform, we conduct a parallel rated Div. 1 + Div. 2 round on the competition problemset.

Round will happen on September 6th at 12:55 UTC and it will last for two hours. There will be 5 problems for each division, scoring will be announced later.

Scientific Committee of the olympiad consists of: andrewzta, GlebsHP, Endagorion, meshanya, Chmel_Tolstiy, Zlobober, Helen Andreeva and Bakhyt Matkarymov. Problems were prepared by timgaripov, mingaleg, halin.george, vintage_Vlad_Makeev, malcolm, LHiC coordinated by your humble servant.

Codeforces coordinator KAN helped us to choose problems for a round.

Good luck and high ratings for everybody!

PS We kindly ask everybody who knows problems of an on-site event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

Congratulations to the winners!

In div. 1 they are:

  1. Um_nik
  2. fateice
  3. KADR
  4. dotorya
  5. FallDream

In div. 2 they are:

  1. jiangIy
  2. xolm
  3. YxqK
  4. lixolas
  5. Rawnd

The analysis is published. Thanks to all for participating!

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

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

Note that round ends 5 minutes before CSAcademy Round #47, so you can participate in both of them if you want.

==============

Обратите внимание, что раунд заканчивается за 5 минут до CSAcademy Round #47, и вы можете успеть поучаствовать в обоих раундах, если хотите.

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

    I'm afraid that my laptop chagre is not enough for 4 hours of competition.

    ==============

    Я боюсь, моему ноутбуку не хватит заряда на 4 часа соревнований.

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

    We postponed the start of the CS Academy round by 15 minutes.

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

Why this round called extraordinary? :)

Capture

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

    I believe this means that the round will be rated differently. Not sure on the specifics though.

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

    This word is a translation of "внеочередной" and is used in the literal sense of it — "out of regular order", "specially arranged" (as you can see it's published the day before it takes place), as opposed to the more common meaning, "unusually good".

    This translation of the word is bad but I can't think of a better one.

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

      Yeah, makes sense. Thanks!

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

      A better way to write is "Rated, extraordinary Codeforces ...". Still not so good but at least people would not have any doubt about rating.

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

3 contests in 3 days fantastic :)

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

Is the round rated?

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

I hope there won't be a geometry problem :D

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

    Would be interesting to see the dependency between rating and not loving geometry. I'm pretty sure that yellow+ people don't care, while all the greens hate it.

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

      Graphical Illustration :)

      Forgive my paint skills.

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

      why you have to be mean to him ?

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

        He wanted to see the dependency between rating and not loving geometry :(

        Offtopic Codeforce is missing emojis :D

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

          i don't mean you i mean him why he has to be mean to people with lower rating

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

            Because he is Purple..? The Evolution Of Codeforces

            Mathforces -> implementationforces -> geometryforces -> ColorForces

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

      I would beg to differ. Geometry is rather hated all around the world by vast majority of people. The thing is, green struggle to check whether n points are collinear and reds struggle with computing area of sum of pacmans by integrating border of regions with holes with border consisting of different arcs and segments :P. However I like geometry. I think that maybe geo problems are not as appealing as others but I have just simply forced myself to like it because somebody in our team had to do this :P. And dealing with all stupid corner cases and precision issues is never exciting.

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

      I really hates geometry, so I'll be a great counterexample for that sentence :)

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

      I don't get it that how a particular type of problems should be or can be hated. I mean, there are so many topics there, and if one is not comfortable with some topics or faces difficulties in solving problems regarding those, he/she shouldn't dislike/hate it. Every topic has its own beauty. I personally like geometry even though I am not so good at it. And I suck at DP. Does that mean I'd say "Why so many DP problems?" or "This round sucks because 2 DP problems appeared!"??? No, I wouldn't say that. I know most people are not that comfortable with geometry problems. So what? That doesn't make it bad. And as Swistakk said, Red coders face trouble with really tough geometry problems and Blue/Green/Cyan/Grey coders face trouble with simple problems. So, it depends on one's skill. And it can also happen that a very good geometry(or any other particular topic) problem solver is Green while a red coder is not so good with that topic. It can happen sometimes, maybe rarely. But personally I think, everyone should have basic knowledge of every topic. One should know how to check if n points are collinear and other basic geometry stuffs, and one should also know the basics of every topic that may appear in a standard programming contest.

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

        yeah, but a contest shouldn't be ALL math and geometry. What if you had a contest consisting of 6 DP problems? Wouldn't be very diverse or fun.

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

      No, I hate geometry.

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

      not really. Thanks to those geometry problems my color changed from green to light blue. I love geometry problems :)

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

Good luck and high ratings for everybody

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

I just find there is only 2016 International Olympiad of Metropolises, day 1 in CF Gym

Would you please put "2016 International Olympiad of Metropolises, day 2" to Gym

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

    I just wanted to solve the tasks of the last year, so decided to add them to polygon to test. And then decided to add to the gym also for the others. But I got bored and didn't uploaded the second day :)

    I found the tests on the official site, so you can find them and upload to polygon, if you want.

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

That's my last chance to become an expert till tomorrow.

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

May the force be with all....

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

For every contest, score distribution is announced just before the contest starts. Just for my curiosity, I want to know, what's the reason behind this?

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

The start time of this contest is perfect. thank you ♂ sir

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

Hope problems are better than previous contest.

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

we need more CF rounds!!!

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

Score distribution?

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

WTFFFFFFFFF? WHY DIV1D is very easy??? I hope it will not faill

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

    Did you write dp[i][money on card] or what?

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

      dp[i][j] means minimum answer for first i numbers with at the end you have 100*j bonus. (why 100*j? because j is divisible by 100 everytime)

      So, you can calculate dp in O(n2) easily, but I guessed it is not optimal to have > 3100 bonus. I'm not sure that it will pass systest

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

        I hope >2000 is not optimal, otherwise my solution is wrong :/

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

        Hope there won't be problems where you assume things at EJOI.

        I am not that good at such problems, always trying to prove things and then I spend a lot of time on some math (99% of cases I fail to prove). Just assume that as a fact but by the time I start coding the contest is over :(

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

How to solve Div 2 C? I tried to find a recurrence relation for 1 hour before giving up.

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

    priority queue on cost.

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

    DSU

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

    Prepare a set S comprise of number from k+1 to k+n. Iterate over the flights in decrease order of their cost. For each flight, let's call the initial departure time i, find the first number in the set S that is greater or equal to i+k, erase that number from the set.

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

    Sort the flights by their price in a descending order, then for each flight you have to do one of those things

    1-the flight is already fine, no need to delay it(i > k) 2-the flight is bad, so you need to find the first j where j > k && j <= k also j must be minimum and set the flight to that time(you have to keep in mind that there is no other flight in the time j) and add the cost

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

    I used intervals tree for find first free place, starting with min(i,k)

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

How to solve div2 D/div1 B ?

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

    Prefix/suffix minimum sweep line

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

      mind to explain?

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

        You need to find the minimum possible cost to cover all flights for n people towards the Metropolis within a certain prefix, and similarly we do that for each suffix. Then, you just do a sliding window, and at each step of the iteration, you can find the answer in O(1) using the precomputed prefix and suffix values.

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

      Can you suggest some good tutorial of this topic?

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

        This isn't a geometry sweep line, it's just the standard technique that's usually finding interval intersections and stuff like that.

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

    Sort all flights by their departure day. Now iterate over the last day that everyone must be in city 0 (from k to 1e6). We can see that the number flights we can use to go home will only decrease while the flights we can use to go to Metropolis increase. Now just keep minimum for every person (to go home and to go to Metropolis).

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

Is there nlogn scanline solution for div1C? I solved it with merge sort tree in O(6 * n * logn * logn), but I'm quite concerned about TL

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

    Well I calculated number of points in all 9 directions of every rectangle, so my solution is 9 * NlogN, if you accept that as NlogN :D

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

      Mine was 4*QlgN, I calculated the points that are up-left,up.right,down-left and down right for every query

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

    Yes i did with scan line in the O(6*n*logn)

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

    Yes. You can sweep from left to right and do all the queries when appropriate using a binary index tree to query the appropriate 8 regions.

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

How to solve C?

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

Is the there a hack test for DPpos, money, where money is current money in card?

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

    Can you explain your dp solution?

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

      Well DPpos, money is the answer till pos if we have money money (:D) in the card. I assume that if money > 3000 we will just pay for the next by card. And we have 2 cases for the dp: either we pay everything by cash, or we remove Y (from 1 to min(currentcost, money)) from the card.

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

        Do you have any proof?

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

          Nope, I stresstested it with a brute force (1000 random tests) and it was ok, but still I'm not sure so that's why I asked if someone has a counter sample.

          UPDATE: it passed.

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

Too many data structure!

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

My current rating=2017, so this is good bye 2017 for me. Also goodbye div 1 :(

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

Binary search + segment tree (query min prefix) solve D1 D in any contrains for cost, bonus.

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

Time limit of Div.1 C is too tight, I kept getting TLE on pretest 4 with N log N complexity! It's not fair!

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

    Well, i passed pretests with O(nlognlogn) solution, so there may be a problem in your implemention

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

      I think there's nothing wrong with my implemention, maybe I have a large contant. That leads to 9 * N * log N.

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

        I also have a constant O(6nlognlogn)

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

          O(6 * N * log N * log N) passed? That's crazy. Well, perhaps I was wrong. I'll check my program later.

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

          I have corrected my answer. It seems that my submission during the contest was right, but I picked the wrong data structure. The problem can be solved with binary search tree by making all queries offline, but I used persistent segment tree. That brought me a huge constant, I think I could pass within 3 seconds. Thanks for listening to my problem.

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

            Good day to you,

            well I managed to get AC with PST (in ~1.6) so it shall be no problem.

            Your PST seemed to run even faster then mine.

            Moreover if I changed the limits:

            #define MAXN	500005
#define MAXP	18200095

            the TLE turned into WA (but hope I didn't broke anything by this)

            Good Luck & Have Nice Day!

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

              I'm sorry but I'm quite sure my PST method runs much slower than my BIT method (about twice slower), and my BIT method passed in 1.2s. That program might be my last submission during the contest, I had not finished debugging it, so it went WA. Check my previous submissions during the contest, I was saying about that. Thanks a lot for listening to me and wish you a nice day (Exactly evening here in China).

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

                Oh yes, I didn't want to doubt about this statement (imho PST has very big "constant" even though the complexity is nice — due to memory).

                I just wanted to propose that the mistake might have been somewhere else — anyway seems you have tried to increase constants too (with TLE) so I'm slightly confused :O :P [maybe other submission]

                Well so enjoy your evening then ^_^

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

my reaction while pretests is running

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

    same reaction when main tests and hacks are running as well.

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

Finding a typo in my code for problem D after the contest ended. However it still passed the pretests. Pretests for D are too weak. :(

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

A minute of silence for a contestant who made the following "genius" piece of code...

int n; //Size of array P
PersistentIT t;

ll Solve(int l, int r, int d, int u) {
    ...
    int n = (r-l+1);
    int nu = t.query(l, r, u+1, n);
    ...
}

I can't believe that it took me nearly 1.5 hours to solve C (with I should be able to do in less than 15 minutes, given that I had the Persistent IT template). I'm so terrible at not creating bug T_T

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

    I'd recommend using the -Wshadow compiler option because of this. It saved my life quite a few times.

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

Div2C solvable with segment tree?

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

    Yes, but with priority_queue is easier.

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

    I solved it with segment tree and my code is 120 lines long. I see other people submissions that are <=50 lines and I feel stupid :/

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

    i used a greedy approach with a set

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

      I used greedy with vector pair!! WA just cz of missing long long :(

      Same code passed on adding long long after the contest :(

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

How to solve div2C ?

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

    I used MergeSort + BinarySearch but couldn't finish the code before the contest .

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

    I solved it using a set. First, insert all numbers from k + 1 to k + n into the set. Sort the given elements by the decreasing order of C, call them a[i].c, keeping their initial positions, call their initial positions id. Then iterate through the sorted array, and find lower_bound of the index, call it idx, and remove it from the set. Add ans = ans + (idx — a[i].id)* a[i].c.

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

Does anybody have solution to D, which is clearly correct? I wrote something and I've stresstested it, so I'm not in this group :P

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

    I think so.

    Let's do binary search on answer. It is clear that we will spend bonuses on last 1000s and last 2000s (it can be not a suffix, for example 2000 2000 ... 2000 (9 times) 1000 2000 1000, it is optimal to spend bonuses on two 1000 only). But if we omit two 1000s or take two 1000s after omitting 2000 (going from right to left) we can change it (two 1000 for one 2000, take the variant which is more on the right). So we have only O(1) possible variants, each of them can be checked in O(n) time.

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

    You can show that there is an optimal solution that pays for the first k using cash, and the last n-k using rewards card, except for at most one exception which costs 1000.

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

how to slove div2 B....

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    cout << 1 << ' ' << min(n - k, 2 * k);
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    More clearly...You can consider a chosen one's left and right are all available and actually good. So you can divide the grids to blocks which contains 3 grids each(Sorry for my bad description) And when k>floor(n/3) it can be count by n-k because all the empty grid are next to a chosen one.

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

Is div1C merge sort tree? I found bug in my solution but still not sure if it's the right way

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

    It can be done offline using sweep line + Fenwick trees.

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

    Mine is with simple wavelet tree. It runs fast enough.

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

    I think my code is right now. How can I submit my code after the contest? There is no button appearing.

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

      You will have to wait until after system testing has finished. At that point you will be able to submit again.

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

    Yes, i got AC with merge sort tree

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

    I solved it offline using SQRT decomposition + Fenwick trees. Managed to squeeze it into TL.

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

    Can be easily done by greedy + vector pair!! I got WA cz of missing to typecast answer to long long :(

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

    I used persistent segment tree.

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

I wrote a '+' instead of a '-' in a 200-lines code on C and I found it 1 minute after contest ended :( FML

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

when i locked my solution and solution is hacked

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

how to solve div2/C .

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

    Record the boundary range with a next array

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

    This is my solution and might be wrong

    1-Sort the A[] in descending order of cost (store it as pair<cost,time of flight>)

    2-Make a set and insert all possible values which is from (k + 1 -> k + n)

    3-Now loop over the A[] and do this for each value

    binary search on the lower bound for the (time of flight) then before removing it cost += (newTime of Flight — oldTime) * A[i].cost;

    4-Remove the new time of flight from the set

    The flight with huge cost, the place wont change or change minimally..

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

      I used that approach . but the problem was with calculating the total cost it was always wrong .

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

    priority_queue + save index which have the same cost

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

    Greedily assign the most expensive flight to the earliest time you can.

    How do you find this earliest time? My approach was to keep all indices from k+1 to k+n in a set. Then, when an index is assigned, remove it from the set. To find the earliest index, use set::lower_bound.

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

      why is this similar approach giving TLE on test case 6? code

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

        Your TLE lies in this line

        lower_bound(st.begin(),st.end(),c[i].second);

        should be

        st.lower_bound(c[i].second)

        code

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

        That was the exact mistake I made. Use set's lower_bound, not the generic one.

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

I misread the statement of Div2.D that there will be flights between the cities. Then I went to an intricate solution using ternary search + visual vertexes + shortest path on a reconstructed graph and a transposed one. Failed to finish the implementation.

Maybe I should improve my reading. The previous round is ruined for I misdeemed that given points A,B,C can be exchanged.

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

I can't debug 1B out... Goodbye div1...

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

    You are probably doing some loop till n instead of till m. Had the same retarded bug and got WA on the same test as you

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

      I still can't find the problem, probably we coded wrong on some different places and WA'ed on the same pretest

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

Anyone with probably correct solution to Div1 E?

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

    First, you can compute the Minkowski sum of the velocity vectors. This gives a convex polygon with 2k sides that describes achievable speeds. Then, to compute the answer for a exhibition i, center the polygon on the exhibition, scale it depending on the number of days ti, and count the number of factories inside it.

    To compute the number of factories inside it, split the polygon into 2k triangles, and sum the results for each triangle. The hard part is then to compute the number of points inside a triangle.

    Actually, there are only 2k different kinds of triangles if we ignore translation and scaling, and for a single kind of triangle, we can compute all values in O(n log n).

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

      How do you compute in O(n log n) for a triangle?

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

        We can assume that the triangle is (0, 0), (0, 1), (1, 0) by changing the base. We have points (xi, yi), and queries (ai, bi), (ai, bi + ti), (ai + ti, bi). With a single sweep along x + y, it is possible to compute values in O(n log^2 n). With a sweep along x + y, and a sweep along x, I think it is possible to reduce it to O(n log n) by computing #(x + y < ai + bi + ti) - #(x + y < ai + bi + ti, x < ai) - #(x + y < ai + bi + ti, y < bi) + #(x < ai, y < bi). (I will try to draw something to explain it).

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

          It is correct, but kind of an overkill.

          You may express the original polygon as a sum of 2k half-infinite trapezoids, some of which are added and some are substracted. A number of points in a trapezoid of fixed shape may be found in O(n log n).

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

            Sorry, I don't see how you would decompose the polygon into the trapezoids. Could you explain?

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

              Shoot a downwards ray from each vertex of the polygon. Each side of the polygon along with its two rays forms a half-infinite trapezoid

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

                Okay. But in what way is this easier than a triangle, with one base of length zero?

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

                  Well with similar trapezoids you can transform them all into rectangles. Then counting the number of points inside a rectangle can be done with a single sweep + fenwick tree. I think doing this with triangles is a lot more complicated.

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

                What kind of transformation makes it a rectangle?

                Also, couldn't some of the regions become triangular when you draw the downward lines?

                Sorry for the questions, just have never seen this technique before.

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

                  Perhaps calling it a trapezoid is confusing? The trapezoids have no bottom edge, as the downwards rays extend to -infinity. The idea is that for each side of the polygon, we want to sum all the points underneath it. Then to get the sum of points inside the polygon, we add up the points below the upper hull and subtract away the points below the lower hull.

                  All the trapezoids are two vertical lines and then a sloped line. Half-infinite trapezoids with the same slope can all be transformed into half-infinite rectangles with a change of basis. So if the side of the polygon is the vector (a, b), the transformation (x, y) -> (x, ay-bx) works (it makes the sloped side horizontal).

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

                Oh, okay. I thought the "trapezoids" were real 2D trapezoids, which cannot be affine transformed into rectangles, but it all makes sense with infinite trapezoid. (I guess a triangle is a sum/difference of two or three trapezoids, then.)

                Thanks for taking the time to explain.

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

Why doesn't system testing start right after the contest ends?

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

    I shouldn't be the one posting this but the problemsetters :D

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

    I just wanted to know why it doesn't happen. Why are you making fun of it ?

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

      You'll understand that once you decide to handle your own round :)

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

I solved Div1 D like this and hacked. Is there any counterexample?

1) Try buying first k with money only 2) Try buying first k with money only, except the last "1000" of them

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

    You're missing the case of buying first k plus the first "1000" after them.

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

    Try this one?

    13
2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 1000 1000

    It should returns 21900 by buying first ten of 2000 and the first 1000 (12-th position).

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

    Accepted now, thank you all!

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

How can i know for which input was my DIV2B hacked?

Thank you

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

Today I learned: if s is a set, lower_bound(s.begin(),s.end(),v) is not guaranteed to be logarithmic. Use s.lower_bound(v).

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

    I learned that in an official contest :') , AFAIK in worst case it can run in O(N^2)

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

      Yep. Got TLE on problem A today because of it. Luckily some frantic Googling let me fix it in time :)

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

    http://en.cppreference.com/w/cpp/algorithm/lower_bound

    The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-RandomAccessIterators, the number of iterator increments is linear.

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

Mike Bought a nitro for the systest :D

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

Bugatti CF Systems

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

can someone tell me what is wrong with my code 30156568 for 2D(1B)?

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

    I am also getting WA on same Test case :(

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

    I think you miss a condition int your get_ans(): from 1 to i there must be n flights with different departure cites, and also from i + k + 1 to the last day, there must be n flights with different arrival cities.

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

    I found that your code had some small mistakes:

    1. var "myINF" was declared as a 32-bit integer, but exactly it should have declared as a 64-bit integer.

    2. the answer could equal 1e12, so the INF should be a little bigger.

    3. the max suffix or prefix ans may be updated more than once in one day, so in the function goright dpr[i]=dpr[i]-prev+sumright[num]; is correct.

    this is the correct version 30160358

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

Can anyone tell me if there is a way to make 30158579 faster? In each query I use 6 calls to 2D Fenwick Tree, so the complexity is O(Q log^2 N).

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

    Maybe compressing the coordinates and not using a unnordered_map.

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

    Good day to you,

    Firstly, such 2DFenwick also has "hash-map-complexity" which can't be neglected.

    Well there were some other greedy solution for this problem anyway to keep problem, simply replace fenwick, you can:

    Use some segment-structure, whic could answer: Number of numbers on "[L → R]" lesser/equal then "X" (if you want rectangle [L,X]→[R,Y]), you can ask [L,R,Y]-[L,R,X-1].

    First structure, which could do it in "clear" O(logN^2) is merge-sort tree (segment tree with sorted number in each node. You use it as classical segment tree with binary searches)

    Second — probably faster — way is Persistent Segment Tree (you can simply add "1s" in order of their heights). This works in O(log(N))

    Hope it is understandable.

    In case you are interested in anything (or it was not undestandable), don't hesitate to ask.

    Good Luck & Hope it helped,

    Have nice day!

    ~/Morass

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

    Instead of storing a pair in unordered_map, try using an array of unordered_maps. Although 6 calls to 2D Fenwick tree seems unlikely to pass given the constraints and time limit.

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

    I managed to make a 2D Fenwick Tree pass using the query logic of another submission:

    http://mirror.codeforces.com/contest/853/submission/30166694 my 2D Fenwick Tree

    http://mirror.codeforces.com/contest/853/submission/30149861 original submission for the logic

    Turns out you can calculate everything using only 4 queries.

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

      I managed to narrow down my answer for one question to two queries to fenwick tree, but still it wasn't good enough, probably this map/unordered_map is too much.

      Edit: Nevermind, forgot about two corners, it's 4 calls.

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

What did the "rated extraordinary" mean, for this contest?

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

    The rating will increase / decrease by a factor of 500 today. For example, in any other contest, if u get , today you will get

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

i guess the contest is unrated :/

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

Why using arrays here took 826 ms while the same code using vectors here took 264 ms.

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

so is it rated？

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

    my fault. rating updated when i refresh the website.

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

How does Div2C greedy approach work? We can create a bipartite graph with the left vertices as initial times and the right vertices as final times and an edge with the weight of the cost. It is a classic assignment problem. What condition in this question reduces the problem complexity making the greedy solution optimal?

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

Weak testcases ( in Pretest ) in DIV2-D. No integer overflow upto 75 testcases. Got overflow in testcase 76 due to int declaration :(

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

    LOL, since when do people call testcases "weak" when they manage to fail their codes?

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

      (Edited) Weak Pretests actually. If there were overflow cases in pretests, may be I could manage to figure out mistake during contest.

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

Can someone tell me why this does not get a TLE ?

http://mirror.codeforces.com/contest/854/submission/30162063

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

    because c++ is clever :D this while is O(1) :

    long long test = 1000000000000000000; while(test) {

    test--;
}

    and anythings like these are O(1) too is c++ :

    int ans = 0;

    for(int i = 1 ; i <= 1e9 ; i++)

    ans++;

    or

    int ans = 0;

    for(int i = 1 ; i <= 1e9 ; i++)

    ans += i;

    my teacher M.Mahdi said these to me :)

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

      Thanks a lot man... I tried to hack a solution containing similar type of loop and failed. at least learnt something new :)

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

what is the case 83 in div2.d ? any special case or overflow reasons ?

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

jiangIy ( first in div 2 ) . First contest encrypted submission. 25623055

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

    Doesn't it violate Codeforces' "Can't-do"s (here)?

    Point 4 of "Can-do's and Can't-do's":

    It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.

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

    He is webmaster.

    You can compare their code style.

    30148890 29986148

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

I was in doubt if I would attend to a class or do the contest. It seems that it was worth taking the contest =D Thanks for the congratulations!

→ Reply