Kilani's blog

By Kilani, 5 years ago, In English

Hello Codeforces.

I would like to invite you to participate in Codeforces Round 619 (Div. 2) which will take place on Feb/13/2020 17:35 (Moscow time).

The contest will be rated for Div. 2 participants. It will include 6 problems, and you have 2 hours to solve them. The problems were created and prepared by me.

I would like to thank KAN, isaf27 for coordinating this round. And 300iq, -is-this-fft-, AdvancerMan, Dup4, Agnimandur, Tzak, DomiKo, Aleks5d, Supermagzzz, manta1130 for testing the round. I also would like to thank MikeMirzayanov for great and perfect Codeforces and Polygon systems.

hope you enjoy the contest and find some interesting problems.

UPD: Score distribution: 500-1000-1250-1750-2500-2500.

The round has ended. Thanks for participating and congratulations to the winners.

Div1:

  1. jqdai0815
  2. dreamoon_love_AA
  3. LayCurse
  4. wucstdio
  5. neal

Div2:

  1. COVID-19
  2. MofK_from_Bangladesh
  3. jxdxhy
  4. Crazy_Diamond
  5. DovydasVad

Tutorial

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Is it the summary of regular codeforces announcement? I love it.

»
5 years ago, # |
  Vote: I like it +80 Vote: I do not like it

I tested the round, and I highly recommend you participate! It is a good round!

Hats off to Kilani.

»
5 years ago, # |
  Vote: I like it +85 Vote: I do not like it

Hello Codefores.

You forgot the letter "c". hope your statements don't have such mistakes.

»
5 years ago, # |
  Vote: I like it +48 Vote: I do not like it

 Thanks Dude UserIsUndefined :)

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think everyone is busy on 14 FEB as there is no contest on the day .

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I hope the problems are as short as the announcement.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It doesn't matter if they are short.Even short problems can be hard.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +64 Vote: I do not like it

    It's not about difficulty, it's just tedious to make sense of a wall of text. And usually problems "feel more beautiful" if they are concisely (but still understandably) stated.

    (I don't care about that so much unless it's like two pages long, but still, this is why people like short statements.)

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

    Like arc84B Small Multiple. Only one sentence which seems like Div.2A/B. But actually it's in the difficulty of Div.2D/E

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

Previous contests of codeforces used to be much better. But these days contests have just become a waste of time. Most of the people are unable to reach the questions which are really interesting and actually need to be solved.Easy dp and graph problems need to be included in the contests.

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

    gitgud

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    I think this is the biggest difference between hiring-focused platforms and olympiad-focused platforms. But I agree some easy problems should be included in early part of Div.2.

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

    Can problem C yesterday be regarded as "graph problem" and problem E yesterday be regarded as "easy dp"?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I love your gym statements and was waiting for your official round :D

»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Glad to see the change in frequency of contests.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Rey Mysterio Round :D

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Luck

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I was Candidate Master when I registered to this round, and I became master on yesterday contest. I checked the registration list for this round, and I don't have an asterisk on my handle. Will this round be rated for me? Thanks! :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Yes.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Yes. Registration before rating change can lead to such problem.

    It's actually a known bug in CF, and I've written a post for it. Unfortunately CF hasn't fixed it. :(

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 4   Vote: I like it +32 Vote: I do not like it

      Wow, that's weird haha. Well, let's hope I don't lose my color because of this contest. Good luck everyone!

      UPD: it seems the bug has been fixed, I see an asterisk in my handle on the standings. Well done Codeforces! :D

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck & high rating!

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope that I will gwt rank in Top-1000.

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

woo good luck

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I told My Non-cs friend,there is a contest today and he asked "is it Codeforces a dating Site"?

»
5 years ago, # |
  Vote: I like it +107 Vote: I do not like it

What a nice problemset! (no it is not)

»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

EducationalRoundForces

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

Does $$$O(knm \log(nm))$$$ TLE F?

»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

ImplementationForces (would be okay for Educational round though)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2B. ?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    let HI be the highest value that is adjacent to a -1. let LO be the lowest value that is adjacent to a -1. the value of k is equal to (HI + LO) / 2. let DIF be the maximum difference between two adjacent elements that are different from -1. the answer would be the maximum between DIF and the maximum between HI — k and k — LO.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have done what you said but still WA

      My WA solution code

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think your code has some bugs and you are not doing exactly what I said. if you try: 5 1 2 3 4 -1 your program outputs something wrong. Try coding again in a simpler way.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain logic behind this solution?.

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

        all the -1's will be replace by k. so you only need to take care of the minimum and the maximum neighbors because the maximum difference between k and any number between LO and HI will always be less than or equal to the maximum between |HI — k| and |k — LO|.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks.!

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hey I tried finding the lowest positive and greatest positive numbers and assign the K= average of the two number and then find the maximum adjacent difference what was wrong in this approach

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            lowest positive and greatest positive numbers should be adjacent to -1

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Why are we searching lowest and highest which are adjacent to -1? Why not the whole array except -1?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                100 99 98 97 96 -1 0 for this case we should put 48 at -1's place but if you search highest and lowest you will put 50 which will be incorrect. Hope this clarifies

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why O(log*m*n*k) got "TLE" on problem F??

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

how to solve C??

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

    In fact, you need to minimize the number of pairs $$$(l, r)$$$ such that substring $$$s[l:r]$$$ contains only zeroes. This can be calculated separately for each group of adjacent zeroes. For a group of $$$x$$$ adjacent zeroes it is $$$x(x + 1)$$$. So the problem can be rephrased like this:

    $$$\text{Split } n - m \text{ into several numbers } a_i \text{ such that } \sum a_i(a_i + 1) \text{ is minimum possible}$$$

    It is easy to see that the solution to this problem is to: (1) split $$$n - m$$$ into as many numbers as possible (keep in mind that you cannot have more than $$$m + 1$$$ groups of zeroes); (2) when splitting, make $$$a_i$$$ as equal as possible.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Intuitively I agree with you. But, what’s the formal proof of your last statement i.e. splitting them as much and as equally as possible will yield the lowest desired value?

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

        Assume you have the "lowest" splitting. If there are number with difference > 1, you can always make the result lower. Let's say you have $$$a$$$ and $$$a+x$$$ in the splitting, and $$$x$$$ > 1. Then compare:

        $$$a^2 + (a+x)^2 \text{ vs } (a + 1)^2 + (a + x - 1)^2$$$

        This reduces to

        $$$0 < 2 - 2x$$$

        In other words, if $x$ > 1, the reduction of the gap between numbers always reduces the sum of squares. Then the minimum sum will be if the largest gap between numbers is 0 (if possible), otherwise 1. You can easily show that such reduction does not take infinite time.

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

    you need to minimize the largest substring that only contains 0's. to do this you just need to distribute the 0's between the ones. for example if n is 8 and m is 2 is should be distributed like 00100100. then to count them you have to count the number of substrings n * (n + 1) / 2 then subtract the number of substrings that contains only 0's, to count that you need to divide the number of 0's by the number of ones + 1, and count separately the regions that contain one more 0 than the others (if the number of 0's is not divisible by the number of ones + 1) for example if n is 10 and m is 2 the distribution would be something like 0001000100

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

    Imagine the string as groups of zeroes separated by ones. The answer will be the number of all substrings — the number substrings in each group of zeores(Z). To achieve the highest answer to the original problem we want the number of substrings in each group to be the lowest.

    We achieve that by spreading all zeroes in as many groups as evenly as possible. the groups(G) will be n — m if n — m <= m and m + 1 otherwise(write down some cases and you will see why, that how I found that during the contest). The number of zeroes in the groups will be their overall count of zeroes divided by the number of groups. If we have reminder(R) in this division then we can put 1 extra zero in Z % G groups to keep the zeroes as evenly as possible spread.

    By now we have G — R groups of Z zeroes and R groups of Z + 1 zeroes and using that we can calculate the answer as ((n + 1) * n / 2) — (G — R) * ((Z + 1) * Z / 2) + R * ((Z + 2) * (Z + 1) / 2).

    I hope that was helpful :)

»
5 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

for people looking to improve their algorithmic coding skills, is giving contests based on heavy implementation, of any use?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I enjoyed the implementation — which has it's own set of puzzles. Unfortunately I forgot to remove a debugging infinite loop counter before submitting, :( I'm gonna kill myself if my code actually passes after removing the counter.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B? I tried Binary search on m, but it failed on pretest 2.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the largest element that is adjacent to a -1 is a and the smallest element that is adjacent to a -1 is b, then we should set all -1's to be the average of a and b say c and that will minimise the differences. the maximum difference will be max(maximum difference between the elements that were already defined,c-a,b-c )

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

    I solved it with binary search,

    You can take a look at my implementation.

    A.C Submission

    If you have any doubts, you can ask.

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

      can you explain how you found that the function is monotic so that binary search can be applied

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just wrote some cases on paper and observed the pattern.That worked for me.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain how your code works?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Consider the point i found while binary searching at current state is 'x'.

            Then if, f(x) < f(x + 1) you can observe that the minimum point is lying at lower x than the current one. So I make high = x.

            Else if, f(x) > f(x + 1) than the minimum point is lying at higher x than the current one. So I make low = x + 1.

            And, to avoid any error. I make answer as the minimum of(low, high).

            I hope you understood. I am not that good at explaining.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve D with euler tour?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried it with euler circuit.The conditions of euler circuit are satisfied for all matrices i believe.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. That's what kinda what I did. I found an euler tour that also ran through all the edges.

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

O(t) solution of problem C in Python gets TLE while the same code in C++ AC

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My O(t) solution got TLE in PyPy3 but got AC (795 ms) in Python3. They are the same code. Are there any strange testcases?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you append your answers in an array and print at last, it will pass

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had no luck on both pypy and python 3. However switching from input() to sys.stdin.readline() made it pass (even though testing on my local machine the latter isn't supposed to be faster, both versions take around 500-600ms).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use the Fast I/O Method As the number of Test cases is about 1e5, So you have to take input 1e5 times. Therefore Fast I/O reduces some time.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I tried switching from input() to sys.stdin.readline(), and my solution passed both in PyPy3 (748-779 ms) and in Python3 (701 ms). I'll use this fast I/O method from the next contest. Thank you.

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

      I use this fastIO usually. I forgot to use it in this problem, but it helps me a lot with big I/O in several problems:

      def fastio():
          import sys
          from io import StringIO
          from atexit import register
          global input
          sys.stdin = StringIO(sys.stdin.read())
          input = lambda : sys.stdin.readline().rstrip()
          sys.stdout = StringIO()
          register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
      fastio()
      
»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone tell me if my approach is wrong or i have some implement mistakes.

I just calculate the same color square size of every grid being bottom right.

Then check if every grid can be bottom right with the same color square size * 4.

Then build 2D prefix sum table for query.

submission

»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

What's up with the problemsetters these days? Are they competing on who can make the worst problems? Then I have to say that they did really well this time.

Congratulations!

»
5 years ago, # |
  Vote: I like it +98 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody find out why my C submission is wrong? (https://codeforces.me/contest/1301/submission/71007756)

I see guys with literally same code get AC

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

for a moment I thought I'm in Div1 round

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -35 Vote: I do not like it

    all codeforces rounds are like this recently. also انت طري

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else tried D with Euler Circuit?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is a constraint in output that $$$a\leq3000$$$. So Euler Circuit doesn't work.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to compress the string formed afterwards.

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

        I mean if you just copy a general implementation of Euler Circuit, 99% $$$a$$$ will be greater than 3000 (even if you compress the euler circuit). So you have to construct the Euler Circuit by yourself. Actually there is a easy way to make $$$a\approx3n$$$.

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

          for a full test case, the lenght of the euler circuit is nearly $$$10^6$$$, it is almost impossible to compress its length into $$$\frac{1}{300}$$$ of the original length.

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

            Yeah i get what you are trying to say but what I did is a tad different from some optimal compression technique.I found that string "RUL" was repeating numerous times in the circuit, and then compressed it afterwards.I didn't know any other way to find some sort of pattern in the graph and brute was a bit too difficult for me.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              my code here

              (please ignore my heads)

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              To go through a row, a easy way is to use (m-1,"R") and (m-1,"L"). To optimise, use (m-1,"RDU") and (m-1,"L") if possible. After that, there is no vertical edge left except the first column.

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

            "for a full test case, the lenght of the euler circuit is nearly $$$10^6$$$, it is almost not impossible to compress its length into $$$\frac{1}{300}$$$ of the original length" 70990140

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Why are recent rounds be like ManyCasesPerCaseForces?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    Calculate 2D prefix sums for each colour.

    For each possible size $$$i$$$ ($$$1$$$ to half of $$$n$$$ or $$$m$$$) and each possible position, calculate whether you can make the required shape by checking if the partial sums of each colour in respective regions are equal to $$$i^2$$$, and if so mark it down (e.g. on top-left corner). Do partial sums on each possible size.

    To answer a query, binary search on the largest possible size. The partial sums you just calculated helps you determine if there exists at least one square of such size.

    Time complexity: $$$O(n^3 + q log n)$$$

    I realized it can be binary searched after the contest.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow.. What an amazing solution. I've never thought that was related to binary search. Thanks a lot!

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Same. But you need $$$O(n^3)$$$ space to store the partial sums. std::int16_t works. But I didn't use binary search in the contest. So the time complexity becomes $$$O(n^3+nq)$$$ and space is $$$O(n^2)$$$. Hope no FST.

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

This was an amazing contest and the problems' had mind blowing quality ! Even $$$A, B$$$ required thought ! I have noticed contests with a single problem setter have great quality generally !

»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Have seen all kind of "*forces", but this was my first experience of gridforces.

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

I have to say that it is really good test, even problem A and B needs to be thought. Besides, C is a good problem too.

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

Can anybody take a look and find bug on my code for div2B? Seems like my approach was correct but it failed on pretest2

http://codeforces.me/contest/1301/submission/71011665

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    while (arr[l] == -1) l++;
    while (arr[r] == -1) r--;
    minar = maxar = arr[l];
    

    This is wrong, when array doesn't start -1, you are including a[0] to compute min and max. correct one 71018156

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're right. Thanks a lot!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am extremely sorry that my code matches with others.This happened because I used ideone as i was unaware of the fact that ideone gives access of my code to everyone.From now on I won't use ideone. I request you to consider my submissions because this was the first time I got this much rank.

»
5 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

guys, I solved a question right in the first time but my rating went down why?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the only Problem — A and it showed me accepted verdict. I am newbie here and I dont know that why did my rating drop? Please answer it.

»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Screencast

Warning: It's my first time to make a screencast. The video quality is very low. I will make it better next time.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B. "Motarack's Birthday" — interesting problem about arrays, so I suggest next time to name it more descriptive, e.g. "Motarack's array" or so. It is easier then to remember and to search problems.

»
5 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm trying to understand how ppl use a n x n x log2(n) x log2(n) array for solving problem 1301E - Nanosoft. Unfortunately I don't really understand it and my approach times out so I'm looking for new clues. Could someone give a brief explanation or a link to a tutorial somewhere? Thanks!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the ternary search solution of B ?? Pure ternary search not the hoax one .....

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you manage to set Problem D as the worst and the most boring and the most uninspiring problem ever?