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

Автор Vladik, 4 года назад, По-русски

epam

Привет, Codeforces!

Рад анонсировать и пригласить вас на Codeforces Round 689 (Div. 2, based on Zed Code Competition), который пройдет 11.12.2020 17:35 (Московское время).

Мы хотим предложить вам для решения 6 задач взятых с Zed Code Competition 2020, который проводился в рамках конференции Adapt by Zed компанией EPAM Systems.

Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100.

Всем выше перечисленным огромное спасибо за вклад, внесенный в подготовку раунда, а вам удачи на предстоящем соревновании! :)

UPD: Разбалловка для задач: 500 — 1000 — 1250 — 1500 — 2250 — 2750.

Поздравляю победителей официального зачета:

  1. yash_daga
  2. AiriKatagiri
  3. tejas10p
  4. RNG-Ming
  5. meidong

а также победителей неофициального:

  1. neal
  2. Geothermal
  3. LayCurse
  4. emthrm
  5. hank55663

Спасибо всем за то что приняли участие. Желаю приятного дорешивания! (разбор)

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

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

As a tester, 1 in 7 children does not have enough food to lead a happy and active life, but what does it take to end global hunger? Participate in Codeforces Round #689.

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

As a tester, I love Zebras!

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

I think it will be a good contest!

Good luck to everyone!

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

As a tester, wishing you all Happy Rating :)

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

BRCode Will there be 3b1b styled tutorials xD?! Im aware it must be really hard to make but they're really great BTW don't stop making them.

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

    Hi, sorry I was just testing this round — there won't be any video editorials for it.

    However I am making video editorials for a contest later this month, so look out for that :p

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

[copyright striked by Digon]

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

I will be glad to participate and test my knowledge

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

The unseen bug is the deadliest

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

Good luck everyone ❤️

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

As a tester, I want to wish you good luck and high rating!

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

    Unfortunately, I don't see your name in the testers list

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

      Unfortunately, I don't know what were you looking at :)

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

        Unfortunately, then there are four possibilities
        1.You're from a different world line and you haven't tested this round in this world line (according to the announcement at least)
        2.Your name hasn't been added to the list given in the announcement but you tested this round
        3.You never tested this round
        4.You are an alt account of one of the testers and mistakenly commented from the wrong account :P.
        Screenshot-2020-12-11-023006

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

I suspect there's a problem that will require Z-algorithm. ;)

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

    If there is I am going to troll them by solving it with KMP.

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

    Now even if they planned to have such problem, they will replace it with another problem because of this comment!!!

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

      It is five hours left. Are you sure they can replace a task in this time?

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

        I think they should, but if above is true then it will be either a D or E problem and replacing that would be little difficult. I still think its doable since there are too many questions and rounds already in queue, they can use a similar difficulty problem from future round.

        PS: After all this comment, if we still see a question on string pattern matching it can help few candidates to gain rating.

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

          Oh, man, change a task for that reason?

          Well, authors, change all the tasks please! I think there will be tasks for 2-sat, binary search, bitmasks, bruteforce, chinese remainder theorem, combinatorics, constructive algorithms, data structures, dfs and similar, divide and conquer, dp, dsu, expression parsing, fft, flows, games, geometry, graph matchings, graphs, greedy, hashing, implementation, interactive, math, matrices, meet-in-the-middle, number theory, probabilities, schedules, shortest paths, sortings, strings suffix structures, strings, ternary search, trees and two pointers.

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

            Lol, Do you really think writing all the data structures is equivalent to the first comment?

            Let say we actually have a D problem on Z-algorithm in this contest, then you don't think people seeing a substring and string pattern question will first try to relate it to Z-algorithm?

            Okay if you disagree with all of my above comment, then why contestants are not allowed to comment even on data structure used in a problem during contest?? I must say sometimes knowing which data structure to use makes problem much easier to solve.

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

              Main phrase is "during the contest". This statement about Z-function is useless, because participants don't know the tasks and all their guesses are just random.

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

      Chill dude. Why so serious?

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

    What is Z-algorithm?

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

As a tester the problems were very interesting :)

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

    Were the problem statements short, sir?

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

      Why everybody wants to see short statements? It is not so difficult to read legends, if they are not very long, of course.

      As an author of 672 round I would like to say that some authors love interesting legends in their statements. It is such a pleasure to make tasks about your favourite films, or games, or even about your friends.

      Of course, I can understand participants. Rounds require speed. But to my mind, one or two minutes spent on the legends are not impotant.

      Please don't downvote me for the unpopular opinion.

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

        Sorry. I want to see short statements because I want to see the beauty in the problems instantly. And by beauty I mean algorithmic and mathematical beauty. I don't care about the story, and even while upsolving, I become very happy to see a problem which has a short formal description but very hard to think. Most recently: 986C - AND Graph, I bookmarked this problem even after solving it, I was so happy.

        Also, my dad peeks into my laptop from time to time, and if he sees me solving a problem related to zebras and cookies and Gildong the dog, he will question my career choices. That is why I always switch to some AtCoder problem (without flavour text) when he is around. :P

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

          How do long statements relate to "algorithmic and mathematical beauty"? Legend is only a story around the mathematical construction.

          If you don't like stories, you can just skip it and get the formalistic statements.

          "I become very happy to see a problem which has a short formal description but very hard to think." I agree with you, of course, beautiful tasks are very nice. But why this task can suddenly become worse if there was a legend? The task remains the same, the solution remains the same.

          If it is just aesthetic love to short statements... well, maybe. But I still don't understand it.

          And yes, your situation with your dad is interesting, but I don't really think that this could be a real argument for other people.

          However, I appreciate your opinion. "So many men, so many minds".

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

          I don't care about the story

          This might change your mind.

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

            I'm sorry, what's wrong with this task?

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

              I think the story is very well connected to the problem which makes it interesting.

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

                Oh, I thought that you were against this task.

                Now, I agree with you, this is a beautiful legend that fits the task pretty well. Nice example :)

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

          "Gildong the dog"

          Since when Gildong was a dog?

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

        But some people like me are bad at English and have to use the Google Translate to read the problems,and long statements are difficult for them to understand >_<

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

          There was a really great round 635, where statements have legends, followed by a picture. All that lies above picture is a legend, all that lies below — a statement.

          This trick solves your problems with English.

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

            Thanks for that.
            But actually,**few** CF problems with long statements has a short formal description below the legends.
            I strongly suggested that if the author want to make the statement long,at least he need to add a short formal description.
            Besides,the long statement may has some confusing words that may lead some competitors with bad ability of understanding(like me) understand the problem in a wrong way,and wastes a lot of time.

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

              No, I disagree. If I will have a legend and a task apart, it will look like "listen, I have a legend, but nobody cares about it so here is a formal description".

              Real life tasks most commonly don't have formal statements.

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

          What's worse,when we copy the statements to the Google Translate,the Markdown and the $$$\LaTeX$$$ would be lost.

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

        I think one issue is some legends don't really add anything to the problem. Legends like having a city connected by roads being described by a graph or two playing a game and determining the winner if both players play optimally seem natural. Legends like someone receiving and array for their birthday and having to calculate some property of it seem a little contrived. Then there are those legends where person A proposes a problem to person B and person B can't solve it for reasons like not having enough time, being too young or being too small and now they ask you to solve it for them. There's also the other situation where person B can solve it and they want to know if you can solve it too. Some of these can be entertaining but also feel a little unnecessary.

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

          I'm strongly agree with you! Legends like "birthday" or "B can't solve" or "can you solve it too" are so annoying! Honestly, I... well... At least I don't like this types of legends (i don't like it very, very much).

          However, I was talking about good legends, without this typical words about birthdays or "A wants to solve but can't".

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

          How did you know that mike recieved an array for his birthday lol.

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

What is the problem score distribution?

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

I hope Vladik will put me on the tester's list. ⊙︿⊙

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

Wow netman, was once an IGM. I thought Vladik was the highest rated at first. Looking forward to some really good math problems.

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

I'm trying but not getting better. I hope I will do well in today's contest.

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

score distribution ?

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

What is the score distribution of problems ?

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

bad contest.

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

And now I want to ask you: were the problems' statements short enough? :)

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

Anyone else found B to be a mere implementation exercise? It took me almost 2 hours, mostly because I kept telling myself that Codeforces either wants a "smart solution" or a super dumb solution. C looked cool, though.

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

I hate Probability

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

Great contest! I thought I had registered but apparently, I did not, that cost me 10 minutes of the contest and my mistake ended in an emotional downturn the rest of the time :(

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

I hate Probability.

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

How to solve C ?

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

    Find such maximal position X that for all i > X it is true that a[i] = i.

    Then just calculate the answer with a well-known formula:

    ans = 1

    if (r[i] >= X) ans = ans * (1 — p[i])

    Answer is 1 — ans.

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

    Here is how I thought about it : First we find the first index such that the suffix of the array is sorted. Now inorder to make the array not sorted after m operations, the elements at index = (first_index-1 to n) should not be sorted. Then just do 1-x as we have to find winning probability. Idk why it fails on pretest 2.

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

    Well first find the length of the largest suffix of a that is sorted in ascending. Say it has length len. Then let x = n-len. Clearly, if any operation (r, p) has r >= x, the whole array is sorted. Lets say we have opi1, opi2, ... opik where 1 <= i1 < i2 < ... < ik <= m, such that the previous condition is satisfied. picking any combination of these operations to go through to sort the corresponding prefix of array a will suffice to sort the whole of array a. Also an interesting thing is the probability of this occuring is exactly 1 minus the probability of the complement, that is, none of these operations going through. None of the other operations opi matter if it doesn't belong to the previously said list. Now the probability of this compliment, is just the product of (1-pi1)(1-pi2)...(1-pik). As I already said, ans is 1 minust that. One corner case is if array is sorted to begin with, in which case the answer is just 1.0. (As ops don't affect array)

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

      I did the same thing, I was a bit confused about the corner case first. So here's a thought : If some prefix of the array is already sorted given that (prefix_index>first_index where suffix is sorted) then we should not count it in finding the winning probability as no matter we include it or not the array will always remain sorted! This logic handles the corner case well and also makes more sense. However we count it's contribution to the final answer, why is that?

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

        Because in the given corner, if we use the same algo logic, we'll be ignoring the case where, even if all those ops with r >= x don't go through, the array remains sorted. Which means, the product that we subtract from 1 normally, isn't valid in this case. That's literally the only difference between the ans of the algo and the way we handle the algo.

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

Could not understand question C. Can anyone help?

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

    Note that once the array is sorted it never gets unsorted, by definition of the problem.

    Then, if a postfix of len x is sorted, the array can get sorted in each experiment if $$$r[i]+x>=n$$$

    In this case it stays unsorted with prob $$$1-p[i]$$$

    So we need to multiply all these numbers to get the probabilty that the array is still unsorted after last experiment. Then ans equals 1-prop.

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

    Give you a permutation.

    Then give you $$$m$$$ operations like $$$(r_{i},p_{i})$$$. It means in this operation, It has $$$p_{i}$$$ probability to let the first $$$r_{i}$$$ numbers in the permutaion be sorted.

    You task is to find the possibility of permutations to be sorted.

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

Nice problemset

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

What may be

  • test 2 of problem C
  • test 13 of problem E

?

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

Can anyone pls explain the solution of problem B...? :(

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

    Since you can easily get the solution later. Here's a hint, try searching for problem "Maximal square in a rectangular matrix having 1" and try to use the same approach. I used same.

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

How to solve E?

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

    My solution breaks it into two cases, although maybe someone else can provide a more concise solution.

    I won't detail the exact formulas, but you can see them in my submission.

    Case 1: $$$x \geq y$$$

    The overall value of $$$k$$$ diminishes over time, so we should greedily add $$$y$$$ whenever possible to prolong the time the cooler amount stays above $$$l$$$. Initially, for some number of days, we won't be able to add $$$y$$$ without overflowing past $$$r$$$, so our cooler amount decreases by $$$x$$$ for each of those days. After a certain point, we will always be able to add $$$y$$$ without overflowing, so our cooler amount decreases by $$$x - y$$$ for the remaining days. We can calculate all this information in $$$\mathcal O(1)$$$ with some math.

    Case 2: $$$x < y$$$

    Because $$$y$$$ is greater, we can always first let the cooler drain at a rate of $$$x$$$ for as many days as possible, before adding $$$y$$$, then repeating. This is optimal since we're only refilling when absolutely necessary, so we don't risk overflowing $$$r$$$. There might be an $$$\mathcal O(1)$$$ math formula for this, but I'm not sure. I did $$$\mathcal O(x)$$$: whenever we add $$$y$$$, it's because we can no longer drain any more $$$x$$$, so $$$0 \leq k - l < x$$$. We can thus treat this as a graph that cycles through nodes $$$0 \dots x - 1$$$, and if we ever encounter a cycle, we know that going through this cycle will sustain the cooler capacity for the entire $$$t$$$ days.

    I know that wasn't the clearest explanation (I found it a bit difficult to put into words), but hopefully the code can clear up any doubts. https://codeforces.net/contest/1461/submission/100945988

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

These error involing precision always frighten me. Solved D,E but could not C even after many attempts. Can anyone help what is wrong with my code? https://codeforces.net/contest/1461/submission/100926909

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

how to solve E??? Can't even know how to approach...

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

I was implementing an inclusion-exclusion for c but kept getting tle on pretest 10.

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

    Inclusion-Exclusion is O(2^n). For example,

    | A U B U C| = |A| + |B| + |C| — |A ∩ B| — |B ∩ C| — |C ∩ A| + |A ∩ B ∩ C|

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

    Inclusion exclusion wasn't needed. 1-p would be the product of individual (1-pi's) provided the part after position ri is sorted From that p can be computed

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

    I have used inclusion-exclusion as well. But I have used dp for calculating it.

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

Is it just me or was C too easy? B felt harder to implement.

My approach for C, If you know array after idx is sorted, then any operation that operates on idx or above will completely sort the array. So probability of atleast one such operation = 1 — probability no such operations happen.

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

I think D is well-known. upd: Divide and Conquer DP

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

What was the logic for problem B

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

    Just implementation (you can use prefix sums as well).

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

      How to do it using the prefix sum?

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

        Well... Just as said: you bruteforce the peak of the tree (the highest *), then just check if there are all elements are * on the lower layers (prefix sums can done it O(1), which is fast). So, in total we have O(N^2*M).

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

    Let's define dp[i][j] as a number of spruces where (i, j) is the top. Now you can calculate dp table iterating from bottom to the top in the following way:

    if s[i][j] == '*':
        dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1
    else:
        dp[i][j] = 0 
    

    The answer to the problem will be the sum of all values in the dp table.

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

      Intersting solution... Do you have a proof for it?

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

        I would like to think of this as: dp[i][j] is the maximum height of the spruce where (i, j) is the top, instead of the number of spruces.

        It's obvious that, looking at (i, j) alone, if the maximum height is dp[i][j], there are dp[i][j] possible spruces starting from (i, j).

        Now, to have the tree with height dp[i][j], you need the next layer, which are dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1], to have the same height of dp[i][j] - 1. That's why you take the minimum of them, and add 1.

        I'm not sure if this helps, but this is my perspective on the solution.

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

        This picture is not to scale but can help. Assume there are cells bellow as well.

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

      Amazing solution with better time complexity

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

Could someone tell why my problem C code was giving TLE .

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

Am I the only one who wasted 30 minutes on C and then realizing that I took forced the solution to the next test-case without reading the queries for that problem
PS: spookywooky can relate :(

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

How to optimize B ?

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

Some one please debug my code for Q4 100952421

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

    Just a small hint: to prevent bugs in binary search you can try to use lower_bound() and upper_bound()

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

    My code was failing too in pretest 7. For me, it was an integer overflow problem and changing int to long long int fixed the code.

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

Is there any other way than dp for B?

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

    B is not dp

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

      B is in my opinion a spin off of a classic dp problem Maximal square If you this problem, I guess coming up with dp solution would be much more easy

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

    i know a way using manacher algorithm and two pointer in $$$O(n*m)$$$ worst case

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

      Could you tell me about it please?

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

        here ,
        Basically i calculate horizontal radius for each cell, using manacher algorithm for each row, by putting $$$ * $$$ to $$$ 1 $$$ and rest all $$$ . $$$ to different values >1 , and then i applied column-wise two pointer, so we could get in n * m time.

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

    I used a simple algorithm for B

    Basically, build it from the bottom (after checking for valid indices, etc.) :

    tree[i][j] = min({tree[i + 1][j - 1], tree[i + 1][j], tree[i + 1][j + 1]});
    

    Reference

    Edit: Perhaps that qualifies as DP (not sure)

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

Very nice problemset!!! XD

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

    Nah that problem D was 50x more cancer than this problem B :P. On this problem B they were generous enough to let you bash.

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

How to solve D ?

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

    I believe segment tree should do it, just sort the array beforehand. For some reason I could not get the second test in the given pretest right, so I didn't submit. But still it seems relatively simple. Correct me if I'm wrong.

    The method I thought of is instead of getting the traditional tm = (tl + tr) / 2, we use binary search to find the first index greater than our mid element.

    And finally, you insert the sum from tree[v] into some set. In the end for each query if you can find it in the set it's possible, otherwise not.

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

    Just a simple "merge sort"-like recursion will do it all.

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

      I thought that only , but if we divide the array into two parts , and sum of both left and right is greater than sum required then we have to check in both half . So wouldn't that take O(n) per query ?

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

        You need to precompute all the possible sums using divide and conquer. Then ,for each query, you just need to check if the required value exists or not (using a Map,for example).

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

          Is'nt there a possiblity of exceeding memory limit in case the size of map or set becomes very big?

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

            The maximum number of sums that we can get should be in the order of $$$O(n)$$$ i think.

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

            It can be proved by induction that the number of all possible answers won't exceed n.

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

        Just calculate sum of both left and right array and store it in set. After this call for next two halves... You can traverse the array for sum calculation or use prefix sum also..

        Then for each query check the no. in set and print accordingly...

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

        We devide the array in all possible subarrays, and store the sum for each one somewhere.

        Then while queries we can "directly" give the answer in log n.

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

        No, actually it is much faster than it looks like.

        It is easy to see that the maximum depth of recursion is $$$log(n)$$$ because each time we are splitting the array into two halves.

        In each level we are doing at most $$$n$$$ operations, by summing up each part of the array.

        So that's a total time complexity of $$$O(n*log(n))$$$.

        Bonus: we can actually do the summing part much faster by calculating the sum of the desired interval from the sums of its two halves, so that's $$$O(n)$$$ time for the whole recursion instead of $$$O(n*log(n))$$$, but the total time complexity will remain $$$O(n*log(n))$$$ because of the sorting we are doing at the beginning.

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

        you can precompute all the possible answers in nlog(n) , then you can answer each query in O(1) time . giving a total complexity of O(nlog(n) + q)

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

    Do exactly what the question says. I literally had a vector in a queue and pushed left vector and right vector into the queue and continued doing so until vector size is 1.

    Basically I calculated all sums possible from a given vector, the complexity would only be O(nlogn)

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

Does N*M*M/2 pass in B?

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

B is harder than C and D, imho

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

I solved A in 2 min and then struggled with B for the rest of the competition, can somebody tell me CLEARLY how to solve B ? (I know it is just implementation, but how ?)

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

The values of r may not be necessarily distinct in problem C (:

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

    So which value should we consider?

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

      what I meant to say was that you cannot store all of the values and then compute the answer, because at some point you might overwrite the previous values if the same value of r comes more than once in the given operations.

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

How to implement solution of B?

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

    you can refer mine 100926055.

    dp[i][j] in my solution denotes largest length of spruce that can be made from the coordinate (i,j).

    Hope it helps!

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

    we will use DP! lets call maximum possible k for a tree rooted at (i, j), mem[i][j].

    lets call c[i][j] the minimum number of consecutive *'s from left of the cell or from right of it (including the cell). this can be found using partial (prefix) sum and binary search in O(log(N)).

    Then the maximum possible k for the cell bellow (i, j) ((i+1, j)), is min(c[i+1][j], mem[i][j]+1), because:

    1. mem[i][j] needs to be at least k-1 for mem[i][j] to be k.
    2. a k tree has 2k + 1 *'s at the base.

    Then the answer is just sum of all the mem[i][j]s.

    Submission using this principle.

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

The system test for E is weak. I hack someone with the following test after the system test: 31 2 48 27 3 2

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

Interesting problemset!

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

weak pretests :/

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

what sould be the time complexity for problem B? will N^3 solution will pass??

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

    n^3 will pass

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

      but it will be 500*500*500 == 125000000 can we ... how is it ok ? its little less than 10^9

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

        If the constant factor is low, it'll pass. for 1 sec the number of operations is generally around 4*1e8 from what i know. My n^3 passed with 234 ms

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

        there is a lot of cases that the solution will break in the third loop ex: in the worst case the third loop in row 1 will iterate m/2 in the next row it will iterate m/2 -1 and so on and if in any case, you can't make the current spruce tree you will break so this will make the time is much less

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

    in most contests,
    - O(n^3) for n <= 500,
    - O(n^2) for n <= 3000,
    - O(n) for n <= 200000,
    - O(nlogn) for n <= 1000000
    will pass.

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

I am getting WA on test case 20 in problem C (I think it is about precision). Can someone help?

My submission

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

I liked the pictures in the questions, but for QB, adding a pragma after comp ends up ACing.WHY!!!!??? :(

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

Can someone please point out what is wrong in my solution for problem C. It got fst on testc-case 25

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

    float has very limited precision.

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

      damn! I thought I was working with long doubles all this time, why in the world did I write#define ld floatafter writing #define ld long double :((((. I am the dumbest person who ever existed on this planet.

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

I may have found F interesting, only if s was always "+*".

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

Why does C fail if we use float instead of double? 100933790

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

what is the limit of memory that can be allocated on runtime in C++?

my solution for B failed system test because i was allocating (3*500*500) at worst.

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

what is limit for memory allocation in C++ during runtime?

my solution for B failed system test because i was allocating (3*500*500) memory at runtime in worst case scenario.

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

I haven't solved E but I know a TestCase where 1 solution fails I know I can't hack it but is there a way to hack now for somebody else or it isn't possible after system testing.

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

100962567 In spite of using 3 loops(O(N*N*M)) in B, my code gave Time Limit Exceeded on main test case 4.

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

I think the B is bad. I spent 15 minutes thinking about how to improve my $$$O(500^{3})$$$ brute-force because 1e8 is dangerous. However, in fact $$$O(500^{3})$$$ can pass it easily. So, what's the meaning of the B? Just for testing Brute-force?
If so,that is obviously unresonable.

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

Problems B and D were about justifying to yourself why brute force should work :P

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

x

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

List of ideas that solve F: 100956230

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

    Thank you, I got all these ideas except the last one with dp, now I know what I missed.

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

    That's it!

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

Thank you very much, I managed to get back to green after almost a year!

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

For problem D, I used the following solution: 1. sort a. 2. compute prefix sum of a for efficient range sum operations 3. for a given sum s, call the helper method check on the entire range of a.

In this helper method check, do exactly what a split operation allows us to do: 1. split by middle value midV; 2. do a binary search to find the right most index midIdx such that a[midIdx] <= midV. 3. then check the range sum of [l, midIdx], [midxIdx + 1, r]. If one of them equals sum, return true; if both of them are smaller than sum, return false; if they are bigger than sum, recursively check on that range.

The terminating condition of this check method is: 1. l > r, left index is bigger than right index; 2. the range sum of the current range is < sum; 3. the range sum of the current range is > sum, a[l] == a[r], meaning we can not split anymore. 4. if the range sum is sum, simply return true.

My submission is 100978064

I keep getting the stack overflow error on one of the recursive call but I can't figure out why my terminating condition is incorrect. Can some one help me with this? Thanks!

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

I made a stupid mistake. In the c problem, when the array was originally ordered, I directly continued, ignoring the following input. I submitted this question for the first time at 00:51 and passed it in the last ten seconds. It is because of this stupid mistake. So I have an idea, can someone sum up some common stupid mistakes and share them so that when the solution fails to pass, we can first check whether they have made these stupid mistakes (if no one does this, maybe I will Do it).

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

Finally master! Thanks for very interesting problems and i got a little distance from winners!

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

I recieved a system message about my submission for Problem D coincides with other's submission. But I always use the same FastIO module which can be proved by my previous submission. I don't understand why it's considered a violation of the rules this time