AliShahali1382's blog

Codeforces Round #684 [Div1 and Div2]
By AliShahali1382, history, 2 years ago, In English
$$$~-\text{In the name of God}~-$$$

Hello Codeforces,

I'm glad to invite you to our first contest Codeforces Round #684 (Div. 1) and Codeforces Round #684 (Div. 2) which will be held at Nov/17/2020 17:35 (Moscow time) . The problems are invented and prepared by AliShahali1382, Mehrdad_Sohrabi, and Mohammad.H915. The round is rated for both divisions. You will be given 5 problems and 2 hours 15 minutes to solve them. I recommend you to read all the problems :)

Firstly I'd like to thank isaf27 for coordinating and reviewing the round, as well as helping with many different things.

Thanks for our testers 300iq, coderz189, Atreus, Shayan.P, Retired_cherry, morzer, BledDest, UnstoppableChillMachine, MAMBA, prabowo, WNG for testing and giving very helpful advice.

Finally, thanks to MikeMirzayanov for very nice and convenient Codeforces and Polygon platforms.

I hope you all will find the problems interesting. I wish you high scores and good luck!

Scoring distribution:

Div. 1: (500-500)-1250-1750-2500-2500

Div. 2: 500-1000-(750-750)-2000-2500

UPD : Editorial is out.

 
 
 
 
  • Vote: I like it
  • -337
  • Vote: I do not like it

Comments Comments (494)
| Write comment?
»
2 years ago, # |
  Vote: I like it +169 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +550 Vote: I do not like it

As a Monogon give me contribution.

→ Reply
»
2 years ago, # |
  Vote: I like it +146 Vote: I do not like it

Been waiting for these guys' contest for a long time now! Hope y'all ready for a fun contest :)

→ Reply
»
2 years ago, # |
  Vote: I like it -46 Vote: I do not like it

It's time to return an expert

→ Reply
»
2 years ago, # |
  Vote: I like it +242 Vote: I do not like it

As a student of the writers, i'm sure the contest will be good because they are geniuses.

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

    Yeah and we are forced to participate and upvote the blog and all of the comments XD

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

      yeah because they're teaching you to respect to older's contests

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

        they are one year older but yes youre right. : )

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

          sure I am. because I'm one year older than you too.

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

      :)))

      i'll see you next week

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

      It is fun to participate in our seniors contest. I hope it will be good. but there is a high chance that it will be bad. Hope it wont get unrated. XD

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

    are you a fan of FC barcelona?

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

      yes.

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

        i was also ,but after last three years it is very hard to support barca.SED LIFE

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

          as a fan, you have to support the team to get back to its good days. given the current situation and the change of manager, I believe in this team : )

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

      Yes

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

      As a problem setter : Two of problem seters is fan of barca :)

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Dogs are coming...

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is Retired_cherry a tester in soo many rounds? Is he really friends with so many contest writers? Hmm.. strange

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

    People with testing experience are often asked to be testers again.

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

    And I am testing the rounds without asking for you know what I want.

    → Reply
»
2 years ago, # |
  Vote: I like it +129 Vote: I do not like it

As a tester(Don't down vote!), I think it would be an interesting round!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So we have a subtask in problem A of Div2?

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone tell me why div3 is not happening ??

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does (750+750) mean , is it its a combination of 2 750 problems or just 1500 level problem ?

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Good luck bruh!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess I should say, OMG another Iranian round!!!

→ Reply
»
2 years ago, # |
  Vote: I like it -139 Vote: I do not like it

IslamForces

→ Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Ahsant! =)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

See you tomorrow night :)

(P.S UTC 14:35 = UTC+8 22:35)

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I am really excited to see what my friends have prepared after putting a lot of effort into it :)))

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I wish you write a lot of rounds from now

→ Reply
»
2 years ago, # |
  Vote: I like it -28 Vote: I do not like it

plz put some good easy problems for interview prep.

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

    For Interview type Questions goto leetcode,gfg or interviewbit.

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

      yeah bruh btw what is ur rating on codechef?

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

        I don't know what you will do with it but anyway, 1854.

        → Reply
»
2 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Good luck for GodForces!

→ Reply
»
2 years ago, # |
  Vote: I like it -47 Vote: I do not like it

−In the name of God −

Very happy to see that

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    god would be proud XD

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -31 Vote: I do not like it

      I'm pretty sure god never said anything about codeforces contests... these people talking in his name... must be frustrating for him

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

        You guys are talking about the God as a person!

        that's a pity

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -27 Vote: I do not like it

          Because he shouldn't be brought here in CF... what is the plus value of writing "In the name of God", this is literally believing without understanding

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

            Before everything we say "In the Name of God" that's the real believing

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              ← Rev. 2   Vote: I like it -8 Vote: I do not like it

              Whatever.

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

                Reply to your Rev.1

                no one did "targeting Non-Muslim people" and it isn't what Muslims do. what you said at the first was considered offensive (at least to some people's beliefs) and what you said now...

                look, it's obvious that you don't know Muslims and that's the reason you think like that

                "being an honest and good person" is what a real Muslim try to be and seriously you're wrong when you say "I'm pretty sure you like to do these things to get free Hassanate" because that's not what they're doing they're just defending their beliefs without expecting "Hassanate".

                I offer to finish talking about this in CF and research and read about other religions before commenting about them (not just talking about what we heard about them)

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

              Telling people what "real believing" is. Very clever.

              Did you notice that we no longer live in the Middle Ages?

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

                Actually, there're some people still living in the Middle Ages or even before that :)

                → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        we muslims do everything In the name of god so we never forget about god and be thankful that we can do this!!!

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

          everything?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -6 Vote: I do not like it

            Yup. There are even dua's regarding pissing, pooping, sex etc.

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

              This is racism!!! If you wanna know about islam you can go research! But saying things like this is too offensive

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

                what is the relation between racism and this? gheime haro tu masta nariz pls :<

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -9 Vote: I do not like it

                  kids pls dont come to adults conversations!

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

                  Because Islam is a race. /s

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

          Why not put some more exclamation marks behind it? Looks super clever.

          → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

Yeah...... Again, some of the medalists of the Iranian Computer Olympiad I wish we had this again!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Why did you give a negative rating to my comment? Did I say something bad?

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

      Laughing My Freaking A*s Off :)

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wa alaykumu s-salam AliShahali1382

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest *2

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

Peaceful Round !

→ Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I hope these guys would be as much good writers as they are great people and contestants.

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

    ‌But I hope these guys would be good writers.

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

    I think the hardest part of the questions is to understand the statements. be ready for it!!!

    → Reply
»
2 years ago, # |
  Vote: I like it -44 Vote: I do not like it

I am an atheist. Am i allowed to participate ?

→ Reply
»
2 years ago, # |
  Vote: I like it -140 Vote: I do not like it

Problem D's Title:

Spoiler

Problem E's Title:

Spoiler
→ Reply
»
2 years ago, # |
  Vote: I like it -67 Vote: I do not like it

why grey coder when comment anything gets down votes and whereas Red coders get up votes.

I have already negative contribution I am sure I will increase more from this comment as well.

→ Reply
»
2 years ago, # |
  Vote: I like it -38 Vote: I do not like it

I like the starting — In the name of God.

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

    no one cares

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      What causes a person to be toxic?

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

        This penetrating display of one's own faith. It's like waving your penis. Nobody wants to be bothered with it.

        → Reply
»
2 years ago, # |
  Vote: I like it -51 Vote: I do not like it

−In the name of God −

i am happy to see that, thank u ^^

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

what is polygon platform that is mentioned in post?(I am new I don't know, I am sorry if i asked wrong question!!)

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

    Polygon is a service to prepares programming problems and contests

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

    Polygon is the problem setting platform of CodeForces. There you can prepare problems. Write statement, checker code, validator code, generate testcases, add different types of solutions (ac, wa, tle etc) and run them. Explore ownself: Polygon

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great to see few consecutive rounds, I must say I started losing confidence in between last 2weeks gap, regular contests are fun in many aspects. Hopefully I would be able to increasing my rating, and most importantly enjoy solving the tasks.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have a doubt. I registered for this contest before last one as a candidate master but now i am expert and it is showing me as registered in div1. Can i participate in div1 if i want to do so by not unregistering myself from div1? And if i do so what about rating changes, will they be changed relative to div1 participants only?

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

    There is also some purple participants in div2 as well

    https://codeforces.com/contestRegistrants/1440?order=BY_RATING_DESC

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

      Yes, i meant in both cases (mine as well as vice-versa). Definitely, we have option of registering with correct divisions too. I wanted to ask whether there is any guideline or rule which we need to follow in such scenario or it completely depends on our wish?

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

        I would suggest that you participate in the correct division. The fact that is technically possible to register for the wrong one is a weak legitimation to do so. I mean, what rule would make sense to you?

        → Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Excited for this contest?please don't make it unrated.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Hey Guys, check https://gameofcodes.herokuapp.com for practicing weak and strong topics and much more!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is special about problem C?

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

    There will be an easy and a hard version of this problem.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish you high scores and good luck! Little wish to become blue:)

→ Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it -7 Vote: I do not like it

I think there will be two versions of problem C based on constraints. Which one is better to solve? 1.Solving C1 and C2 both at a time. 2.Solving C1 first and then move to C2.

→ Reply
»
2 years ago, # |
  Vote: I like it -35 Vote: I do not like it

newbie needs some contribution here.....

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

My first time participating in a Div 1 contest. Very Excited to participate in this round and also do let me know if there are any new strategies that I need to employ in Div1 contests xD :)

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

    Yeah just ask for strategies from your competitors, don't see how that can go wrong.

    PS: Jk ofc, most of the people here help each other for healthy competition.

    → Reply
»
2 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Guys actually this is my 2nd account my first account is red ....so i want to all to spam that upvote button and as a return gift i will wish for your best performance . PS: I am a GodMan ....my wishes are always fullfilled.

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

    solve atleast 3 problems and i will upvote you.

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

    Gave 5 contests and still a newbie XD, and says that he is red, ohh come onnnnn XD

    → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

best of luck everyone 5 min left!!!!!!!!!!!!!!!!!

→ Reply
»
2 years ago, # |
  Vote: I like it -29 Vote: I do not like it

is it rated ?

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

    Why we still here, just to suffer.....

    → Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

For Div2C2/Div1A2, I write more than 200+ lines of code to handle edge case when n or m is odd. Although I can think clear how to solve it, but it is too complicated and I give up. There must be some simpler ways, good question!

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

    I bricked on only one case where the grid is full filled and both n and m are odd, in that case I print the answer as nm + 2. Man it took me ages to compensate this 2, still dont know how do we do it :(

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

      You only need to solve the 2x2, 2x3 and 3x2 cases. You can then model all n, m into those cases. I bruteforced all costs of strings, made them into linear string instead of grid and tried implementing. I had this one bug in both n and m odd case which I couldn't find which made me mad and I gave up.

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

        I see some hints from other reviews, actually we just need to transform the last odd row and column to all zero first, then solve remaining grid by 2x2 as previous did

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

          that's exactly what I did.

          but the implementation costed a total of 90 mins (debugging time included)

          Accepted - XXL size code
          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Same. I wrote 446 lines of C related code (not counting code template) before giving up and moving to E (which seemed easier to implement).

    Some part of the cancer code
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, what I did was first make all the frame equal to zero (the corner, if needed to fix, is tricky), and then solve the rest of the matrix in blocks of 2. I had 4 functions — handle_4_ones calls handle_1_ones calls handle_2_ones calls handle_3_ones.

    What fucked me over was a bug in my corner case. But now I realize that if the 3 in the corner are all '1's, then we don't do anything, but if it isn't we can just make the whole square 0 in <= 3 moves (and not do if else 8 times and lose because of it :( ).

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

    I wrote 257 line of code but got wrong answer on pretest 1 just because i used 0 based indexing at the last second, now i feel like crying :(

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

    My approach:
    1. First of all I pushed all 1s to the bottom two rows
    2. Then pushed all 1s to the right bottom 4 cells
    3. Then handle the last four cells manually
    My submission https://codeforces.com/contest/1440/submission/98733831

    → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Easiest problem of contest: C (idea)

Hardest problem of contest: C (implementation)

Can anyone who used segment tree for E suggest how to handle the lazy updates? What information did you store in nodes? The second type of query was easy to handle and implement. The first, not so much.

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

    As array is nonincreasing updates are assign y on some suffix of [1;x]

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

      I stored the min, max, suffix sum at each node. Would that have been enough? I did eventually implement the lazy updates but it was linear and not constant due to bad implementation :(

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

      Can you please give some hints fo Query 2 of E?

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

for Div2D/Div1B After finding that "a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset" does not exist how to find if clique of size k exist or not? Anyone Please!

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the Pretest 2 of D2-C2 :(

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

    Maybe this one?

    1 
3 3
000
011
011

    My solution failed on this test case initially.

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

      No not this. I print the answer for this to be 4. One case as of now I am aware of when both n and m are odd and the grid is full filled where I print the answer as 2 more.

      For eg : 

      1
3 3 
111
111
111

      here I print the answer as 11 moves

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

    After I've solved this edge case I've managed to pass pretest 2

    1
3 2
11
11
01
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's a couple from Pretest2 of Div2-C2 that may be worth trying :

    2
2 3
011
000
2 3
111
100
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok thanks, actually my code runs fine on this (giving 2 and 4 moves respectively), but I found a case inpired from your test that breaks my code.

      1
2 3 
111
110

      Here I print 7 (not possible to constraints)

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a hint for D.2 E?

→ Reply
»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

took me 200 years to implement div2 c ...

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I wrote a 250 Line code for Div2C1 and still managed to fail on pretest 2 :sob:

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was div 2 E going to be solved using segment tree?

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

    Square Root Decomposition I suppose

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

      Nope. Segment tree that simulates binsearch, or treap. Kinda tough to implement.

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

    I solved it like that, yes. The hungry man takes from no more than $$$O(\log n)$$$ continuous segments and you can find those using the "binary search on segment tree in $$$O(\log n)$$$" technique.

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

      Nice can you give any refrence to "binary search on segment tree in $$$O(logn)$$$" please?

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

        I only know of this tutorial. Unfortunately it's only for Fenwick tree but the idea is the same — the tree already as a "binary-search-like" structure so you can descend in the tree instead of of making separate queries for each binary search step.

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

        for this problem I think you can do usual binary search (like middle=(x+n)/2) and the find range sum in [x,m] then accordingly change the range. but time complexity will be $$$O(n(logn)^2)$$$ but time limit is 3 sec so should be sufficient..

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

          You can't, because every query in the problem requires $$$O(\log n)$$$ such binary searches.

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

        "Seg Descend" might be helpful, though I haven't solved the problem yet so i don't know for sure. You can find it in this page https://cp-algorithms.com/data_structures/segment_tree.html under the heading "Searching for the first element greater than a given amount".

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

      Can you please elaborate more on the part "The hungry man takes from no more than $$$O(logn)$$$ continuous segments".

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

        When he has bought food in some segment and can't buy food at the next one, the amount of money he has must have been at least halved since the start of the segment (because the array is nonincreasing and the updates maintain that).Oh,I guess it's actually $$$\log C$$$, but it's not very important.

        → Reply
»
2 years ago, # |
  Vote: I like it +197 Vote: I do not like it

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

My fingers are hurting after writing code for div2 C.

→ Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Am I the only one who felt that problem C1 (Div-2) was totally hardcore implementation problem?

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

    I don't think C1 was. But, definitely C2 imo

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

    I don't think so. https://codeforces.com/contest/1440/submission/98728859

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

      Maybe you can take a loot at jiangly's submission and see that it is not that long, but still dumb implement problem.

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

        yeah it 's for sure that it is not that long if we see jiangly submission , jiangly writes beautiful implementation for each and every problems . But newbies like me writes terrible code see around 388 lines — spaces . Submission link : https://codeforces.com/contest/1440/submission/98743493 It is really nice to see someone mentions the highness of jiangly which in my mind is one of the best coder in the world right now . Sorry jiangly for mentioning your name and an annoying notification of mine :)

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

          Yep jiamgly made me learn. Everything I finishing upsolving I always look at jiangly's submission.

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it +19 Vote: I do not like it

          Yes, indeed!

          Does there really exist anyone who don't love jiangly-chan?

          jiangly-chan, we love you! <3 <3 <3 <3

          Just join "jiangly fan-club"! ;P

          btw you can check my submission also

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

            How to join that club ? I don't know that they will gonna take a pupil like me in their club but anyway i have learnt a lot from jiangly coding . The way of writing inner lambda functions in main and lots of simple coding style too . Only thing i don't do is writing std:: again and again . I respect and love jiangly way of writing code a lot (infinite times repeat) . I wish that one day jiangly be the best coder in the world . Sorry if anyone finds my words and complements annoying in advance .

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

              It seems that the club is not in the "Organizations" of Codeforces.

              But you can create a brand new organization named "jiangly fan-club" for sure! (just like Ildar Gainullin fun-club, btw Ildar Gainullin is 300iq)

              I'm sure lots of coders who learnt from jiangly's code will be glad to join!

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

            Its too short!

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

          Ever since I found jiangly, I never looked others' code :) (no offense to other people who write beautiful code)

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

I am an idiot. I debugged C2 like crazy, submitted in the last 20 seconds, and forgot to submit C1 :(

Btw, great problem — NO IF ELSE IN C2, NO CASES, REALLY EASY IMPLEMENTATION.

obviously now when I look at it I could have saved a lot of the code, but still...

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

    I did a similar approach in my implementation. I still don't know why I got RTE on pretest 2. I spent the last 10 minutes trying to figure that out.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, isn't finding a clique of size k NP-complete? I lost my mind after reading D cuz of that and not to mention I left C behind long long ago XD

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

    I think you can have a clique if and only if you can solve the second task of the problem with k-1. And I think you can do the transition somehow..

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

      Then someone please explain why the problemsetter hasn't been given a million dollars to have shown a poly time solution to an NP complete problem.

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

    There is bron-kerbosch algo, but I think complexity does not allow it to run on 1e5 vertex.

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

      the trick was realizing that for having a clique of size k, you need at least k * (k — 1) vertices

      → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think extremely easy idea but extremely heavy implementation problems should be reduced (as least just give m,n even).

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

B and C were so uninteresting. You could easily see the idea (or at least the pattern) in both of them but it all came down to who could implement them faster.

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

    I mean... you're right about C but B was pretty easy to implement... You just sum up elements in a single (kind of-)simple for loop.

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

      I don't think it was very easy to see that, took me 10 minutes to observe it and then another 20 minutes to debug my code. Also, I think C was very implementation heavy, some typos and you will have to spend another 30 minutes figuring it out. PS: my personal opinion.

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

        I never said B was easy... I was it was pretty easy to implement. I mean, the shortest and most simple implementation for C was at least 50 lines of code (or probably closer to 100).

        This is my implementation of B:

        B-solution

        You can't say a problem like this is implementation heavy.

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

    I think C was really braindead. In B I needed like 20 minutes to switch n and k. I think this is the first problem where the number of the partial thing is named n, not the number of the whole thing. Same goes with k, it is usually used for a property of a part. Misleading nameing.

    → Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Why did div1A have subtasks? In one operation, we always cut off one cell from the bottom/right border until we get 2x2 and there are just 4 distinct operations there. I don't see a simpler solution for the first subtask.

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

    Fix each cell individually in 3 steps.

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

      Wasn't the same logic used in the hard subtask also? Each cell can be fixed in 1 step and we are left with just 2 corner cells which require atmost 3 steps.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      Fix each cell individually in 1 step.

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

    Still the number of submission in div2 for the same problem were 2500(easy)-700(hard). People must have found some logic for 3*n*m

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

    For subtask one you can change one cell of each 2 * 2 in 3 operasion such that other cells do not change

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

    except last row, all cells in 1 operation. total=(n*m-m). for last row, we can chang each cell in atmost 3 operations. total=(n*m-m)+m*3 = n*m+2*m. this can work for both subtasks?? is the total correct?

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

      Use the idea for "all but the last row" with columns too. Then you're left with a 2x2 grid.

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

How to solve Div2.D / Div1,B ?, ty.

→ Reply
»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

....?? Why NP-Complete problem comes here?

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

    From the problem statement it kinda follows that it's not NP-complete if you can instead answer the other question.

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

      Can you please tell me just the idea. After finding that "a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset" does not exist how to find if clique of size k exist or not?

      → Reply
»
2 years ago, # |
  Vote: I like it +118 Vote: I do not like it

I'm not gonna forgive you 3 seconds TL in E :<

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Make sure you have amazing typing speed with precision before solving Div2. C

→ Reply
»
2 years ago, # |
  Vote: I like it +629 Vote: I do not like it

Do you hate your participants or what? What the hell is wrong with these limitations? Why in every problem I have to optimize everything? Ideas are maybe fine, but you have killed this round with your limitations.

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

    Looking at the standings atm I don't know if I should be afraid of you or of an author...

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

    Do you also have to guess the hashset implementation which passes the tests? Fuck you guys, for real.

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

      +1

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

      As a mere blue coder, I know something is wrong when I see Um_nik TLE 2nd problem in div1.

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

      And I thought I was pissed off when carefully implementing clique checking optimised for this problem, lol.

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

      +1

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

      The fact that you could not pass test 57 test is not a reason to say every word that you want, I did not answer yesterday because you were angry, but really a pity for those who are LGM and for example can be a good role model for others, do not value himself.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -75 Vote: I do not like it

        Fuck you. Today I'm not angry, will you answer?

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

          Why did I really waste my time writing the previous comment? Keep polite and thank you for proving to me that I was not wrong about you :) ;)

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 4   Vote: I like it -10 Vote: I do not like it

          You are clearly an extremely talented programmer um_nik, but that does not give you the right to treat people like this. Your language and rudeness is completely unnecessary.

          Edit: downvote me all you want — if the guy goes around telling people to f**k themselves because he TLEd on a question, that’s rude, disrespectful of the writers who gave up their time, and just plain unnecessary. No amount of rating points makes that ok behaviour.

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

    I support you. Especially for Div1B, I think 1 sec for this problem is terrible even with $$$O(n \sqrt{n})$$$ without hashsets or something. I always consider quitting Cf with writers who give us problems with such TL/MLs...

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

      I think my recent submission 98748728 is $$$O(m sqrt(m))$$$ without hashset and got TL :(

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

        It's not. Tests 56 and 57 are against solutions like yours with wrong complexity. Tests 25, 58 and others are made against $$$O(m\sqrt{m})$$$ solutions with too high constant and/or log factor.

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

          Ah, my submission is wrong with small K (maybe N^2/K). Sorry for confusing

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

          By the latter sentence, you mean pretests did not have maximum tests? With such tight TL?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -20 Vote: I do not like it

            There are tests that look like maximum tests, but the ratio between runtimes of any 2 tests can, due to implementation details, be different for 2 solutions with the same complexity. Pretests probably have tests that caused higher runtimes on most authors' solutions, while on some other solutions tests like 25, 29 and 58 can cause higher runtimes. Or maybe I'm wrong and tests 25 and 29 did cause higher runtimes than tests 6, 7, 9 and 12 on authors' solutions but for some different reason they decided to not put them in pretests.

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

          I think that you are just bullshitting me. I used different hashset and got AC now. I was having TL 57. Did different hashset magically fix my complexity?

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

            For some reason test 57 caused an $$$O(n^2)$$$ blow up on your hash table. Changing your hash function from (v * A + u + B) % P; to (v * A + u * B) % P; gave AC: 98754739

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

              For fixed v, if u are near each other hashes are also near each other.

              As hash table is already 50% full, and chaining is done by increasing index by one you get a blow up.

              Increasing size of hash to 100m from 2m ( 98748122 ) or changing chain step to something like P/3 ( 98756686 ) also passes.

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

              mmm cool)

              → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -42 Vote: I do not like it

            The official solution was O(n.sqrt(n)) without any hashmap or something like that.

            → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Congrats Errichto — LGM

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C2?

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

    In the easy version, I guess you have changed each cell with 3 operations if needed. To optimize this, we can first modify all the cells in the first n-2 rows with one operation for each by using either

    XO

    OO

    or

    OX

    OO

    -shaped modification.

    For the first m-2 columns in the rest 2 rows, to modify arr[n-1][i] and arr[n][i] into "correct" entries, just do one operation depending on the current entries on arr[n-1][i] and arr[n][i]. You may divide this part into 4 cases.

    As for the rest 2 columns in the rest 2 rows, similarly, do operations depending on the current entries on arr[n-1][m-1], arr[n-1][m], arr[n][m-1] and arr[n][m]. You may divide this part into 16 cases. Each case can be done in 4 operations.

    → Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Opinion: Hard problems are interesting but increasing of difficulty are kind of imbalanced, and those easy problems are not good.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

(memed12dc8d7b93006a2.jpg)

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

    Can relate xd. I spent something like 40 minutes on this and didn't get this through xd. In the end I got the idea, but it is quite messy to code.

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

      here is my approach for C2

      1) Eliminate first n-1 rows
      2) Eliminate first m-1 cols of last 2 rows
      3) Bruteforce last 2x2 box
      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yeah, that's what I was coding in last minute, but lacked a bit of time. Quite consoling to see a rather clean solution with provable $$$nm$$$ bound after coding a lot of shitty things before and coming up with a few solutions that would require something like $$$nm+3$$$ operations.

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

          Lmao, this ad-hoc problem is "fun". But I think the lower bound is smaller $$$n \times m$$$.

          And how were you as a red-ranker seeing the first problem of the contest is that heavy implementation problem :(((

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

            Looking at other people's comments, this problem appears to be anything but fun, and obviously it isn't fun at all to have a really heavy implementation problem being problem A.

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

              That is why "fun" is inside the quote :D

              → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

My code for problem C went for around 200 lines, could not even debug, why such implementation heavy problem with no thinking required

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

    It's more like how you do the implementation.
    I made 3 separate funtions to handle the bottom-right 2x2 square :
    handle1() : when number of ones is 1.
    handle2() : when number of ones are 2.
    handle3() : when number of ones are 3.

    I completely implemented each case in handle1();
    For handle2() and handle3(), I converted the 2x2 matrix, with some operations to case which handle1() does and then call handle1().
    Although it helps in a little bit easy implementation but still the code was long

    → Reply
»
2 years ago, # |
  Vote: I like it +79 Vote: I do not like it

My story with div1C: figure out what to do quickly, start writing a segtree... keep writing a segtree... finally finished 20 minutes before the end. Sample gives very wrong answers, so I'm debugging like crazy, but I'm getting nonsense answers. Check how much time is left... 2 minutes, no point trying. OH WAIT I'm getting very negative sums in the debug output, is there something wrong with my "push an update deeper in the segtree" function? Yeah, I flipped some range bounds and was updating sum[l:r] to $$$y (l-r)$$$ instead of $$$y(r-l)$$$. Quickly I deleted debug couts and managed to submit without even testing on the sample. AC on pretests, less than 1 minute left.

Top 10 anime fight turnarounds.

For the record, the main idea in that problem is to repeat "find first A[z] <= y, find largest sum A[z:new_x] <= y, subtract the sum from y and make x = new_x" because that decreases y more than twice.

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

    How do you know that making the change x = new_x won't be appearing O(n) times every query???

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

      The last few words answer that.

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

      Because it will decrease y at least twice. So it is log(y)