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

Привет, Codeforces!

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

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

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

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

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

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

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

Место Участник Задач решено Штраф
1 dlalswp25 6 205
2 Ormlis 6 207
3 Tlatoani 6 214
4 yokozuna57 6 232
5 peti1234 6 235

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

Место Участник Число взломов
1 racsosabe 80:-17
2 Elo 33:-4
3 peti1234 24
4 AsunderSquall 26:-7
5 xiaofan7 25:-10
Было сделано 605 успешных и 888 неудачных взломов.

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

Задача Участник Штраф
A Geothermal 0:01
B SSRS_ 0:04
C Valera_Grinenko 0:02
D SSRS_ 0:10
E Akulyat 0:38
F Suiseiseki 0:58
G rainboy 0:42

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

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

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

Deleted

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

    Hey I want to know why you got downvoted... You were just wishing everyone good luck. Am I missing something? I feel bad for you :(

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

      Anything that's obvious, repeated and doesn't adds value and just adds an extra comment for the sake of it and just increases the time to read the comment thread gets downvoted mostly, and sometimes people do it just for fun as well to channel their frustration of a bad contest or something. I have a feeling this will be downvoted too, but that's all there's to it, the explanation you were looking for.

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

    Don't worry we will upvote you eventually. Love from Sweden!

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

I have a feeling this is going to be a good one.

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

road to cyan

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

there is almost 10 days difference between the techno cup round and the next div 2 round .... plz if we can have some contest in between??

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

I wish I would do better in this contest. Hopefully ,I will do it.

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

Is it rated?

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

As a Monogon give me contribution

Edit: I'm getting scammed, rip

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

Again an educational round without any tester? What if we observe any issue with test case/problem explanation later during the contest? We still have around 19hrs, I guess we can have some testers and there feedback?

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

    Why is he downvoted? He raises a fair point I think?

    (Edit: his comment was downvoted when I wrote my comment)

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

      Exactly, I was just talking about one of the possibility based on past educational round. Lets hope we see a healthy round today.

      I don't think there would be any harm in having few testers, there are many yellow/red participants who participates in educational round, for them round will already be unrated. So we can maybe ask for volunteers? Even many rated participants would be ready to volunteer.

      awoo what do you think? This will just decrease the chances of any actual issues in the problemset.

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

      Seriously, why does it take a red's agreement to give this person the upvotes he deserves.

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

    +1 from my side.. We already witnessed(Round 682) what happens when something unorganised goes from tester's side. And this one is without them wholly.. Fingers crossed

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

i hope i can be a CM trough this contest ,at least rise some ratings

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

Chasing CM dream...
Wish I would not lose my ratings.

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

Last two contest was horrible. Finger crossed this time

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

I just want to make my contribution to 0 from negative.

I know I may add more negative contributing from this comment but still I want to give it a try.

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

Please make my contribution from -1 to 0.

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

upvote and down vote should be logically. First time i comment and I just expressed my feelings, but why am i getting down vote? It makes me frustrated. But i realized, upvote and down vote means contribution for codeforces. Please, make me 0 contribution from negative.

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

Hey guys ,do check https://gameofcodes.herokuapp.com (Okay, I know its a promotion, but the whole site is for codeforces lovers, so I guess its okay)

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

    Why So downvotes? I think dude has made a cool website, though it loads a bit late. But I think the UI is just awesome.

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

      Glad you like it. Don't worry about the downvotes... it just motivates me to make it much cooler and make it more user friendly.

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

[Deleted]

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

All the best Goiss !!! Just making my contribution >=0 from negative.

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

how to make friends on codeforces?i have 0:(

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

    u can click star but that will make the user your friend.it will not increase your count of friends.for that somebody needs to click on the star of your profile

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

This comment section is a bit weird...

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

Hope petya, vasya, or their friends aren't too confused.

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

Highly unbalanced round :(

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

Definitely losing lots of rating, can I get some contribution upvotes? :((

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

B and D should interchange their position :)

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

    D is a stupid problem.

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

      The contest is still going on man! Calm down

      These remarks just give away hints

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

        maybe you are right, but i don't think calling a problem stupid gives any kind of hint.

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

          Anyone who solved B but couldn't solve D would become biased after reading this, don't you think so?

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

            no, i don't think so. But i will make sure not to make such comment during ongoing contest.

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

            yaa I solved B but couldn't solve D I should have read above comment

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

    Whats the trick to B? Solved A, C, D still couldnt figure out B.

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

problem E is very hard. and I think they should have switched places of problem c and b. D is a very interesting problem. Good luck everyone!

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

C < A < D < B

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

Something seems wrong with the official scoreboard, it is also showing for users having rating >= 2100.

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

You should've switched the C to B, D to C and B to D. Time penalties just killed my contest. And there comes very tough E so I can't even come back

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

    Maybe C with B should have been swapped, yes. But B with D? Are you serious?

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

      For me, formula for B wasn't that straightforward. And I also needed construction to get the idea is correct

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

      D seemed pretty standard. I still don't know how to solve B lol

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

    The order was the same for everyone, so you have only yourself to blame for your poor strategy choices.

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

This round is pure destruction.

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

What is C ? Trollforces ? I want to ask authors that why would they think this problem to be worthy at a position for D2C

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

    We estimate the difficulty of ER C as Div2B, not Div2C. Do you think that this problem is easier than Div2B?

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

      Oh ok .. I never knew such a thing also existed. Also I liked the problem D. Thanks for the round once again.

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

How to solve D ?? Can anyone explain the answer for the first test case ? .. i even failed to understand the test case with 1 hours . poor me :(

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

    nth fibonacci * inverse(2^n). You can try brute force by recursion on some small numbers and check the pattern. The question is how many ways are there of choosing (only)odd numbers so that there sum is perfectly n.

    When n=2
    1 1
    
    When n=3
    1 1 1
    3
    
    When n=5
    1 1 1 1 1
    1 1 3
    3 1 1
    1 3 1
    5
    

    These are the ways of arranging radio towers on different n.

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

    The main idea is that lets say you want to cover the region of n blocks, then what you can do is take the 1 position and make the tower to have 1 power, take 3 position and put tower in the middle with power 2, take 5 position and and put tower in the middle with power 3, and so on.

    So for a state with n position we get a nice recusive relation

    f(n) = f(n - 1) + f(n - 3) + f(n - 5) .....
    

    In the end since we are required to print the probability which is equal to f(n) / 2 ^ n where 2 ^ n are all possible configurations and f(n) are valid configurations. Also remember this all happens under mod

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

Whoever made problem D, I love you. Fibonacci sequence popped out of nowhere. Could someone please share a solution to F?

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

:(( i solve problem B in 1:52 but i can solve ít on 1:20. i gave up for 30 mins :((

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

Me:

  • Didn't solve B
  • Solved D in 70 seconds (And yes, I mean it, that's from scrolling to "Problem D" to getting Accepted)

"That's what we call a balanced problemset"

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

Nice DIv3 till D and DIv1 after D . If I am not wrong it seems (Div1 +DIv3)/2===> DIv2.

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

the gap between D and E is huge man

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

Solution for problem D: The probability of choosing any $$$a_1,a_2,\dots ,a_k$$$ is the same for all, $$$\frac{1}{2^n}$$$ as we have to chose those and not chose the others, so we just want to find the number of subsets of $$$1,2,3,\dots ,n$$$ that work.

Let's call this number of good sequences $$$a_n$$$. Notice that if $$$i$$$ is the smallest element that was chosen then it needs to cover $$$1$$$ while not hitting $$$0$$$ so the radius is exactly $$$i-1$$$. Therefore it covers $$$[1,2i-1]$$$ and we have to cover $$$[2i,n]$$$ without hitting $$$2i-1,n+1$$$. This is the exact same problem with $$$n-2i+1$$$ elements. Therefore, we have:

$$$a_n = a_{n-1}+a_{n-3}+a_{n-5}+\dots $$$

We can see that $a_0 = 1$ and $$$a_1 = 1$$$. So using this recursion we calculate $$$a_2 = a_1 = 1$$$, $$$a_3 = a_2+a_0 = 2$$$, $$$a_4 = a_3+a_1 = 3$$$ and $$$a_5 = a_4+a_2+a_0 = 5$$$. At this point we realize this is the Fibonacci sequence, and we can prove it with strong induction. $$$a_{2n-1} = a_{2n-2}+\dots + a_2+a_0 = F_{2n-2}+\dots + F_{2}+F_{0}$$$ from the hypothesis $$$F_{2n-3} = F_{2n-2}+\dots F_{2}+F_0$$$ so the above is just $$$a_{2n-1} = F_{2n-2}+F_{2n-3} = F_{2n-1}$$$. The even case is similar.

Therefore the answer is just $$$\dfrac{F_n}{2^n}$$$.

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

    While solving, I didn't realize dp[N] = F(N).

    I solved it with dynamic-programming.

    Code

    Nice observation.

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

    Thanks for the explanation.

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

    The way I solved it is noticing the problem comes down to "Find the number of ways that you can express a number $$$n$$$ as a sum of odd numbers". Pretty well known this is found with the Fibonacci Series.

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

    That's nice! I solved it in a more dubious way. My solution is based on the following observation: suppose the first active tower is x, then towers 1 -> x-1 and x+1 -> 2*x-1 are not active. Ok, now say we have N towers and we activate the first tower. Its signal power is obviously 1. This leaves us with the other N-1 towers and the initial problem, but with only N-1 towers. If we say dp[i] = the solution for i towers, then we can now state that dp[i] = 1/2 * dp[i-1] + something (1/2 is because we have to activate the first tower) Now suppose the first tower we activate is the second one. Its signal power is 2 and the first and third towers are not activated. Excluding these towers, we have the initial problem but with N-3 towers. So dp[i] = 1/2 * dp[i-1] + 1/8 * dp[i-3] + ...

    Let's take some examples: dp[5] = 1/2 * dp[4] + 1/8 * dp[2] + 1/32 * dp[0] dp[4] = 1/2 * dp[3] + 1/8 * dp[1]

    We can keep 2 partial sums, one for odd numbers and one for even numbers. When we calculate dp[5], we add it to the odd partial sum the following way: sum[odd] = sum[odd] * 1/4 + 1/2 * dp[5].

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

Why do u write "row" Instead of "consecutively" When u know prob A contains rows and cols

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

How to solve B? It was very hard for a B problem.

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

    Say the sum is $$$S$$$, since we want them all to have the same number of blocks and the pile he chose ends up with $$$0$$$ they will have exactly $$$\frac{S}{n-1}$$$ blocks. So we always have to make $$$S$$$ divisible by $$$n-1$$$.

    The only other condition is that $$$\frac{S}{n-1}$$$ is at least as large as all elements, otherwise since we can't take blocks away that pile would be larger.

    Thus, if the maximum element in the sequence is $$$M$$$ the answer is just the largest of $$$M(n-1)-S$$$ and $$$(-S) \pmod{n-1}$$$

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

      Thanks man , this s/n-1 thing came to my mind but was not able to develop on the thought .

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

      What is the reason behind $$$(-S)(mod \ n-1)$$$?

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

        To redistribute the blocks between $$$(n - 1)$$$ boxes, $$$S$$$ should be divisible by $$$(n - 1)$$$. $$$(-S) \bmod (n - 1)$$$ is the smallest non-negative number that, when added to $$$S$$$, makes it divisible.

        Note that in this case, $$$\bmod$$$ is the mathematical definition of the modulus operation, in some languages (in C++, but maybe in some others as well) the standard modulus operator doesn't work that way (it will not produce a positive result if $$$(-S)$$$ is negative, but $$$\bmod$$$ in mathematics always produces a non-negative number), so you have to add $$$(n - 1)$$$ to the result of this expression to handle it, if the result is negative.

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

    The idea is that if we can use the minimum value of the array to make every other value equal to each other ,then we can do the same for every other $$$i$$$. Let $$$mn$$$ be the minimum value in the array and $$$mx$$$ be the maximum. Then we need to calculate the sum of differences between $$$mx$$$ and every other value different from $$$mn$$$, we can call this value $$$s$$$. If $$$s>=mn$$$ then the required number of blocks will be exactly $$$s-mn$$$. Otherwise, we need to verify that $$$mn-s$$$ is divisible by $$$n-1$$$. If $$$(mn-s) mod (n-1) = 0$$$ then the answer is $$$0$$$, otherwise it will be $$$n-1$$$ minus the remainder.

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

    Just make the sure you can satisfy all the conditions if you pick the box with the smallest number of balls. Because that box is the one with the maximum constraints. Then the other boxes will automatically satisfy the conditions because they will have lesser constraints than the smallest box. To satisfy the smallest box, calculate how much extra balls you require to make every box other than the selected box have the same number of balls i.e. the max.no. of balls in a box.

    If the req no. of balls is less than the balls you have, just make sure that the extra balls are divisible by (n-1)

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

The problems A-D were very good and I enjoyed solving them.

But why sudden steep increase in difficulty for E,F,G

(Looked like Div0.5).

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

Solved E in $$$O(n^3)$$$...

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

Has someone solved e using ST with arithmetic sequence? I didn't manage to debug it in time.

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

Actually, I like problem B. But I didn't like why the arrangement is A — B — C — D instead of A — C — D — B (More precisely, B is harder than A, C, D because the idea not the straightforward one rather than A, C, and D). Since the target of contestant is Div. 2 user, I think put B in the second problem wasn't a good idea due to the idea is "more cool" than C and D.

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

any ideas what the 8th pretest for problem E is?

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

It would be better if you would have even allowed $$$O(n^2 \cdot logn ) $$$ solutions in problem E :(

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

    We have written some $$$O(n^2 \log n)$$$ solutions for E, and they pass. Unfortunately, several participants even squeezed $$$O(n^3)$$$ with a lot of optimizations, so perhaps we should've left the constraints as $$$n \le 5000$$$. What is your solution?

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

      I came up with this: iterate on leftmost of the 2 ranges, and initially map each input boundary to leftmost author. Then run a 2nd loop for 2nd author from right to left and keep removing intervals from left interval and move to right interval's DS. But that would required me to use lazy propagation which is very slow. I think with some smart work, it can be done without lazy propagation? or does the solution approach completely differ from this one? Time Complexity would be O(N^2 logN)

      PS : Some N^3 solutions still managed to pass I believe. Also what do you think, would a time limit of 2.5 secs might have been better?

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

        My solution is the following:

        Let's look at two edtiorials as segments $$$[x, x + k - 1]$$$ and $$$[y, y + k - 1]$$$ ($$$x \le y$$$). Suppose there is a guy who wants to listen to problems $$$[l_i, r_i]$$$. Let's look at the centers of these three segments. If the center of the segment $$$[l_i, r_i]$$$ is closer to the center of $$$[x, x + k - 1]$$$ than to the center of $$$[y, y + k - 1]$$$, then the guy should go to the first editorial, otherwise — to the second editorial. It means that if we sort the participants according to the values of $$$l_i + r_i$$$, the prefix of them will go to the first editorial, and the suffix — to the second editorial.

        There are different ways to continue this solution, but perhaps the most simple is to build prefix sums to answer the query "the sum of $$$a_i$$$ on some segment of participants if they go to an editorial starting with problem $$$x$$$" in $$$O(1)$$$. Then we just iterate on the prefix of participants that go to the first editorial, and find the best editorial for the prefix and for the suffix in $$$O(n)$$$.

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

          Wow! Centers of the segments is brilliant! I wrote exactly that but tried some weird comparators. Nice problem!

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
      • Iterate for the range $$$ [l,l+k-1] $$$ of the first author.

      • For each $$$ l $$$, iterate for the range $$$ [r,r+k-1] $$$ of the second author, where $$$ r >= l $$$.

      • Whenever change range $$$ [r,r+k-1] $$$ to $$$ [r+1,r+k] $$$, remove the participants who will now prefer reading editorials from the first author's range. (They won't see editorials again from the second author for each $$$ r' > r $$$)

      • Maintain 2 segment trees, each having lazy propagation. Update answer by $$$max( ans,Query1(l,l+k-1)+Query2(r,r+k-1))$$$.

      • Participants having $$$ l_{i} = l $$$ will permanently join the first author for each $$$ l^{'} > l $$$, so update the segment tree accordingly.

      • Reset the segment tree of the second author.

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

      98943451 it didn't even use the simplest optimization that iterates j from i+1 :(

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

Solved problem D by finding pattern from sample test cases.

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

Please give One editorial for Two editorial!

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

Solving E be like...

4n15vj.jpg

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

What sort of optimizations in Problem E for passing O(n^3) solution ??

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

My solution for B,

Main observation is, If we empty any box the total number of blocks should be divisible by (n-1). Since we cannot remove any blocks we should add some blocks and the sum of all blocks should be divisible by n-1, so we will add some X blocks such that the sum of all blocks will be divisible by n-1. In this case each box will have (initial sum of blocks + X) / (n-1). If this value is greater than or equal to maximum blocks holding box, this is the answer.

But if this value is less than the initial maximum blocks holding box(say MAX), then we cannot arrange equal number of blocks in all boxes. so in this case it is optimal to have that MAX blocks in all boxes.

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

I have faced problem submitting D in last 7 minutes of the contest.Is there anyone who faced the same problem? Or it was just bad luck of me.

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

I felt B was easier than D. I don't know, I just was not able to see the Fibonacci pattern and delved deep into the combinatorics realm.

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

nvm

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

Can someone explain the logic behind using fibonacci pattern in problem D

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

I so much wanted to solve D. Solved it at once after seeing the solution. Damn man

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

What I don't like about D

A lot of people solved it by the "notice the pattern" style without understanding anything about the problem itself. I don't think it is acceptable for the D problem

Also surely B was more difficult than C but that is less of a problem

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

    what is proof of using fibonacci pattern in problem D

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

    This happens a lot of time, especially with OEISable questions, kind of a shame that they miss out on nice problems but people are desperate to do questions during the contest (ofc I also used to do that), and besides that, I think being able to observe pattern is smart too, so it's acceptable imo.

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

      I thought about OEIS kind problem too while writing the comment . Thank god it was not easily googlable this time.

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

Wasted more than an hour debugging G only because of some extremely stupid mistakes. I can't believe how foolish I am. Really wish I could code more accurately =(

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

In the problem D, everyone used modExp(y, mod-2). why everyone used mod — 2.. I didn't understand.. can you please explain...

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

Very unpopular and complicated solution for D:

Any tower will cover only odd number of points. So lets say we decide to choose $$$k$$$ points and the number of points spanned by $$$i^{th}$$$ point is $$$y_i$$$. Now we just need to solve for number of solutions to the equation $$$\displaystyle\sum_{i=1}^{k} y_i = n$$$ , where $$$y_i = 2x_i + 1$$$ and $$$x_i >= 0$$$. It transforms to finding the number of solutions to the equation $$$\displaystyle\sum_{i=1}^{k} x_i = (n - k)/2$$$ , which is given by the formula $$$\binom{x+k-1}{k-1}$$$ where $$$x = (n - k)/2$$$ and parity of $$$n$$$ and $$$k$$$ is same.

The final answer would be just the sum of all values from $$$k=1 . . . n$$$ divided by $$$2^n$$$. Total time complexity would be $$$O(n*log(mod))$$$. Submission Link

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

in question A.Robot Program ,it was written that not more than 2 or more commands can be preformed in A ROW,so why test cases are made for rows and columns.

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

Why don't this (Problem B) give TLE ?

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

    The above solution uses the O(N log N) approach (multiset takes O(logN) for finding, deleting, and adding an element), which easily passes in 1 second under the given constraints

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

what is the dp approach for D?

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

    write a recursive solution to find nth Fibonacci number and memoize it.

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

      fibonacci?.. I was solving it 40mins through combinatorics while there was such a simple solution:(

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

        We can observe through the statement that we are supposed to find the number of ways in which n can be represented as the sum of odd numbers.

        We can see that from the below observation:

        Now, if there is any tower with power $$$P$$$ then it can provide signal to the right $$$P-1$$$ cities and the left $$$P-1$$$ cities and to itself. So, each such tower will provide signal to $$$2P-1$$$. Also, note that each city should get signal from exactly one tower. Consider if choose x cities with each having power $$$P_{i}$$$ then we have,

        $$$n={\displaystyle \sum_{i=1}^{i=x}(2P_{i}-1)}$$$

        Using the above observation, we can easily deduce that we are required to find the number of ways in which n can be written as the sum of odd numbers. Now we can easily check the probability of every single case is $$$p=\frac{1}{2^{n}}$$$ and x = number of ways to represent n as the sum of odd numbers, we get final answer as $$$xp$$$. Rest is just left to use MOD operations wisely to obtain the final answer

        To find the number of ways in which n can be represented as the sum of odd numbers uses the dynamic programming approach.

        Base cases are: $$$dp[0]=0,$$$ $$$dp[1]=1$$$

        The recursive relation here is: $$$dp[i] = dp[i-1] + dp[i-2]$$$

        Proof for the recursive relation:

        (1) $$$dp[n] = dp[n-1] + dp[n-3] + dp[n-5] + ... $$$

        Also,

        (2) $$$dp[n-2] = dp[n-3] + dp[n-5] + ...$$$

        Therefore, using (1) and (2), we get,

        $$$dp[n] = dp[n-1] + dp[n-2]$$$

        Hence, $$$x=dp[n]$$$ and $$$y=2^{n}$$$

        P.S Don't forget to use the modulus operations wherever necessary.

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

In problem D , i didn't reduce the probability fraction to irreducible form , but it got accepted. Should this not affect the final output ?

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

    Yes,it shouldnt make any difference because as much as I remember , the condition is that denominator and the modulo should be coprime and denominator is only the power of 2 in the problem and modulo is a prime no.... BTW , I hope you remember (x/y)%mod=(x*(1/y))%mod=((x%mod)*((1/y)%mod))%mod.

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

I think A,C,D were much simpler than B..... Its just my opinion

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

https://youtu.be/BauOvXZOmL0 I solved B using Binary Search , give it watch if you want to.

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

Any ideas for problem G?

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

    The main idea is the following. Consider some starting vertex $$$v$$$ for Bob. Bob can make at least $$$x$$$ moves from this vertex if there exists such a vertex $$$u$$$ that the distance from $$$v$$$ to $$$u$$$ is not greater than $$$x$$$ and the distance from any Alice's marked vertex to $$$u$$$ is greater than $$$x$$$. The rest is multi-source bfs + centroid + possibly binary search (there is a solution in $$$log^2$$$ and a smarter one in $$$log$$$).

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

Can anyone tell who is rainboy (sorry for unnecessary tagging)? I am just amazed to see his/her performance. He/She starts from last and does the most difficult problem which has only 5-10 submissions and then leaves the contest, whereas he/she could rank $$$1st$$$. He was an international master before and now just specialist. Does he/she do that on purpose or is there some other reason. P.S.- Rainboy ranked 6th by completing the last 2 problems. Rainboy ORZ

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

    He is probably another Karan gujjar.

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

      Please don't compare that shit with this guy. This guy is really really good. Was just confused of why he uses this strategy.

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

        I guess his main focus must be competitions like IOI, ICPC, where speed isn't given that much of an advantage over problem-solving. So, my guess is that he starts with the hardest problems because those are the level of problems that you would expect in such competitions, and also he must not care about rating at all :)

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

Just now, a friend asked me what happened to Master purinliang. I said "What was going on?" and then he sent me some screenshots.

I took a look! Ouch! It turned out to be yesterday. There were five young people, all rating more than 1900 points, and two rating more than 2400 points. They prepare a round named "Educational Codeforces Round 98", and I am very glad to join it.

However, the Problem A using a confusing vocabulary "row". I think that "Wa! There is a chance to hack others!" I coded that

if(x <= y + 1) {
    printf("%d\n", x + y);
    return;
}
printf("%d\n", x + x - 1);
return;

A "Wrong Answer" suddenly attacked to hit my face. Ouch! I was very careless and didn't dodge, Ouch! It is not good, I advise myself "Rat tail juice"(it means "Behave yourself" in chinese), and reflect on it, and stop making such cleverness in the future.

Ah, "Educational round" should be based on peace, coding ethics, and no hacking in the room! Thank you my friends!

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

Can someone help why my solution for problem B 98926905 got hacked.

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

    Why did you use while loop that has cost you? While loop will cause time limit excedded

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

    This part of the code highlights the flaw of your solution. Before you take a look at the explanation, see if you can find why there is a flaw.

        while((n-1)*mx<sum){
            mx++;cnt++;
        }
    

    Explanation: In this while loop, the incremennts keep running until the condition in the while loop is no longer satisfied. In most test cases, this while loop only repeats for a limited amount of times, so time is not a major concern. However, in the hack testcase, (n-1) * max is 2 billion, while sum is 3 billion. In order for (n-1) * max to be greater then or equal to sum, max would have to be incremented 500 million times to exit the while loop. When there is a total of 1000 cases of this type, there simply isnt enough time to increment the variable 500 billion times. (500 million x 1000 cases)

    How this can be avoided: Be careful with while loops because the execution will never leave the while loop until the condition is no longer satisfied. If there is a possible case that could make that while loop run forever or run a very large amount of times, see if you can find a way to remove it. Here, a max function can replace the while loop (and thus fix this flaw).

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

      Ok. I should have given more time while thinking about the solution. As soon as it passed the sample test, I immediately made the submission. I think it would have anyhow failed the system test. Also my logic has a flaw, I could have made a better solution. Anyway, Thank you for your explanation.

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

      I have made a new submission. Is there a way to run my new code on the test which was used to hack my solution?

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

        You do not need to worry about that, since all successful hack's test cases(including yours) are added in the test cases that is used for practice submissions.

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

How to solve problem B?

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

how to solve problem E?

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

It's soo much of wait for rating changes in rounds having 12 hours of hacking phase!

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

do comments add up for contributions ?

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

[Deleted]
It seems that I still have to wait...

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

When will the results of this round show in division 2 users rating..?

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

when the tuitorial come out?

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

When will the ratings gets updated ??

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

Looking forward to Rating changes & Editorial!

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

Hello, In question C)Two Brackets I am unable to understand why am I getting TLE for testcase #22, by looking at editorials I understand my approach could have been improved but as per my knowledge for test case #22, time complexity for my code should be O(n)(only for this particular test case),then why the error? https://mirror.codeforces.com/contest/1452/submission/98933235

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

    In test case 22 the input may be of the form [[[[[.........)))))))), in your code when the else if condition of s[i] == ')' will become true, it will iterate the complete vector as there wouldn't be any '(' for each ')', your loop will run for each closing braces and hence the time taken would change drastically and complexity would become o(n²)

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

Five hours after system tests and still no rating changes. Keep waiting...

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

Hey, I took part in the contest and was able to solve 2 questions. However, my rating hasn't updated. Neither has my contests page. Can someone tell me why?

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

how to solve b?

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

    It's easy to know that the most candies are needed when the nephew choose the smallest $$$a_i$$$ and make the candies in the rest of the box not smaller than the biggest $$$a_i$$$. You can get a fomula and calculate it quickly.

    Sorry for my awful English because I'm a Chinese :(

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

why i get tle in test case 20 of problem E

my submission : 99017296

logic

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

Where's the editorial

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

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

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

Reminder: please update ratings...

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

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