Теперь раздел EDU доступен и на английском языке ×

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

Автор djm03178, 11 месяцев назад, По-английски,

안녕하세요, 코드포스! (Hello, Codeforces!)

We're glad to introduce you to Codeforces Round #578 (Div. 2), which will start at Aug/11/2019 15:35 (Moscow time). The round is rated for Div. 2 participants.

You will be given 6 problems and 2 hours to solve them. The score distribution will be announced later.

The problems are prepared by hyunuk and me.

Thanks to pllk, Learner99, Rox, mohammedehab2002, cheetose, jh05013, rkm0959, edenooo, and alex9801 for testing the round. We would also like to specially thank to KAN and arsijo for coordinating the round, and of course, MikeMirzayanov for Codeforces and Polygon platform.

This is our very first round, so I hope you enjoy it a lot!

UPD: The scoring distribution is 500 — 1000 — 1250 — 2000 — 2000 — 2500

UPD2: The contest is finished. Thanks for joining us! Here's the editorial.

UPD3: Congratulations to the winners!

Div. 2

1: gamegamewillwinioi2020

2: oliviahye

3: ccf_n0i

4: 2om_neek

5: Tropical_maid

Unofficial Div. 1

1: kcm1700

2: uwi

3: square1001

4: kmjp

5: KrK

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

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

Waiting for a good round.

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

    You are also waiting for some upvotes, aren't you

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

    You definitely should participate, every contest coordinated by arsijo is an ACE (absolutely cool event).

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

      that's true, there are so many Supreme Hilarious Ideal Triumphant contests coordinated by him.

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

        You’re just another hater. All you can do is to write hateful comments.

»
11 месяцев назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится

Why can a user with rating $$$-40$$$ be the tester of a round? That's totally unfair! I don't want to take part in this round!!!!!!

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

BTS bring me here!!

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

I'm your fan

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

It's a friendly contest time for us Chinese :)

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

Wow! Korean Round!

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

Since our hopes were shattered last time, we hope that this time is different.

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

Man, such a friendly time for us Chinese!

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

the success key for this contest is to avoid "string" word.

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

Hope the difficulty distribution is reasonable this time :)

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

I hope the problems are enjoyful.

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

Winner Winner Korean round dinner!

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

BST(Binary Search Tree) bring me here!

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

I want to become purple!I've been waiting for it for a long time!

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

Too much new problem setter rounds recently.

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

Good tester

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

Waiting and still waiting...

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

Good time for Asia programmers!

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

Thank you all ...

»
11 месяцев назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

Is it rated?

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

Another Korean Round! I think this round would be wonderful round.

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

I don't need to stay up late for the contest.It's a nice time for Chinese users.Wish everybody(especially me) good luck!

»
11 месяцев назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

I love Korean people.

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

WOW! A very friendly time for Chinese and Korean!!! I won't worry about my sleeping!!!

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

Nice time!!!

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

Why arsijo? I definitely don't want to take part in this contest!!!!!!!

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

Good Luck for everyone who join this competition.

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

I've been waiting for this round almost one year. so hyped!

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

Wtf, where this dislike of arsijo is coming from? You haven't even seen this round yet, moreover, to my knowledge, most coordination work was done by KAN, and arsijo will just help to arrange the round as KAN may be busy at this time.

Also, by saying this sort of things you express disrespect to authors of the round at the same time. They did so much work, hoping you to enjoy the round, and now you dislike the round even before it began just because of coordinator.

All you guys saying "ohh round by arsijo again" are getting really annoying, not better than dumb "Is it rated" guys.

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

Wow!! I hope it would be great round ever!

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

good job!

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

I have the level to solve problem_A/B/C and more but my english level is so poor that I can not understand the meaning of problems QWQ

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

Finally I can take part in a contest without staying out late!

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

Korean-made problems and Korean-friendly contest time. It is perfect if the problems are very wonderful.

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

Time to go blue

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

Desire for becoming Candidate Master within 3 Div.2 Rounds!! :)

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

i think this round #778 very exciting. I hope my rank < 200 ^^

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

I failed to solve problem B in previous 2 contests. I don't want to make a hat-trick.

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

A good time.

I'd like to become blue this time.

kkkkk

»
11 месяцев назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

I don't like problems with long statment :/

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

hi gamegame do you think you will win ioi 2020

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

5:35 AM ON A SUNDAY MORNING on the US West Coast :(

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

what is the pretest 4 in problem B ?

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

    I changed

    if (a[i + 1] >= k)m += a[i] - (a[i + 1] - k);
    

    to

    if (a[i + 1] >= k)m += min(a[i], a[i] - (a[i + 1] - k));
    

    and it passed pretest 4

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

    I had the same problem. I did all I could but couldn't find what was wrong. Ruined the contest for me.

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

      Same for me...First I struggled with pretest 2 but then pretest 4 destroyed me cries

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

    I think you should add this to your code QwQ

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

    you can't dig under 0 so you have to judge it if the next one is less than k.

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

How to solve D?

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

What is the pretest 4 of problem C?

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

How to reach to solution of C ?

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

WHat was pretest 2 of Problem B?

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

I used long double in C, and I am afraid of precision problems now.

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

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

Waiting for the editorial guys!

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

Expected time complexity for problem D?

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

Why I keep getting TLE on pretest 11 of problem E?

I think it's O(|s|),Why?

Code

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

Can D be solved in O(n*n) time?

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

    Yes, using 2D partial sum to find out how many new white lines are created for each cell being chosen as the top-left position of the eraser.

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

I used divide and conquer and KMP in order to solve problem E . Though I was not quite sure if it would pass TL but my submission got the verdict WA. Can anyone help point out mistake in my solution :

My submission for problem E Apologies for the poorly written KMP.

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

How to solve D ?

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

Why wouldnt suffix automaton solution for E pass below the time limit? I couldnt use an array bcs of memory, so i switched to maps, but that gave me tle, but the complexity is O(n*log(alphabet_size)), is the map factor just too big?

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

    Why don't you use String Hash to compare two strings? It can be fast and easy to write.(Though it is slower than KMP)

    And, the alphabet_size=26, I think you should use array to store the edge on the SAM. The factor of map is very big when the size of it is too small like this.

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

      i jump straight to coding instead of thinkingof another solution, thats why i didnt use hash

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

    But the size of it is very big. I think you can think about the Suffix Array to solve the String Problem. When the alphabet_size or the size of string is very big, SAM is very slow.

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

    Oh, I didn't find that the alphabet_size is 62...

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

    Is there any way to squeeze suffix automaton in the tl?

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

      How are you using SAM? Constructing the terminal states after each new string takes too long and I can't see how to do it without

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

        If we assume that we have memory to hold an array for the transitions between states, that means our adding of a transition takes O(1), then our complexity of constructing SAM is O(n), when we query for the largest prefix that is a suffix of the first string, we just traverse the SAM and if we come to the node which is coresponding to the last character inserted into SAM, we found our longest prefix which is a suffix of the first string. By n we denote total sum of lengths of strings in the input, i dont see why this wouldnt pass(only cause of large constant for the map) , correct me if im wrong

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

          You can have more nodes corresponding to suffixes in addition to the one corresponding to the entire string. For instance if the string is $$$abb\dots bb$$$ every node corresponding to a substring with only $$$b$$$ is a terminal state.

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

            Yea, sry, ur right, dont know where did i get that silly idea

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

            Then, next question, can somehow suffix tree be implemented to fit the tle? To implement a treap for the transitions? Would treap be faster than c++ map? Or is there some c++ built in way to speed up map? And why is map factor so big?

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

Really good contest, in my opinion, even though I wasted a lot of time in A B and C. Almost had enougth time to debug E. RIP Rating twice in a row 1-1

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

What is the hacking test case for E?

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

Spent 1 hour trying to read and understand the preprocessing part of KMP. Then figured out that it can be solved with Hashing. Managed to only get A and B after that.

I still don't understand the preprocessing of KMP though.

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

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

Can you please tell me where is a mistake in my solution of B? 58581229

I spent the whole contest trying to find what's wrong with it.

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

Hey everyone, do you know what's wrong in my solution for E? 58612747

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

I'm foolish to use (single) unsigned long long for hash.

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

Nice pretest for C :v

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

Hack test case in E for MOD 1e9+7 is nonsense

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

    Dang that sounds really unfair, although I always use weird values to prevent getting owned a little bit more.

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

.

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

    edited

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

      Can you help me find my mistake too .

      Link to submission to B

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

        This line:if(arr[i-1]>=arr[i]) c+=min(k,arr[i])+abs(arr[i]-arr[i-1]);

        The conditional is unnecesary, because you can add blocks to the bag while arr[i-1]>arr[i]-k. With that, the sum changes too, the absolute value will generate wrong answer. You should change that line to: c+=min(k,arr[i])+arr[i-1]-arr[i];

»
11 месяцев назад, # |
Rev. 8   Проголосовать: нравится +19 Проголосовать: не нравится

R.I.P. for my single Hash (use unsigned int) in Problem E

Wrong Answer On Test 65 TAT

Great Hash-Killer!

I will never use single Hash in Codeforces again...

Tips: Using some unusual prime numbers to model can help you pass E

like NTT model number $$$998244353=119\times 2^{23} +1$$$ ...

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

    My single hashing using $$$M = 10^9 + 9$$$ and $$$P = 67$$$ passed here 58620113. Ignore all the calculations in the end in isEqual function I only check the equality of the 3rd hash.

    Edit: uphacked :D. It would be appreciated if people could share in this thread some tips to make string hashing more probable to pass :)

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

Я думал, что это признак плохого тона закидывает антихештесты в системные тесты. Ок, буду иметь ввиду.

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

Why does Problem D use "cin" get timeout results?

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

    Please add this in your main(),in front of your cin

    ios::sync_with_stdio(false);
    
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    What an interesting way to trick the plagiarism checker. Isn't it violation of the rules?

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

      Maybe not.

      This is a well-known skill in China to speed up cin, and cancel the influence from stdio

      As far as I know, lots of chinese OIers use this skills in their own codes.

      For honest, maybe sometimes using cin is more convenient than using scanf, (like Probelm E), and this skill can make iostream faster.

      So why not use this?

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

My submission got TLE on test 3 but it passes the pretests. How is this possible? .-.

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

When will the rating be updated?

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

Can someone explain what happens in problem C when both n,m are 1 or any one of them is 1?

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

Please, Can anyone help me know where my solution for problem C fails.?

My Solution

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

https://codeforces.com/contest/1200/submission/58612411

https://codeforces.com/contest/1200/submission/58619785

EXACT SAME CODE PASSES AFTE CONTEST??? I'm that unlucky to just get the wrong base on test 19? Are you kidding me? Can I get this restored?

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

God damn it! I feel so unhappy now (prob.C). I got WA on main test 35 because of real number rounding :(( (look at the selected text parts) In the contest I code like this: During Contest After that I fixed a little bit and got AC :(( After Contest Who has the same errors like this? Show me your hand bruh =))

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

For Problem E,why hash algorithm fail?

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

Please someone tell why my solution for E is failing at case 8. Though the expected and actual output seem to be same.

https://codeforces.com/contest/1200/submission/58612328

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

    Basically I had the same idea and my submission failed too. Can someone please help us to understand the error?

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

Why my submission failing for no apparent reason?

58615776 Please Help B question

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

    When you do the sum m+= k-abs(h2-h1) you are forgetting that the number of blocks of height h1 could be less than k-abs(h2-h1), so when you do that sum, the remaining number of blocks of that pile become negative, and that's impossible. So, the sum is m+=min(h1, k-abs(h2-h1)), and with that the number of blocks will never be negative.

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

My rating becomes 2019 Nice number LOL

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

58606364 What is wrong with this solution for B ? It fails pretest 4 test case no. 6, but when i run that particular test case on an ide, it shows the correct answer.

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

    If h[i]<h[i+1]<k ,then m-=b makes 'm' increaing ,obviously it's not true.

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

      Why won't m increase in that case ? Suppose h[i]=4, h[i+1]=6, k=8. Then we can collect all the 4 blocks from h[i] and transfer to m,right?

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

        Sorry it doesn't mean that. Well , k=160,h[i]=47,h[i+1]=107 then u should make b=-47 but not h[i+1]-h[i]-k=107-47-160=-100 ,right?

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

58580810 Could somebody tell me where is my mistake? It's my first time to be hacked in problem A and I'm gona to be crazy. T_T

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

    Look into your (**left, right**) variables they took same value in testcases. Two costumers cann't enter same room

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

Any ideas to solving F?

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -67 Проголосовать: не нравится

As i said in this comment i got TLE on test 3 but it doesn't make sense because the the code passed the pretests.

And the same code after contest got AC.

WTF?

And i lose rating because of this.

Why is this? djm03178 MikeMirzayanov

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

Someone explain D?

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

    consider for each column and for each row, all the available left-top positions of the cfpaint which can make this column or row all white form a rectangle. We define left-bottom position of this rectangle as (x1,y1),right-top position of this rectangle as (x2,y2),and then we need to add 1 to all the position(x,y) which satisfy x>=x1 and x<=x2 and y>=y1 and y<=y2, for this purpose, you can solve it like this: init dp[n+1][n+1] all value as 0,and when you deal with each row or column,first find the available (x1,y1)and (x2,y2),then just do like this: dp[x1][y1]++,dp[x2+1][y1]--,dp[x1][y2+1]--,dp[x2+1][y2+1]++. after solve all the rows and columns, you iterate over dp[n+1][n+1],set dp[i][j]+=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1],after this find the maximum value in dp is just the answer.

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

Может кто подсказать, в чём дело? F 58631952

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

경합이 아주 재밌었고 레이팅도 올랐고 덕분에 "아무개"란 단어도 배웠어요! 고마워요ヾ(❀╹◡╹)ノ゙❀

Thanks to this contest I learned a Korean word "amugae" and gained +25 rating points, thank you very much!

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

I have received code coincide message for problem C,Here is the two links:58583425 58592979 I admit that these two codes are very similiar. But it is truly just because the solution for problem C is so simple and the codes between us written similarly accidently.What's more, not only the codes between us looks similiar,many codes are. I have tried to comunicate with Mike, but I didn't get any response yet maybe Mike is very busy now. I just want to show thst I am honest to participate in the contest.

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

For problem F, can someone explain how is the LCM term coming? (Specifically, how is the number of states for a particular vertex 2520 and the logic behind decomposition of the graph in various states).

I'm not sure what the author means by state here.

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

Can anyone explain me why my first submission got TLE and second got AC? I think the both code has same complexity. Thanks in advance. :)

1st submission: https://codeforces.com/contest/1200/submission/58837253 2nd submission: https://codeforces.com/contest/1200/submission/58837269

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

Why problems aren't rated yet?

Edit: They're rated now!