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

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

Hola, Codeforces!

Мы рады пригласить вас принять участие в Codeforces Round 936 (Div. 2), который состоится в 22.03.2024 17:35 (Московское время).

Раунд был подготовлен dope, max0000561, sadness и мной.

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

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

Мы хотим поблагодарить:

Отдельное спасибо хочется выделить KoT_OsKaR и teraqqq за помощь в создании задач.

Всем удачи на раунде и высокого рейтинга!

Разбалловка: 500−1000−1500−1750−2250−2750.

UPD: Дата проведения раунда изменена, чтобы избежать пересечение с соревнованием на другой платформе.

UPD: Разбор

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

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

Приятного аппетита

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

As a tester, this is one of the coolest rounds I've ever seen

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

Can I have a slice of pizza, please ?

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

That pizza looks delicious

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

As a tester, I think that this round is very nice

Good luck guys!

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

As a tester, I recommend you to buy computers for the lowest price

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

Does anyone eat pizza without sauce or mayonnaise? Anyway it looks delicious.

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

Good job bois! I hope this contest will serve as a cornerstone for many to reach the heights of 1C. The best part is an afterparty in Marino. The great Holiday of Vyval is coming!!!

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

Уффф чо за легенды

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

Enjoy the process!

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

pizza without toppings ??

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

Hopefully it is the start of 74TrAkToR's Redemption Arc

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

Наши слоны!!!

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

The unusual round time tho :)

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

Hope reach pupil after this round

GL for everyone!!!!

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

фиаско это тоже опыт

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

Hope everyone will get positive abs(Good bye 2023's) delta.

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

Hopefully mathforces❤️

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

sigmaforces

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

It is 2:00 a.m. and now I'm hungry 🥺

You didn't have to do this to me.

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

I think the timing is showing in UTC+3 for everyone

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

Pizzas and kudos to the authors for continuing the trend of attaching pictures!

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

It's great to see CF round's authors posting images of their daily life again <3

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

wow!That pizza looks so delicious!

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

Hoping for a pizza with positive Delta toppings...

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

Автокомментарий: текст был обновлен пользователем yunetive29 (предыдущая версия, новая версия, сравнить).

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

Users on this site have pretty weird satisfaction downvoting any thing they see,even their own picture. [:

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

Yay 74TrAkToR First Round Coordination in 2024 !

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

The upd says "The date of the round has been changed to avoid interference with a competition." What competition is that?

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

UPD: The date of the round has been changed to avoid interference with a competition on another platform.

Average 74TrAkToR moment

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

hope, I can solve at least 1 problem

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

Hope for a exciting contest <3

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

traktor bros going to cook us

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

UPD: The date of the round has been changed to avoid interference with a competition on another platform.

Which platform?

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

The traktor bros are about to serve up something fierce

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

Good luck guys!

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

Ramadan Kareem

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

I hope that round's problems would be like Pizza !!

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

Bro,you smells good

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

.

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

If I could get 1600 by the contest,I would be excited all day long.Try my best!

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

Bro,you smell so good.

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

74TrAkToR :(

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

Why do I remember it was March 21st? Did I make a mistake?

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

good luck everyone :>

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

Seriously? Goodbye 2024 in March?

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

pls everyone give me dislikes! I want to have lowest contribution!

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

EVERYONE DISLIKE MY COMMENT! I HATE THE JUDGES, I HATE EVERYONE!

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

sorry, someone took my laptop

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

OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH !

74TrAkToR Round !!!!!!!!!

74TrAkToR Round !!!!!!!!!

74TrAkToR Round !!!!!!!!!

74TrAkToR is the person in the photo you ? It looks very ......

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

As one of their lecturers I strongly recommend you to participate in round! Hope you like it!

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

Hopefully it is the start of 74TrAkToR's Redemption Arc

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

Yes,brother,as you see,I am back!

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

In one of recent contests, I submitted wrong algorithm but it passed the pretest so that I got FST on it. I hope the data in this contest is difficult enough that it will minimize the likelihood of FST. By the way, I hope I can become Expert.

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

As a tester who forgot to test a round for three months, this round is very cool

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

Hope remain Expert this round.

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

IPL is clashing with this contest

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

After contest will have pizza..

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

As a participant, this is one of the coolest rounds I've ever seen

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

How to solve problem C?

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

    Binary search on the answer and greedily cut every sufficiently large subtree.

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

      I implemented that but somehow got WA. Can you please have a quick look at my solution to see where my mistake lies? Thanks

      252801186

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

        You are updating subtree sizes incorrectly. Say a is a parent of b and b is a parent of c. You cut c and subtracted its size from b. Now you cut b and subtract its updated size from a. But a was calculated using old subtree size of b, so you didn't subtract enough. You should calculate subtree sizes during the same dfs.

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

      I'm doing exactly this but getting WA2. Where is my mistake? 252806411

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

      But wouldn't there be too many options for cutting and each option affecting the answer ?

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

        Suppose we are looking for some x.

        A few important notes:

        Hint 1
        Hint 2
        Hint 3

        And the solution:

        Solution

        My solution: 252786253 (I'm sorry for somewhat dirty code, I was trying to implement is as fast as I could after I found out the solution).

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

      hi, I also do exactly like this but I dont know why I got WA :( I will be very happy if you can spend some time look through my code :) 252794634

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

        I'm sorry but I don't understand what you are doing. For starters, you have two dfs instead of one. Also, no offense but I find your coding style difficult to read. The best I can do is direct you to my submission 252744762

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

          Thanks for looking at my code! I found out the error alr, it is because I only cut the node when its weight >= ans and max weight of children node < ans, where ans is the answer we are looking in binary search. I shouldnt include the condition about the max weight of children nodes in my dfs1 function.

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

      In your solution, could you please tell that in can() func, what's the purpose of checking sz >= x again (at the end)? In all provided test cases, that condition never got satisfied. Thanks for sharing your solution, btw.

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

        Root has no parent so there is no $$$(v, p_v)$$$ edge to cut and hence I thought I had to handle it separately. However, upon further consideration, it appears that the logic inside DFS handled it just fine too since it's basically the same.

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

how to aproach C? spend 1:30 and still have no idea.

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

Is E based on inclusion-exclusion principle???

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

    My solution has nothing to do with PIE. First observe that $$$p_{m_1} = s_1$$$ and $$$a_{s_1} = n$$$. Now solve the problem for $$$p$$$ and reverse of $$$s$$$ independently. Iterate over $$$p$$$ in reverse, it's easy to find the number of candidates for each position.

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

This was a really interesting round for me! Problem B was annoying simply because C++ % operator apparently does not work for negative numbers.

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

C >>>>> D (D is a garbage problem imo, literally solved in 10 minutes, just failed to implement 3 times)

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

    I solved C in 5 minutes but skipped D because it wasn't obvious to me. I think both problems are a bit boring but not bad for their positions in Div 2.

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

      I didn't solve C for an hour straight (how do you prove that greedy works?).

      D just felt like an implementation problem to me, not much thinking involved.

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

        Let S be a subtree that has >= x-1 children, and all its children have < x-1 children

        So cutting any of its children will invalidate the tree instantly

        If you have remaining cuts to make, we have two choices

        1- to cut now

        2- to leave this and cut later

        We need to prove that cutting now is the best option every time

        Suppose that cutting now will make the tree invalid and cutting a parent edge later will make the tree valid

        Remember that we have >= x-1 children right now, so the tree can be invalid only if the remaining tree without the current subtree has < x nodes, which will make any parent cut also invalid

        Which contradicts our assumption, so if there is a solution for x, we should always cut once we have >= x-1 children

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

        For each partition $$$P$$$, consider a deepest vertex $$$v$$$ where it differs from the greedy one $$$GP$$$. It means that greedy cuts edge $$$(v, p_v)$$$, where $$$p_v$$$ is parent of $$$v$$$ but $$$P$$$ doesn't. Note that it's impossible for $$$P$$$ to cut $$$(v, p_v)$$$ if $$$GP$$$ doesn't cut it.

        Let $$$u$$$ be the lowest ancestor of $$$v$$$ such that $$$P$$$ cuts $$$(u, p_u)$$$. Let's exchange these edges: consider $$$P' = (P \cup (u, p_u)) \setminus (v, p_v) $$$. We gained one new good component rooted at $$$v$$$ and lost one good component rooted at $$$u$$$ (and also increased the size of some component above $$$u$$$ but that's besides the point).

        Hence $$$P'$$$ is an equally good partition with a smaller "deepest different vertex". Choose $$$P^*$$$ to be the minimal partition by this criterion to infer $$$P^* = GP$$$.

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

C humiliated me

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

Surprisingly difficult C : Tree Cutting, but interesting nonetheless. I've added my hints and thought process on CF Step

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

E << C and D. I wasted too much time on C and D so ran out of time to debug E but I feel I'm close :(

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

    Problem difficulties are always subjective. I solved C in 5 minutes but spent an hour on E because I went in the wrong direction. I had dp[gap] = number of permutations with max - len = gap. It has interesting but complicated updates. I thought it could be solved this way, but eventually, I gave up and found a simpler solution.

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

Is this correct approach for D — We need to iterate over all the bits from 30 to 0 and try to merge numbers in pairs of two using DSU, depending upon whether that bit is set in x or not ?

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

Problem C is the reason for my headache today.

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

Would anyone be able to tell my WHAT is wrong with my code for problem B?

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

how to not be blank on problems like E?

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

can anybody tell why some test cases are not giving the correct answer : link

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

whats idea of D?

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

I hope the pretests are strong, cuz I passed D mostly by guessing

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

In today's contest I solved D but couldn't solve C.
In last div3 I solved E but couldn't solve B.
I don't know whats happening to me 😞

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

downvoted

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

got Accept D in the last 5 minutes. I regret not to use the initial idea (binary search) to solve this problem. My rank got down like 800 positions.

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

Why this solution fail on $th test case problem D

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

3000+ solve on c and I am not one of those geniuses.

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

Am I the only one whose confused about the problem B's statement?

What most people have done is take the maximum Subarray Sum using Kadane's Algo in the beginning and then just keep on taking that subarray along with the present added element using operation.

My question is: Won't the subarray become bigger as we keep on adding elements and then the entire array would be taken at once? This, in my opinion, would WA every solution.

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

A -> Simple sorting and sum

B -> Kadanes algorithms and then fast exponentiation

C -> Binary search on answer

D -> could not do during the contest :(

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

can anyone please look into my submission: submission thank you

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

Can question B be done without kadane's algo? something even simpler maybe?

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

fuck me.

forgot to mod the maximum of the sum of contiguous subarrays and i had no clue about how it would cause wa on test 3.

not trying to complain here. it's just that next time you see me i be gray.

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

I solved D in 15-20 minutes, spent a hour on C and still have no idea.I suck at Binary search.

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

Problem ABC : Simple greedy.

Problem D : Bitmask, and it's a bit harder than my expectation.

Problem E : Ridiculous problem which can be placed at div.2 C in former contests.

Problem F : Just a trival DS problem.

So what's the cool point of this contest ??? The unreasonable difficulty distribution?

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

in E I boiled down the problem to the following expression

SUM(product(ai)) for all expressions such that we can reduce 1 from aj and add 1 to ai any number of times subject to constraints i<j. example

expression -> 4!2!2!3! we can have the following expressions 4!3!2!1! or 7!0!1!3! but cannot have 3!3!2!3!

how to solve it further.

PS: SUM(ai) is bounded by n (2*10^5)

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

Do we any have graph solution for E?

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

Do we have any graph solution for E?

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

That's probably the worst round I have participated in for a long time.

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

-100 delta lets goo

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

Did not like it.

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

Cool contest! This is one of my worst performances recently :(, is F intended complexity n log n? I wrote a n log^2 n solution and TLE'd by a constant factor...

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

for problem F, i passed pretests, i can't pass pretest on system test, please rejudge, thank.

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

can anyone explain what's wrong with my code Solution

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

Problem D shares the approach with a problem on HDUOJ 2 weeks ago: (Chinese)

D. Legal Pairs

(I personally do not recommend this OJ from my experience in this contest: the statements were unclear and there had been serious queueing issues)

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

it's just for me? I just intuitively unclear on how applying Kadane's algorithm once is sufficient to get AC (problem B)

isn't max subarray sum varies every time we insert max subarray sum? because since max subarray sum become larger so that it may include elements on left and right side that were originally unable to include?

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

    Yes, it's not trivial to see, but also not difficult. I asked aryanc403 to elaborate on this in his stream. Timestamp

    The crucial idea is this. If the maximum sum subarray looks like

    _____S_____
    

    Then, all the extensions to the left or to the right have a net negative value. (Otherwise, you could use that extension to increase the sum).

    Now, suppose you place the incoming $$$S$$$ at a different position, like so

    _____S___S__
    

    Then, the max sum now is $$$S$$$ + middle + $$$S$$$. But we know that the middle extension will be negative, so it's better to keep it like so

    _____SS_____
    

    Even in this case, the maximum sum subarray would not contain any extensions to the left or right. Why?

    Hence, the maximum sum subarray is $$$2 \cdot S$$$.

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

how to solve E?

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

Can someone explain why this solution does not TLE? I tried to hack it during the contest, but I couldn't. It uses a memset to reset memory in every test case, which is O(T*MAXSIZE). Does the compiler make some optimizations somehow?

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

Liked the round overall, D is an extremely nice problem, and i liked F too.

Nevertheless, pointing out some issues : BC are both boring and imo not correct for their spots. Tree dp + binary search, and kadane's algorithm really dont fit for the 2nd and 3rd easiest problems, and also are quite standard.

F TL??? the fastest solution for F is merely 2s..... and i had to do quite a bit of constant opt to fit the TL (tho i wasnt using pragmas, my fault ig). Please make TLs more lenient. I dont see why n needed to be so large. Is there some bad solution?

I liked E too, but i think the ideas behind it (and maybe even the problem) have occured before, because it looks standard, but if not, then nothing against it.

I would request round authors to kindly not put standard tasks in BC positions. Again, thanks for the round.

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

I opened problem C, turned off my laptop and went to play basketball( Thanks for the contest! A and B were cool.

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

Nice contest with ultra cool tester...

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

The ratings are updated (lightning fast rating changes).

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

My F code took about 1s in the AtCoder code test, but it took 4s in the CF code test (almost maximum case).

Again, I think it's best not to hold a contest until C++ is completely fixed. I think it will surely be ruined due to constant factor in the near future.

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

Bad round. Don't ever cook again.

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

I tried solving D with a different approach, getting wrong on pretest 2 but cannot find the error.

My approach was to split the given array again and again till it satisfy the three conditions, while iterating through the array:

  1. XOR of all elements within a subarray should be less than x;
  2. XOR of all elements after the current index should be less than x;
  3. OR of all subarray and the subarray formed by other (remaining elements) should be less than x;

as soon as any subarray satisfy these condition i increase the counter and reset ans variable to 0.

my approach might be wrong, I will be glad if anyone points out my mistake

here is my code

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

Is it possible to solve slight variation of B, where instead of max(sum) modulo 1e9+7 for an answer, max(sum modulo 1e9+7) (way harder, i think)

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

In problem F my $$$O(n \log^3 n)$$$ passes but $$$O(n \log^2 n)$$$ with unordered_map gets TL 7 🤡

252809693 and 252810082

can anyone explain why? is u_map constant that bad? I'm confused

(as a side note: choice of constraints in this problem is dumb, at least ML could've been 1024mb easily, but I would also decrease limit on $$$n$$$ and $$$q$$$ for $$$3 \cdot 10^5$$$ or something)

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

Why you didn't write what is permutation of length n in F's problem statement?

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

great clear and fresh que set 100

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

problem C mega sexy

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

Why am I disabled by admin?

Yesterday I signed up for my codeforces account FromOceans, Then I participated in a contest (it was "Codeforces Round #936 (Div. 2)"), and the next day I logged in with my account only to see "disabled by admin"?? I didn't cheat in the game (I can publish vscode's timeline if I need to), nor did I do any DDos attacks on the website?

I don't know where I'm supposed to post, and the account I signed up to explain doesn't seem to be able to post, only comment under existing posts.

If there are any errors in English grammar, please point them out.

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

C was great

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

My rating is higher than tourist

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

74TrAkToR About my problem of being rechecked in code https://mirror.codeforces.com/contest/1946/submission/252762903, most of which I have written in https://mirror.codeforces.com/contest/1914/submission/238131112, all the changes in which only add binary algorithm,In this problem, everyone is going to use this algorithm, this is just a coincidence, can you cancel my punishment

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

It was an amazing round!!!