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

Автор AntiBsayer, 7 лет назад, По-английски

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

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

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

Deleted

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

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

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

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

Hats off to AntiBsayer.

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

Hello Codefores.

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

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

 Thanks Dude UserIsUndefined :)

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

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

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

I hope the problems are as short as the announcement.

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

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

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

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.

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

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

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

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

Glad to see the change in frequency of contests.

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

Rey Mysterio Round :D

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

Good Luck

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

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

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

Good luck & high rating!

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

Hope that I will gwt rank in Top-1000.

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

woo good luck

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

good luck

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

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

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

What a nice problemset! (no it is not)

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

EducationalRoundForces

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

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

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

ImplementationForces (would be okay for Educational round though)

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

How to solve div2B. ?

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

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

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

how to solve C??

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

    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.

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

      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?

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

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

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

    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

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

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

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

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

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

    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.

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

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

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

Can we solve D with euler tour?

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

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

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

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

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

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!

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

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

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

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

for a moment I thought I'm in Div1 round

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

Anyone else tried D with Euler Circuit?

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

Why are recent rounds be like ManyCasesPerCaseForces?

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

How to solve E?

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

    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.

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

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

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 !

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

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

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

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.

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

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

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

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.

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

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

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

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.

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

Screencast

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

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

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.

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

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

I'm trying to understand how ppl use a n x n x log2(n) x log2(n) array for solving problem 1301E - Нанософт. 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!

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

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

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

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