Автор awoo, история, 5 лет назад, По-русски

Привет, Codeforces!

В 13.11.2019 17:35 (Московское время) состоится Educational Codeforces Round 76 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Внимание Codeforces!

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

Harbour.Space University в партнерстве с SCG, ведущим бизнес-конгломератом в регионе АСЕАН, предлагает исключительным техническим специалистам возможность работать и учиться в двух самых динамичных городах мира. Присоединяйтесь к нашей прогрессивной двухлетней программе, базирующейся в Бангкоке, с 6 месяцами из 24 — в Барселоне, чтобы развить навыки, необходимые для ускорения вашей карьеры и переосмысления того, как данные влияют на бизнес будущего.

Codeforces and Harbour.Space

Плата за обучение:

2 года | €45,800

Образование:

3 часа обучения в день | 15 часов в неделю

Опыт работы:

4 часа стажировки в SCG в день | 20 часов в неделю

Пособие:

€16,800 | €700 в месяц


ПОДАТЬ ЗАЯВКУ→

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

Место Участник Задач решено Штраф
1 neal 7 182
2 kmjp 7 216
3 saketh 7 218
4 KrK 7 225
5 ivan100sic 7 244
5 pwild 7 244

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 Decayed 39:-10
2 liouzhou_101 59:-58
3 dzhiblavi 15
4 Rian_5900 31:-40
5 Fyodor 10:-2
Было сделано 278 успешных и 501 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A amnesiac_dusk 0:00
B Siberian 0:02
C Bohun 0:03
D LJC00118 0:16
E jjang36524 0:23
F TripleM5da 0:19
G black_horse2014 0:19

UPD: Разбор опубликован

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

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

Hope to become expert in this contest......

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

Strange that there's only one comment in 14 hours. Anyway, it's a PikMike contest so I'm excited. Hope I can finally get candidate master lmao.

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

hope to become specialist in this contest.

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

Hope to become 1500+ this contest.

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

Good Contest.

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

Were Segment Trees necessary in D? I had to do some maximum queries on the monster array, was too scared to try my solution without the tree.

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

How to solve C?_

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

    The answer is the minimal distance between two equal elements.

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

      why

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

        If you check the subarray that is the answer to the task, you will see that it's first and last elements are equal (because it is the most optimal). And all the elements between them are all different.

        Sorry for my poor (maybe) English.

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

        If you look at two equal elements in an array then the only case where it is not dominant is if there is at least another pair of two inside. The equal elements that have the minimum difference between them cannot contain another pair because that would contradict that the elements we found have the minimal difference.

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

        because when you take two elements with minimum distance then between these two other element appear at most one.

        1231 if there is repeated value between two 1 then distance between 1 can't be minimum.

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

        Consider you have two suquences

        1 4 3 2 4 1

        Now here, we can choose the first 2nd and last 2nd element in a segment. That will form the minimum.

        and other,

        1 4 3 3 4 1

        Now here, if we choose the same indexes as an upper example, it would be wrong. Because we can still minimize the segment to {3,3}.

        So we can conclude that all we needed to do is minimizing the difference between equal elements. Hope you understood.

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

          why result is 4, 5, 4 for 4 1 2 4 5 4 3 2 1 and not 4 4 for example

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

            Because choosing a subarray should be contiguous.

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

            ****The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.****

            you missed this line.

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

      Wow, I feel dumb now jury-rigging a two-way multimap keeping track of element counts and number of elements with the maximum count

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

    you have to find minimum difference between two repeated value. save the last position you get for each value and when you get it again take difference and update position of last appearence. then take minimum of all diference.

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

    We note that, there is a answer if and only if some number is repeated otherwise ans is -1.

    The shortest such subarray will be |start of that number(x) — another instance of that number(x)| so just count how many repeated numbers are there and print the minimum distance b/w them

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

    I used two pointers which I later realized to be difficult to solve that problem.

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

In question D, codeforces giving different output than other platforms like hackerrank, onlinegdb for the same code. Output on codeforces is coming as 0 and -1 for the 1st test case but it is correct on other platforms. Does someone know why is it so

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

    It's an undefined behavior. For example if you donn't fill a local array explicitly, it doesn't have to be filled with zeros, it may be filled with anything depending of compiler.

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

    See diagnostics in your submission: "Error: attempt to dereference a past-the-end iterator." I had a similar solution with the same bug. That lower_bound returns the end of the map when there's no heroes with energy day or more left.

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

Seems not sorted by difficulty...

RIP my rating.

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

    It seemed very sorted to me. I won't say they were easy though, I might get hacked when I least expect it

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

F is just btuteforce, LOL. 100e9 in 2 seconds))

UPD 1: Hacked.

UPD 2: Added set, Accepted.

UPD 3: Passed final tests in 2.5 seconds.

UPD 4: More stable program with a run time 1.9 seconds: Link.

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

Good test cases on F, I tried my best to make random solutions pass and failed.

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

How to solve D???

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

    Greedy.Every day,choose a hero who can beat most monsters.

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

      Can anyone please elaborate on this? How to choose the hero who can beat most monsters? I did something in my solution but I find that to be too messy.

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

        Binary search on the hero. Solution

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

          I saw people's submissions where they were obtaining the suffix maximums over the max. powers needed for a fixed endurance value. I find that idea to be much less on code. I'd like to know about that idea as I am still not able to think about it.

          UPD: I have mentioned the idea in one of my comments below.

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

        Just sort the {power, endurance} array. Then start with the first monster and check maximum power needed to defeat the dragon(Binary search), also I have maintained a suffix array that will store maximum endurance. If we can defeat the dragon then try to take one more dragon on the same day otherwise start with a new day. Link to my Solution

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

    I implemented O(m*n), and though in worst case scenario there is no way it passes TL, it somehow got accepted.

    I sorted heroes in descending of their stamina, and for each hero in this order I tried to find maximum of monsters he can beat if he enters now (i.e. iterate mosters one by one and increase counter if monster is weaker and hero's stamina is not exceeded). I break cycles if I find a hero with lower stamina than my current maximum.

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

      We still are in the hacking phase, someone might try to break your code so it gives TLE, hopefully not!

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

    My approach is, at first I sort all the heroes in basis on their power and then endurance in decreasing order. Then I try to find out maximum power for every endurance. It always proves that endurance[i]>=endurance[i+1]. Finally, at every step, I just try to pick the longest endurance(using binary search) which can able to kill all the monsters on that range.(I use segment to find out the maximum monster value on that range). If there is any monster whose value is greater than the maximum hero's power then the answer is -1.

    My solution -> https://mirror.codeforces.com/contest/1257/submission/64846739

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

    I finally managed to understand the easy way to solve the problem by going through people's submissions. I'll try to explain.

    First, if we are currently at the $$$i$$$th monster, we have to choose a hero that can kill the largest no. of monsters. The only tricky thing is choosing that hero. Let $$$cnt$$$ denote the current no. of monsters that we can kill from the $$$i$$$th position. Initially, $$$cnt = 0$$$. Now, $$$cnt$$$ can be extended to $$$1$$$ iff there exists some hero whose endurance $$$\ge 1$$$ and the power is more than the power of the $$$i$$$th monster. Using this logic, we'll be extending $$$cnt$$$ as much as we can. To extend $$$cnt$$$ by $$$1$$$, we have to check to see whether there exists a hero whose endurance is $$$\ge cnt + 1$$$ and whose power is $$$\ge$$$ power of all monsters within the range $$$[i, i+cnt]$$$. If there does exist one, we can extend $$$cnt$$$ to $$$cnt + 1$$$.

    To check this thing, we can have an array we store the maximum power of a hero whose endurance is $$$\ge i$$$. This can be computed by taking suffix maximums on an array where the $$$i$$$th element is the maximum power of a hero whose endurance is $$$i$$$.

    Also, since we are always extending $$$cnt$$$ by $$$1$$$, we can instead keep a running maximum of monster's powers instead of using a data structure to obtain the maximum within that range.

    Code

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

      Hey roll_no_1, I did a similar thing as well, but in the other direction, so just putting my strategy here as well

      Invariant: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.

      Steps: Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix max

      This step would mean that at every value of endurance, the best value of power that is greater than or equal to the power for the range having more endurance is taken. (Greedy choice)

      Move from the back and kill the current monster, if you can't kill the current monster, along with the suffix, add 1, else, keep expanding the array backwards updating the maximum.

      Overall an order of O(n+m)

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

      I did solve with the same concept but with binary searching. keeping a max suffix array is much more cleaner. Thanks for sharing, I learnt something cool.

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

    You can solve the problem without using segment tree or binary search. http://mirror.codeforces.com/contest/1257/submission/64838220 Just a map and lower_bound is required

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

    I did a greedy solution. 64832445

    Explanation — sort heros according to endurance and allocate each monster a hero starting from max endurance, than start making maximum group possible.

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

Given the huge TL, I imagine my solution for G is off, but is it something like finding number of solutions to $$$\sum_{i=1}^d x_i = k$$$, where $$$d$$$ is the number of distinct prime divisors and $$$k$$$ is the minimum power of one of the prime divisors?

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

    k is actually floor(n/2).

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

      Upon further thought, it makes sense that it shouldn't be the minimum power of the prime divisors, but it's not at all clear to me why floor(n/2) encodes the proper information. Can you elaborate?

      EDIT: Just tried to verify this on the samples. Unless I'm misunderstanding what you mean by n/2, this doesn't seem to work.

      EDIT2: My implementation was wrong, tried to use stars and bars where I couldn't. My bad.

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

        n is number of prime divisors given in the input.

        Lets say (p1,p2,..,pd) are the distinct prime factors and (a1,a2,...,ad) are the powers of prime factor. Now you can represent these tuple of powers (a1,a2,..,ad) for each divisor as a partially ordered set (poset).

        The goal is to find the longest antichain which is the width of the poset.

        You can notice that sum(ai) represents a distinct level.

        Lets say the number is 2^4*3^2.

        (4,2) represents level 6. (sum=6)

        (4,1), (3,2) represents level 5. (sum=5)

        (3,1), (4,0), (3,1), (2,2) represent level 4. (sum=4) and so on.

        Its kind of intuitive that the poset is symmetric about mid level (level=n/2) and that should have the maximum cardinality. I dont know a proof.

        Thus the answer to the problem is the number of solutions such that sum(ai) = floor(n/2).

        This can be solved by fft.

        My submission

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

Can E be solved using this idea:

1) Iterate from i=0 to n. i is the last problem of first-person.

2) Then do a ternary search for getting the answer among 2nd and 3rd person.

Is this idea correct?

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

    isnt binary search enough? I did not code it, I am a binary search code noob

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

    I don't think this solution is correct. As the cost of distribution between 2nd and 3rd is not necessarily unimodal.

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

I'm not sure if it was intentional, but E could be solved by ordering the three lists, concatenating them, and then running a very well known LIS (Longest Increasing Subsequence) algorithm.

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

    The answer was simply (K1+K2+K3) — N, where N is the length of the longest increasing subsequence.

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

    Can u help me prove it why is it LIS? The idea intuitively seems correct.

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

    But why it's working?

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

      Sort each array independently. Given this LIS size, you know maximum amount that are in place. The goal is to get whole array sorted, and each operation increases that number by 1 (place the element out of order to its position), so we will need that amount of operations. This is not a formal proof but an intuition of how I see it

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

      It's actually exactly COCI lista

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

    This is beyond my knowledge. Never knew LIS would be this powerful. This not only works for 3 arrays. The intuition is you want to maximize the amount of element to stay in its segment. What an elegant solution. to restore the steps of the answer, youll simply make the LIS related elements stay and move the rest greedily.

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

    It wasn't intended (model solution uses some math and prefix sums), but the solution is really cool nevertheless!

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

    Amazing solution!!

    this is a good source for people who dont know LIS to learn how it works.

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

How to solve G?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится
    Hint: It turns out 'finding' the subset is easy but 'counting' it is hard. Can you prove a certain subset must be maximal?
»
5 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Why has CF started giving T test cases for every problem like codechef does?

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

    Now it's easy for us to run all the sample cases at once

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

    It's a common solution for ERs (and, it seems, div3) because it's too much burden for the system to check 20-30 tests (and 30 tests are not enough sometimes) per each submit especially on tasks like A, B, C.

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

    I highly prefer it this way. You get to have much better test coverage without insane queues.

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

Good Contest.

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

How to solve problem C?

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

English lesson: волшебная палочка — magic wand. :)

(Don't try to look it up on Google — you'l get the wrong idea. :)))

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

Finally gained some confidence, Thank you so much for the contest.

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

only single line error in solution of problem D drop my dream of Expert.

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

how to solve F?

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

    Use meet-in-the-middle, split x into first 15 bits and last 15 bits, and use map to check if there is second half.

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

    Simplex!

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

      I also tried to solve the problem by constructing equations and inequations but didn't know how to solve the system. Can you please provide some useful resource to learn the simplex method and also to understand how to code it? Thanks.

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

Can anyone point out what the mistake could be for test-case 2 on problem D ?

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

    Try something like this: 2 6 1 2 3 3 3 3 3 3 3 6 1 1 6 (ans = 2) 6 6 1 2 3 4 5 3 3 3 6 1 1 6 (ans = 4). These tests helped me to find out my mistakes

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

i just have solved problem 1257C - Dominated Subarray — in Greedy solution in just O(n) ; why you did'nt include Greedy tag ! this is my submission : 64830934

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

    std::map works in O(log), not in O(1). So, your solution is O(nlogn)

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

      IWMG my friend did you read my solution !!!?
      i never used std: map in it but just called it . i have used just one loop to read Input and an array to store last position for an element ! why it is O(n log n ) !

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

        Yeah, im sorry for it, i thought you use only maps. Then you're right, your solution works in O(n)

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

In problem D, we have to take input from the users which is O(n). So total TC would be minimum O(t*n) which is the order of 10^12. How is it passing?

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

I can only solved 2 problems... kinda have feeling my rating will be decreased again XD. I hope I can get better next time T_T. Gotta learn more frequent.

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

Any clue about the 18th sub-test of test case 2 in problem D ?

Edit: I was writing min in place of max in Sparse Table. XD

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

Who else, first, thought of Binary Search for C? xD

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

Whats the DP solution for E?

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

    dp[i][j]: I'm looking at element i, at group j.

    I can either start the next group -> dp[i][j]=dp[i][j+1]

    or add element i to existing group -> dp[i][j]=(i is not in group j) + dp[i+1][j]

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

For all of you that want something to uphack but can't: 64856439. This shit really shouldn't pass, it should get WA or TLE or both.

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

Try to hack my $$$O(n*2^{30})$$$ solution to F: Link

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

    How does this runs in less than 2 seconds?

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

      It does, my approach takes approx. 3 seconds on the judging server of CF(I used vectors and cins and stuff), yet it took forever to run on my own computer.

      However, I am getting WA 92 for some strange reasons, and since my logic is very similar to his, maybe he will get WA on the same tese(just my guess).

      I went through his judgement protocol and saw that he has only been tested with tests 1 to 83.

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

What on earth is test $$$92$$$ of problem F? I kept getting WA for it using the most naive brute-force algorithm.

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

    You remove duplicates from the vector a but still loop up to n, not to the size of a, accessing elements past its size. It doesn't necessarily segfault since the vector had size n+1 before, but It seems something problematic happens in that test.

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

      I don't think that causes WA though? Although he/she is reading elements out of bounds, no writes were performed so the data should not be corrupted, and more reads (albeit corrupted) could only cause more "bad" cases to show up, hence this issue should not lead to false positive.

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

        I also think so. I mean, well, I am not doing anything to the out-of-bound indexes, and changing it to a.size() causes TLE3

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

Can D be solved using binary search ? If yes can anyone share their approach?

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

    Try greedily defeat more monsters, so we need to binary search how far we can reach.

    Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.

    Binary search such K and get the answer, to find P, is a problem of RMQ,use ST.

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

    Yes, there is a way. First sort all the heroes by power. Then create an array of suffix endurances for the sorted array of heroes. Suppose you have to kill k monsters on a particular day. Then find the maximum of those monsters and do a binary search on sorted heroes to find the suffix which includes all the heroes that have sufficient power to defeat the k monsters. Now, look at the maximum endurance of that suffix which we already calculated. If this endurance is at least k then we can kill k monsters. So you can check for each k whether we can kill k monsters or not in log(N) time.

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

no systest?

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

Help needed in Problem E

My approach is getting WA on test case 6 and I don't know why. Please can someone tell me why it is coming wrong.

My Approach :

I will try to make all possible prefixes for A(first person) i.e. (from 0 to N) where N = k1+k2+k3. I have maintained a set of elements for all three of them. Now suppose prefix of A is "i", so I will remove all the elements less than equal "i" in the set of first, second and third person and for it, I am maintaining the count in a variable name "taken". Now the problem is to solve for B(second person) and C(third person), and this will be equal to the minimum of the count of (elements in C which smaller than the largest element in B) and (elements in B which bigger than the smallest element in C) this can be done using BIT(In which I delete the elements according to the prefix). Note that I don't have to give the remaining elements of A to B and C first and do the computation as we can assume that A was given to them in the correct order.

So the final answer for the prefix "i" = taken + "remaining element in A(as he has to give it to other)" + min(element B give to C, element C give to B). And the minimum of all the prefixes will be our answer.

My Submission

Thanks in advance!!!

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

    Hi, check this case:

    10 10 10
    10 29 14 28 18 9 20 7 23 22
    30 19 2 25 12 17 8 15 11 21
    6 13 5 1 4 16 3 24 26 27
    

    The answer should be 18. Hope it helps.

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

E can be solved using dp.But some people solved it by binary search,how to solve it using binarysearch?

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

E can be solved using dp.But some people solved it using binarysearch,how to solve it using binarysearch?

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

    And also How to solve using segment tree because I have seen some has done by segmeent tree

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

    using dp mean using LIS or something else?

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

      dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.

      dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.

      the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].

      if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit.

      int id[200005], dp[200005][4];
      
      int main() {
          int A, B, C;
          scanf("%d%d%d", &A, &B, &C);
          for(int i = 1, ai; i <= A; ++i) {
              scanf("%d", &ai);
              id[ai] = 1;
          }
          for(int i = 1, bi; i <= B; ++i) {
              scanf("%d", &bi);
              id[bi] = 2;
          }
          for(int i = 1, ci; i <= C; ++i) {
              scanf("%d", &ci);
              id[ci] = 3;
          }
      
          int n = A + B + C;
          for(int i = 1; i <= n; ++i) {
              if(id[i] == 1) {
                  dp[i][1] = dp[i - 1][1];
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else if(id[i] == 2) {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3]));
              }
          }
      
          printf("%d\n", min(dp[n][1], min(dp[n][2], dp[n][3])));
          return 0;
      }
      
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you plz explain the transitions?

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

          dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);

          cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j).

          dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.

          dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.

          It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.

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

Can anyone confirm whether my approach for D is correct.
Sort the soldiers with inc power. For every ith monster, do B.S and find the soldier whose power >= power of monster, let be at index idx, then I will choose the soldier with maximum strength from index idx to n (as all soldiers after idx have greater power than idx). Let's call this soldier as 'X'.
I will kill as much monsters with this soldier as I can. Now two case arise-
1. Number of monster killed by x becomes equal to its strength, i.e., x.killed == x.strength
2. It's power is less than current monster.

For the first case I will increase the count of day and again iterate as done in first step.
For the second case, I will B.S and find the soldier whose power >= power of monster, and has the most strength(among those having power greater than the monster), let's denote it by 'Y'.
Now 2 conditions arise,
1. x.killed < y.strength For this case I can safely say that instead of chosing X in the first place I could have chosen Y and killed more monsters than X, so I update my current soldier from X to Y (as X.power=Y.power, X.strength=Y.strength).
2. x.killed>=y.strength. For this case I increase count of day , udate my X and iterate forward(X.power=Y.power , X.strength=Y.strength, X.killed=1).
I am getting WA for 2nd test case.
Here is my solution : 64836864

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

The color of the name seems to be wrong

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

Does anybody have a $$$O(n)$$$ approach to solve D?

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

    I don't think an O(n) solution is possible for this problem. O(nlogn) is needed at least.

    UPD: oh there is a clever O(n) solution. watch roll_no_1 's comment.

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

    You are also Chinese, so you can see this.

    https://www.cnblogs.com/KisekiPurin2019/p/11854682.html

    You can use dp to get the highest power of heroes which has at least i endurance.

            scanf("%d", &m);
            for(int i = 1, pi, si; i <= m; ++i) {
                scanf("%d%d", &pi, &si);
                p[si] = max(p[si], pi);
            }
    
            for(int i = n - 1; i >= 1; --i)
                p[i] = max(p[i], p[i + 1]);
    

    p[i] is the highest power which can beat i monsters in just one day.

    and then you can use greedy, each day try to move as more as possible.

            int i = 0, j = 0, rmq = -1, ans = 1;
            while(j < n) {
                ++j;
                rmq = max(rmq, a[j]);
                if(p[j - i] < rmq) {
                    if(rmq > p[1]) {
                        ans = -1;
                        break;
                    } else {
                        i = j - 1;
                        ++ans;
                        rmq = a[j];
                    }
                }
            }
    

    It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.

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

Does anyone know about this anomaly

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

Мой рейтинг 1200+ но я все еще новичок

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

What was the approach for D apart from Segment Trees/Sparse Table ?

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

    Sort by endurance and find for every endurance suffix maximum instead of using segment tree, and just compare maximum of monsters with this suffix maximum

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

    you sort array of pairs <endurance, power>. Then you try to kill in one day as much as possible so you iterate through $$$a_i$$$, count the number of monsters you want to kill this day as $$$cnt$$$ and memorise the most powerful monster this day as $$$max\text{_}pow$$$. You go further and further until there is a hero with $$$s_j \ge cnt$$$ (it can be checked by $$$lower\text{_}bound$$$) and a hero with $$$p_j \ge max\text{_}pow$$$. To check the last condition you can look at max hero power on suffix $$$[j..m - 1]$$$ and you can do it in $$$O(1)$$$ by precalcing an array $$$max\text{_}suf$$$ where $$$max\text{_}suf_i$$$ is the maximum power of hero in suffix $$$[i..m - 1]$$$ in sorted array

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

    Why don't you read above there have been atleast 10 comments about D solution !!!

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

My Screencast for this round.

https://www.youtube.com/watch?v=g5n6eW7uwVY

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

Jesus! Where is the solution(

ok. i just want to know how to solve problem G

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

 UMMMMMM!!! OK XDD

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

I have a question about the problem D. In this question,a special example

Input:

1

5

1 2 3 4 5

3

1 10

2 10

5 1

for this example,the right answer should be 4,not 5.And I found that a lot of the output through the AC code was 5.Why?

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

Can anyone explain solution of F briefly? TIA

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

Editorial?

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

When will the editorial of the problems be posted?

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

How about editorials???

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

https://imgur.com/a/qKs0K8I Почему новое звание новичок, а не ученик?

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

Color display still not fixed ?

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

I can't see my friends standing of this contest. (It's not for sign in problem)

Let me know if I only facing this problem...

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

Why Difficulty of this round in Problemset is None

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Please also include pwild as the 5th place winner, we had the same penalty.

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

    Whoops, sure. Funny enough my script got pwild into the rus version of the table and you in the eng one :D

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

      I was wondering why I got a message saying I was mentioned in some topic, but then not actually finding my name in the text.