Zlobober's blog

By Zlobober, 3 months 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, -__-, halin.george, grikukan, malcolm734, 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. wxh_ak
  2. xolm
  3. Fireworks
  4. nicholasrr
  5. Rawnd

The analysis is published. Thanks to all for participating!

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

»
3 months 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, и вы можете успеть поучаствовать в обоих раундах, если хотите.

  • »
    »
    3 months 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 часа соревнований.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -29 Vote: I do not like it

    I think will be good ,if we have 10 or 15 minutes before CS academy Zlobober .

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

    Я думаю было бы хорошо ,если бы мы имели 10 или 15 минут до CS academy Zlobober .

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +186 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +143 Vote: I do not like it

Why this round called extraordinary? :)

Capture

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      Some crazy things like "there will be subtasks" comes to my mind :)

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I'm sorry to disappoint you, but there won't be any subtasks. Also, if there was any difference in contest format, most probably round wouldn't have been rated.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, makes sense. Thanks!

    • »
      »
      »
      3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3 contests in 3 days fantastic :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -59 Vote: I do not like it

    Not to mention: - You just got 3 upvotes - As of now, this comment was posted 33 minutes ago - Your first name has 3 m's and 3 vowels - Your last name also has 3 consonants

»
3 months ago, # |
  Vote: I like it -76 Vote: I do not like it

Is the round rated?

»
3 months ago, # |
  Vote: I like it +70 Vote: I do not like it

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

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +184 Vote: I do not like it

      Graphical Illustration :)

      Forgive my paint skills.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      why you have to be mean to him ?

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            Because he is Purple..? The Evolution Of Codeforces

            Mathforces -> implementationforces -> geometryforces -> ColorForces

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
              Rev. 2   Vote: I like it -16 Vote: I do not like it

              Codeforces -> Colorforces

              Come on, even the legendary grandmasters admit it. And by leeching of their legitimacy to prove this, I too am contributing to it.

              This comment is an example: watch me get downvoted to hell because I am gray and posted this.

    • »
      »
      »
      3 months 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.

    • »
      »
      »
      3 months 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 :)

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +59 Vote: I do not like it

      No, I hate geometry.

    • »
      »
      »
      3 months 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 :)

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck and high ratings for everybody

»
3 months ago, # |
  Vote: I like it -41 Vote: I do not like it

PLZ downvote or be bad at code!

»
3 months 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

  • »
    »
    2 months 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.

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

May the force be with all....

»
3 months 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?

»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hope problems are better than previous contest.

»
3 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

we need more CF rounds!!!

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Score distribution?

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months 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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months 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 :(

»
3 months 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    priority queue on cost.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DSU

  • »
    »
    3 months 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.

  • »
    »
    3 months 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

  • »
    »
    3 months 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)

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve div2 D/div1 B ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Prefix/suffix minimum sweep line

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mind to explain?

      • »
        »
        »
        »
        3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you suggest some good tutorial of this topic?

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    3 months 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).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

do me git rate for contet?

»
3 months 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

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
3 months 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?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain your dp solution?

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Do you have any proof?

        • »
          »
          »
          »
          »
          3 months 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.

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Too many data structure!

»
3 months 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 :(

»
3 months 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.

»
3 months 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!

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also have a constant O(6nlognlogn)

        • »
          »
          »
          »
          »
          3 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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!

            • »
              »
              »
              »
              »
              »
              »
              2 months 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).

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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 ^_^

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

my reaction while pretests is running

»
3 months 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. :(

»
3 months 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    You sound so arrogant man ? !

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2C solvable with segment tree?

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

    Yes, but with priority_queue is easier.

  • »
    »
    3 months 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 :/

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    i used a greedy approach with a set

    • »
      »
      »
      3 months 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 :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2C ?

  • »
    »
    3 months 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 .

  • »
    »
    3 months 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.

»
3 months 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

  • »
    »
    3 months 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.

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to slove div2 B....

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    cout << 1 << ' ' << min(n - k, 2 * k);
    
  • »
    »
    3 months 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.

»
3 months 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, i got AC with merge sort tree

  • »
    »
    3 months 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.

  • »
    »
    3 months 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 :(

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used persistent segment tree.

»
3 months 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

»
3 months ago, # |
  Vote: I like it +76 Vote: I do not like it

when i locked my solution and solution is hacked

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve div2/C .

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Record the boundary range with a next array

  • »
    »
    3 months 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..

    • »
      »
      »
      3 months 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 .

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    priority_queue + save index which have the same cost

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months 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

      • »
        »
        »
        »
        2 months 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.

»
3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Anyone with probably correct solution to Div1 E?

  • »
    »
    2 months 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).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months 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).

        • »
          »
          »
          »
          »
          2 months 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).

          • »
            »
            »
            »
            »
            »
            2 months 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?

            • »
              »
              »
              »
              »
              »
              »
              2 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months 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).

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    unDERSTANDAble haᵥₑ ₐ ₙᵢcₑ daY

  • »
    »
    3 months 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 ?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
3 months 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

  • »
    »
    3 months 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.

  • »
    »
    3 months 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).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Accepted now, thank you all!

»
3 months 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

»
3 months 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).

  • »
    »
    3 months 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)

    • »
      »
      »
      3 months 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 :)

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it +38 Vote: I do not like it

Mike Bought a nitro for the systest :D

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Bugatti CF Systems

»
3 months 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)?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also getting WA on same Test case :(

  • »
    »
    3 months 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.

  • »
    »
    3 months 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

»
3 months 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).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe compressing the coordinates and not using a unnordered_map.

  • »
    »
    3 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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://codeforces.com/contest/853/submission/30166694 my 2D Fenwick Tree

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

    Turns out you can calculate everything using only 4 queries.

    • »
      »
      »
      2 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months 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

»
3 months ago, # |
Rev. 2   Vote: I like it -42 Vote: I do not like it

i guess the contest is unrated :/

»
3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so is it rated?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my fault. rating updated when i refresh the website.

»
3 months 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?

»
3 months 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 :(

  • »
    »
    3 months 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?

    • »
      »
      »
      3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    3 months 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 :)

    • »
      »
      »
      2 months 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 :)

»
2 months 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 ?

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    He is mcfx.

    You can compare their code style.

    30148890 29986148

»
2 months ago, # |
  Vote: I like it -40 Vote: I do not like it

I really want to thank you for your great post. Keep doing like this. Godaddy $1 Web Hosting is one of the best web hosting services in the world. Thank you.

»
2 months 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!

»
2 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Did you see that in the prolog to the contest [gritukan:http://codeforces.com/profile/gritukan] is grikukan. Is it corrigendum?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to learn data structure and dynamic programming logic easily. please, give me some helpful codeforces blog or others link.