Блог пользователя Zlobober

Автор Zlobober, 7 лет назад, По-русски

Всем привет!

В эти дни в Москве проходит вторая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены члены жюри, приглашённые из Санкт-Петербурга, Минска, Алма-Аты, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401).

Мы очень признательны MikeMirzayanov за разработку системы Polygon, которая делает возможным и очень удобным одновременный перевод условий на большое количество языков, и, по давней дружбе с замечательной платформой Codeforces, мы проводим параллельный рейтинговый Div. 1 + Div. 2 раунд на задачах соревнования.

Раунд состоится 6 сентября в 15:55 по Москве и продлится два часа. В каждом дивизионе будет предложено по 5 задач, разбалловка будет объявлена позднее.

В составе жюри олимпиады: andrewzta, GlebsHP, Endagorion, meshanya, Chmel_Tolstiy, Zlobober, Елена Андреева и Бахыт Маткаримов. Задачи олимпиады разрабатывали timgaripov, mingaleg, halin.george, vintage_Vlad_Makeev, malcolm, LHiC под руководством вашего покорного слуги.

Выбрать задачи для раунда помогал координатор Codeforces KAN.

Всем удачи и высокого рейтинга!

PS Мы просим всех, кто участвует или знает задачи с основного соревнования, воздержаться от участия в раунде и публичного обсуждения задач, в противном случае вы можете быть дисквалифицированы.

Поздравляем победителей!

В div. 1 это:

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

В div. 2 это:

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

Опубликован разбор. Всем спасибо за участие!

  • Проголосовать: нравится
  • +235
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +129 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -32 Проголосовать: не нравится

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

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

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +186 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +143 Проголосовать: не нравится

Why this round called extraordinary? :)

Capture

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

3 contests in 3 days fantastic :)

»
7 лет назад, # |
  Проголосовать: нравится -76 Проголосовать: не нравится

Is the round rated?

»
7 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +184 Проголосовать: не нравится

      Graphical Illustration :)

      Forgive my paint skills.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      why you have to be mean to him ?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        Offtopic Codeforce is missing emojis :D

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +30 Проголосовать: не нравится

            Because he is Purple..? The Evolution Of Codeforces

            Mathforces -> implementationforces -> geometryforces -> ColorForces

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +76 Проголосовать: не нравится

      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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +59 Проголосовать: не нравится

      No, I hate geometry.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Good luck and high ratings for everybody

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Алма-Ата переименовали в Алматы в 1993 году.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

May the force be with all....

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Hope problems are better than previous contest.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

we need more CF rounds!!!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where can i find soloution for problems? i really need to cheat

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Score distribution?

»
7 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    priority queue on cost.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    DSU

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve div2 D/div1 B ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Prefix/suffix minimum sweep line

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      mind to explain?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Can you suggest some good tutorial of this topic?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain your dp solution?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Do you have any proof?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          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.

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Too many data structure!

»
7 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I also have a constant O(6nlognlogn)

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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!

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 ^_^

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

my reaction while pretests is running

»
7 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2C solvable with segment tree?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Yes, but with priority_queue is easier.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    i used a greedy approach with a set

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div2C ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to slove div2 B....

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    cout << 1 << ' ' << min(n - k, 2 * k);
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

when i locked my solution and solution is hacked

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve div2/C .

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Record the boundary range with a next array

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    priority_queue + save index which have the same cost

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Anyone with probably correct solution to Div1 E?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Accepted now, thank you all!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Thank you

»
7 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Mike Bought a nitro for the systest :D

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Bugatti CF Systems

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am also getting WA on same Test case :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe compressing the coordinates and not using a unnordered_map.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

i guess the contest it unrated :/

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -42 Проголосовать: не нравится

i guess the contest is unrated :/

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so is it rated?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    He is webmaster.

    You can compare their code style.

    30148890 29986148

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!