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

Автор AliShahali1382, история, 4 года назад, По-английски
$$$~-\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 17.11.2020 17:35 (Московское время) . 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.

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

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

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

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

As a Monogon give me contribution.

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

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

»
4 года назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

It's time to return an expert

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

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

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

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

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

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

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

So we have a subtask in problem A of Div2?

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

Can someone tell me why div3 is not happening ??

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

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

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

Good luck bruh!

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

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

»
4 года назад, # |
  Проголосовать: нравится -139 Проголосовать: не нравится

IslamForces

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

Ahsant! =)

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

See you tomorrow night :)

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

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

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

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

I wish you write a lot of rounds from now

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

plz put some good easy problems for interview prep.

»
4 года назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

Good luck for GodForces!

»
4 года назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

−In the name of God −

Very happy to see that

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

    god would be proud XD

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

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

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

        You guys are talking about the God as a person!

        that's a pity

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

          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

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

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

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

              Whatever.

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

                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)

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

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

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

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

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

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

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

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

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

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

Wa alaykumu s-salam AliShahali1382

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

nice contest *2

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

Peaceful Round !

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

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

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

I am an atheist. Am i allowed to participate ?

»
4 года назад, # |
  Проголосовать: нравится -140 Проголосовать: не нравится

Problem D's Title:

Spoiler

Problem E's Title:

Spoiler
»
4 года назад, # |
  Проголосовать: нравится -67 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

I like the starting — In the name of God.

»
4 года назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

−In the name of God −

i am happy to see that, thank u ^^

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

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

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

    Polygon is a service to prepares programming problems and contests

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

    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

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

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.

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

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?

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

    There is also some purple participants in div2 as well

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

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

      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?

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

        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?

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

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

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

what is special about problem C?

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

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

»
4 года назад, # |
Rev. 6   Проголосовать: нравится -7 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

newbie needs some contribution here.....

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

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

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

    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.

»
4 года назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

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.

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

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

»
4 года назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

is it rated ?

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

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!

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

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

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

      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.

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

        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

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

          that's exactly what I did.

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

          Accepted - XXL size code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

    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.net/contest/1440/submission/98733831

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

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.

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

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

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

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

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

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

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

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!

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

What is the Pretest 2 of D2-C2 :(

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

    Maybe this one?

    1 
    3 3
    000
    011
    011
    

    My solution failed on this test case initially.

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

      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

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

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

    1
    3 2
    11
    11
    01
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    2
    2 3
    011
    000
    2 3
    111
    100
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

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

Can someone give a hint for D.2 E?

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

took me 200 years to implement div2 c ...

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

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

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

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

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

    Square Root Decomposition I suppose

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

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

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

    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.

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

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

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

        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.

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

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

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

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

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

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

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

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

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

        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.

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

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

My fingers are hurting after writing code for div2 C.

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

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

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

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

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

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

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

        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.net/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 :)

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

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

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

          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

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

            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 .

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

              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!

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

            Its too short!

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

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

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

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

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

    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.

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

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

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

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

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

      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.

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

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

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

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

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

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

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

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.

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

    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.

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

      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.

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

        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.

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

    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.

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

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.

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

    Fix each cell individually in 3 steps.

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

      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.

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

      Fix each cell individually in 1 step.

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

    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

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

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

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

    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?

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

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

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

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

»
4 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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

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

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

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

      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?

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

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

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

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

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

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.

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

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

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

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

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

      +1

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

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

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

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

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

      +1

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

      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.

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

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

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

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

          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.

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

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

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

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

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

        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.

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

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

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

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

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

            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.

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

          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?

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

            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

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

              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.

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

              mmm cool)

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

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

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

Congrats Errichto — LGM

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

How to solve C2?

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

    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.

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

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

»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

(memed12dc8d7b93006a2.jpg)

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

    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.

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

      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
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

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

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

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

            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.

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

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

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

    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

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

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.

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

What is the point of Div1C? It is not segment tree educational contest LOL

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

    To show people that apparently $$$O(n \log^2 n)$$$ with lazy seg tree TLEs in Java. 98740494

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

    +100

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

    It wasn't an "implement standard segtree" problem though. It was implementation-heavy but also needed some clever ideas and the segtree was unusual (I think I've never written this one specifically, although I've written every part of it in some problem). I wouldn't place it in an educational round.

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

      Are this ideas really that clever for D1C?

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

        I see it similarly to last contest's div1D: you can easily spot the main ideas, but you can also easily miss them too.

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

      You can just throw in a lazy range set seg tree and then write a binary search on it and then make some constant optimizations if necessary. I'm not sure if I'd place this in any round.

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

        That doesn't tell me anything. Can you describe in more detail a solution that uses only what you just mentioned?

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

          So queries of type 1 are just a range set, as the array is strictly decreasing. You can binary search to find the starting point. Queries of type 2 can be processed by repeatedly finding the first element less than the current money left (binary search), and then finding the length of the longest segment with a sum less than the current money left (another binary search).

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

            Except now you have $$$log^3$$$ solution and get TL.

            Binary descent over segment tree is still pretty standard, but definitely harder than binary search.

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

              Sorry just asking, but why is that log^3. I tried to implement that during contest, need to know what is wrong...

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

                You need to visit $$$log$$$ segments of shops at most.

                If you do binary search (log) over segment tree sum (log) that would be another $$$log^2$$$.

                You can combine the last two using descent over segment tree.

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

            repeatedly finding

            And that's standard?

            binary search

            Combined this gives $$$O(\log^3)$$$ time complexity per query, right? That should be way above TL even with constant optimisations.

            When I said "only what you just mentioned", I meant only. The problem sucks because it's too implementation-heavy in a contest that's too implementation-heavy. It's not an educational contest problem like just segtree+binsearch.

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

              You can binary search in log time. I'd consider that to be standard (or at least suitable in an educational round).

              In addition, it's not like educational contests can't have observations, and I feel like observations where you notice the values halfen each time is educational.

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

                That's one of the logs. Another comes from the segtree and another from the repeatedly finding.

                It seems you don't understand that all problems aren't solved with catch-all terms like binsearch or segtree.

                In addition, it's not like educational contests can't have observations

                Standard observations that you can find often in contest problems. Otherwise there's no distinction between an educational contest and a regular one.

                and I feel like observations where you notice the values halfen each time is educational

                By that logic, good problems belong in educational contests because good problems are often "educational" in some way.

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

                  Binary searching on segtree in log time removes the segtree log.

                  I think it makes more sense to place this problem in an educational contest than a div 1. I only see one clever idea not "clever ideas"

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

                  Binary search on segtree is log^2, using segtree queries in a way that replaces binsearch is something different. Specifically, it's not binsearch. Also, that's not any more of a standard idea than taking O(log) segments.

                  In last contest's div1D1, I see one clever idea: that if we look at the unique most common value v in [l, N), we can move the right endpoint of this range to the left and as soon as we reach [l, r) such that some other value occurs exactly as many times as v in [l, r), the answer is at least r-l. The rest is implementation and prefix sums. By your logic, that should go to an educational contest, yet nobody complained about that. Mysterious!

                  I only see one clever idea

                  No, you see zero. "You can just throw in a lazy range set seg tree and then write a binary search on it and then make some constant optimizations if necessary."

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

    Huh? Don't you need an idea that we'll take at most $$$\log$$$ intervals? That's something.

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

Why is time limit only 1 second in Div1B.I hope your intended solution doesn't use unordered map with hash.

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

It was one of the most bullshit contests I've ever seen!! :|

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

"You cannot vote twice. You have already voted for this topic before." So sad :(

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

Me: How to get motivation for implementing problems like C1?
Me after reading comments: you don't need to waste your time on such problems!

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

.

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

div2 c1 was literally nothing but kharkari, WTF!!!!!

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

i found a peculiar occurrence.

Why i can't hack this submission. Its time complexity is $$$O(2^n)$$$

But i failed to hack it. Here's the hack

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

    No, the complexity is linear.

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

      Why is it linear?

      The code even can't run out the answer on my local computer.

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

        I accidentally hit delete on my last comment which had the proof in hurry to edit something :( It is basically iterating through recursion visiting each position twice.

        At each step i, you do two calls to f(i+1), both of which are linear. If you were iterating through all possibilities of changing the current position to 1 or 0 with respect to values at all other position j, then you'd have exponential complexity.

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

          if you print anything inside the function it will be printed 2^n times, i don't think TC is linear, see this ideone code, for n = 5, 'check' is printed 31 times

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

            It should have been exponential. It appears that the compiler optimizes the repeated calls to f(i+1) so they are not called twice. If you print something inside it, then the function has to do that and is not optimized.

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

        My bad, you're right :( It is indeed exponential. I think the compiler optimises the two calls to func(i+1) to just one call. You'll have to probably look at the disassembly to find out if that's right. Locally, you might be using debugging flags and other stuff which prohibit compiler optimisations. I don't really know at this point after I realised I'm mistaken. Sorry for having wasted your time.

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

          Yep, just checked on godbolt. Disassembly is different for compiling with optimisation flags (as expected). The optimiser knows that both calls produces the same result and so instead of doing two calls, only one call is done (which explains the linear time and why the code passes).

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

you are nothing but some "oghdei be manaye vaghei" people:'(

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

What the heck were Div2C1/C2 ? First of all it took me an eternity to figure out how to write the clean code. Then after I implemented them there were a few bugs with less then 2 min remaining. Solved all the bugs 1 min after contest ends. This is where it hurt the most. What is the point even?

If anyone is interested in clean code :

Worst problem ever
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    It is truly the worst problem in a while. I thought this kind of problem only show on earlier contest :(

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

    Imagine you were in div1 and the first problem you saw is this :(

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

    Exactly. I tried to solve C2 but couldn't come up with an idea in 30 mins, started to write code for C1, and it took eternity for me to debug. It felt such a waste of my time. I never expected such bullshit problems from CF contests.

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

    Exactly the same thing happened to me. It was really easy to find the solution, but the implementation part was too long for a 2hr 15min contest. These questions make the contest less interesting.

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

Anyone know how to view delta on the scoreboard?

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

Div 2 C1 had a pretty short implementation as compared to C2.

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

Hi, Im a beginner can anybody help me out? For solving div2 c1 my idea was that if you have a block containing 1 then i form a 2*2 square around it and do 3 operations(all other squares are inverted 2 times while arr[i][j] thrice. Its showing that my answer is wrong as apparently there are some tiles remaining 1. 98733171

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

    Since you are beginner i want to tell you without down-voting that you can use spoiler for hiding the code else it pollutes comment section.

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

    This is really annoying, can anyone help me please, i just cant figure it out

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

      I guess you need to either start cycle from 0 and call solve(i+1, j+1, ...) or leave it as is and check condition if(arr[i-1][j-1]=='0')

      cout<<(3*cnt)<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){

               if(arr[i][j]=='0') continue;
               solve(i,j,n,m);
             }
          }
      
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Change arr[i][j] in both nested loops to arr[i-1][j-1], since you are using 1-indexing.

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

This contest is an absolute mess. It should be unrated. Problems A1-A2 are totally about implementation and take much longer than usually A-problems take. Problem B is a complete randomness. I got 889 ms on pretests and had no idea, should I optimize it further (and lose 50+ more points) or not. Finally, it didn't passed system testing. And it's not about wrong complexity. Problems like this one should never appear in CF rounds. Why did you put 1 second TL to this problem? My performance today is a total shit and there were days with even worse performances, but only today I felt like I'm wasting my time taking part in ugly low quality contest.

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

    I wish "these problems suck" was a reason to unrate, I'd probably still have better rating after this contest.

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

     I got +250 in last Div.2 (it is unrated) and +100 here, so I agree with all your thoughts except making round unrated

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

    "And it's not about wrong complexity."

    Actually, in your case it was. Your solution works in $$$O(\frac{m^2}{k})$$$.

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

      Actually it was $$$O(\frac{n \cdot m}{k})$$$, but it totally sucks anyway (fixed it in upsolving and it is still 400+ ms of time with 1 second of TL). But now the question is: why did this solution pass pretests with time comparable to others?

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

        Because in this problem, truly hard tests aren't large tests, they must be specifically crafted to even remotely look like they have many cliques. Even then, a solution with "break after finding a clique" can pass a test with a clique, a solution with "break clique checking when you see that this isn't a clique" passes tests with sparse graphs and so on. Multiple test cases don't help avoid TL either. I'm surprised full tests aren't super weak, actually.

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

    takbiiiiiiiiiiiir

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

    Contest was ok, except again authors did not balance things. B was shit, agree, but C was fine. A had bad scoring (500 for A2 seems pretty bad, comparing to effort): after implementing A2 and passed pretests I had to implement stress to make sure all works fine.

    Pretests for B seems fine too, if you had 0.889 ms. Nobody promises you max test there, so guessing game is always a part of it. But looking at the final scoreboard it seems that problem as B is a little overkill — surprised that all of the round testers did not really see that (800 AC for A2 and then 250 AC for B, 221 for C: very shitty balance).

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

I reduced 1439B - Graph Subset Problem to "given $$$n$$$ sets of nodes, check if they are cliques" (offline). Is it possible to do that in $$$O(n\sqrt{n})$$$ or less?

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

    Apparently, there is an upper bound of $$$O(m/k)$$$ sets of nodes to check. So checking naively requires $$$O(mk\log{k})$$$ and $$$k = O(\sqrt{n})$$$.

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

my solution to problems C1 and C2: https://www.youtube.com/watch?v=qHVt2ulsVxY

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

me after seeing problem C(still couldn't implement it right though)

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

I have heard that it is possible to do D using some dp (quite sad :(), so I will just tease you that there is a beautiful mathematical solution that works in $$$O(n^2)$$$ and starts from proving that there are $$$(n+1)^{m-1}(n+1-m)$$$ valid sequences.

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

    it has O(n.log) solution

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

    this O(n^2) solution can also be optimized to O(n.log(n)) with fft. Shayan.P found a solution in the testing and here is his code:

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

div1 B with set --> TLE on test 6

div1 B with unordered_set --> Accept

... What the...

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

Tip for authors who want to write Div 1 problems:

  1. write an easy problem about the tree

  2. change the building process like the problem E does.

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

U SuCk

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

Haha I'm glad that I was participating in div.1 so I was traumatized from the beginning of the contest And div.1a/div2c wins the prize for the problem with most overly complicated pointless code

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

What an ugly problemset!

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

I solved both A and B in Div 2 for the first time today

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

Super frustrating contest. To lose 100 rating points over a messy implementation question hurts, especially after I would have gone up 150 on Friday but then it was made unrated. Any question is fair game but I feel the ratings will be all over the place after this, and will take a while to settle back to where they should be.

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

codeforces div1 rounds should be eliminated. the last time I was happy about solving a problem was more than two years ago

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

so nice especially b/c div.1

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

So I took a long break this year and decided to participate for the first time after 10 months.

Starting with A, I immediately realized that we could fix a 2x2 square with at most 4 moves. Proceeded to make a few WAs because I didn't handle the case where the number of rows/columns was odd. Problem A these days is no longer easy, I was thinking.

Moved to B and got the idea to solve the neighbor case quite easily. Wrote a dumb code to check a clique for every possible potential nodes. TLE pretest 7. Looked promising but there must be some smart observations here. Tried a few different approaches and got WAs. Started to got frustrated and threw in some random pruning. Passed pretests with a 998ms running time. I knew it would eventually failed system tests but couldn't come up with anything better. After reading a couple of accepted submissions, it seems to be about how to write a fast clique checking part. Am I missing anything or the 2 parts of this problem are completely irrelevant?

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

    I had the exact same idea for A, and also failed on case where the rows and colomn are odd. How do we do it ?

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

      Assume you have an odd number of rows. For each cell of the last row, you can fix it by one operation (itself + 2 other cells from the second last row). Do the same for the last column if needed then we can have an even number of rows and columns.

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

    They're not unrelated at least in my solution, the neighbour case helps you. We're deleting vertices with less than $$$K$$$ neighbours. If a deleted vertex has exactly $$$K-1$$$ neighbours, you get the only clique candidate that contains this vertex and none of previously deleted vertices. You either end up with a valid subset or at most $$$N/(K-1)$$$ clique candidates, since finding a clique candidate = deleting $$$K-1$$$ edges.

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

    just change set to unordered_set in problem B, it will pass.

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

This a boring round for most participants rating 1900-2200 Here is no Algo no Data structure. Just if else

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

    Div 2E is lazy segtree how much more Data Structure do you want m8

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

      You can downvote on my comments, but it can’t change the fact that this contest is getting more and more downvotes.

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

Where are the guys who were excited for this contest ?

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

This was our first experience of designing a contest, and I really apologize for the shortcomings. As someone who is the designer of problem C, I have to apologize again for this question, because unfortunately I saw that many people were annoyed by this problem, and this may have been due to the different way (the main code was 70 lines) Unfortunately, no one of testers mentioned this question

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

    yeah, some of my friends found a really neat solution ("push" all the elements into a corner) which made the code a lot easier and shorter, but the brute force approach is easier to come up with but WAY worse to implement, none of the contest org's fault just a kinda unfortunate situation

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

    C in which division? kek

    One way to maybe improve div1C would be making it an interactive problem where you can query subarray sums; div2C just sucks in any remotely close form and you might as well replace it by a different problem with an operation that's its own inversion.

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

    Thank god, I skipped this contest after seeing my 200lines of code, which eventually failed when I submitted after the contest. People are very excited when giving a new contest, I think this kind of question overkills the excitement.

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

    First experience ? Huh . You better leaved codeforces forever in name of god.

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

      I do not understand the connection between your comment and my comment. let's respect each other's opinions

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

Lesson learned today- Reserve your upvote/downvote until after the contest has finished.

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

Everyone is a bit too angry in the comments. I'll give a calm (but not positive) feedback.

D1A: Bad problem. Both the statement and the solution are not interesting. It is immediate to reduce to the case $$$n=m=2$$$ (which must be solvable because so it says the statement) and then the case $$$n=m=2$$$ is only boring. Furthermore, it is boring to implement.

D1B: The problem is nice (but quite standard), the time-limit is very wrong (assuming that the official solution is $$$O(n\sqrt{n})$$$ with hashsets). In my opinion, this could be easily avoided (in the sense that was also pretty clear a priori, not only after the contest... it is sufficient to compute $$$200,000^{\frac32}\approx 9\cdot 10^7$$$ and multiply by $$$10$$$ because of the hashsets to realize that a larger time-limit would be more appropriate).

D1C: Ok problem. The main idea is nice but then the implementation is quite heavy. I realized the fundamental observation ($$$O(log(n))$$$ consecutive intervals) almost immediately and then I spent 45 minutes implementing it.

D1D: The statement is nice and the problem seems cool, sadly I did not have much time to think about this.

D1E: Not read.

The contest would have been much better with a different problem A and with an appropriate time-limit in B. In any case, thanks to the authors.

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

    The other problems might be good. However, the first problems annoy people and most people would not have time to read or even solve those problems.

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

    I'll put my 2 cents.

    My D1B doesn't require a hashset, I checked edges using std::binary_search, 420ms. It doesn't imply that the TL is actually good, of course it's still too tight, according to the standings. It doesn't cut $$$m\sqrt{m}$$$ from $$$m^2/k$$$, it cuts good $$$m\sqrt{m}$$$ from all others, and what is good is hard to know in advance.

    D1C is imo an instant straightforward idea and then boring implementation. I rushed on this problem using energy from how boring it was (and therefore my motivation was to submit it and then forget it), I was lucky to get "pretests passed" (and then ac) with no debugging, once it compiled it was ready. I'm very surprised, this particular case is a rare phenomenon.

    D1D is "erm, okay, parking function strikes back", so I decided to go to D1E.

    In D1E I wrote a simple code to see the picture for $$$0\leq x, y\leq 50$$$, saw the Sierpinsky picture, then found out how the Grundy is calculated, and then was writing it till the end. I liked the problem, however I still haven't manage to make my lca function work fast.

    Long story short, I liked E, didn't like A (a matter of taste I guess), didn't like B (idea is easy, tl is bad), didn't like C (idea is easy, implementing is boring), can't say about D.

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

      Parking function is definitely among my favourite tricks, always appreciate parking function problem <3

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

        Swistakk Whats this "Parking Function"? Any resources on it?

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

          It's basically what this statement describes. Sequences of length $$$n$$$ such that you have $$$n$$$ cars behaving as described in the statement if everybody comes from left to right where in the end everybody finds a place. There are $$$(n+1)^{n-1}$$$ of them and there is a very tricky and beautiful combinatorial proof which I've read during this contest to refresh my memory, but only resource I know is in Polish (http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2011/02/01/Jak_zaparkowac_samochod_/). In short, you add a fake $$$(n+1)$$$-th parking place and glue both ends after adding it (so parking is circular with one fake place) and you consider circular rotations on it and argue that in each class of circular rotations (consisting of n+1 sequences) there is only one good (one where empty place is the fake one), so number of parking functions is $$$(n+1)^n \cdot \frac{1}{n+1} = (n+1)^{n-1}$$$. This gives a lot of insight into solving D

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

When the ratings will get updated mehnnn.....

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

    In order to carry out the ritual correctly it is necessary to ask for the editorial first!

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

I would like more problems like Div2C because ICPC is coming and it has a lot of heavy implementation problems, I think the problem is a nice combination of thinking and implementation.

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

glad I waited until the end of the contest to rate the announcement! Div2C had no point and literally broke my fingers. I wish something similar happens to the problem designers :>

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

I want to give some mostly positive feedback about this contest. I think the problems were pretty nice, but a little standard/implementation heavy and incorrectly ordered; I think the difficulty ordering for me was ADBEC. The fact that the difficulty was off also meant people didn't get the chance to read the interesting problems near the end of the contest. The time limits were also rather tight, though I didn't run into much trouble.

D1A: It's fine for an A, it's not that exciting, but that's fine.

D1B: As far as I can see, most of the people complaining about failing systests on D1B have the wrong complexity (TLE on test 57 because $$$O(nm/k)$$$). The time limit is quite tight for an N sqrt(N) algorithm, it took me 1/5 of TL and I used fast randomized pbds hash map. I think it would've been nice to let N sqrt(N) log(N) pass as well.

D1C: This was a fine segtree problem, I haven't seen such DS in a while and I think it's fun. The log(n) disjoint intervals observation is pretty cool, too. I might be miscalibrated, but I think this type of segtree should be harder than problem 3/5 though, it should be at least problem 4/5.

D1D: With the bounds as given, I found it to be a straightforward DP based on reversing time. However, with more math, you can definitely solve this problem with larger bounds, which could've been a more interesting hard problem. I ran pretty close to the time limit because I didn't use Barrett reduction, but maybe that's okay.

D1E: This was a cute implementation problem about a particular interesting tree construction. Analyzing the game was a very standard trick, though I'm not sure everyone has seen it; I think cutting out that layer of obfuscation would've been better. Also, you totally could've made the operation "flip one square" instead of "flip a path to the root", and it would be a little more natural/interesting.

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

    For problem B, O(N sqrtN logN) passed if you used vector + bsearch instead of set. Still you wouldn't expect that for 1s TL.

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

    I got TL 58 with the $$$O(n sqrt(n))$$$ solution using unordered_map of edges. When I changed it into an array of unordered_maps of adjacent vertices for every vertex, it passed with 400ms time. kmp

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

      Yeah, there definitely are people who actually failed due to constant factor, though most people just have it wrong. TL definitely should've been higher.

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

    Sorry to bother ecnerwala but I want to know if you knew the need of fast hash at first or how you figured out a hash is needed.

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

    we had n^2 and n.log solution for D but they said it is really hard for div1 D and we wanted div1 c be div1 d but they said it is easy

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

    I expect to have trouble solving D level problems, but I knew the idea for D1C almost as soon as I finished reading it, and it seems to be the same for most other people commenting here.

    It's definitely fine as C (it's even easier than this B imo), but as you said very implementation-heavy because of the type of segtree required.

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

    ‘I ran pretty close to the time limit because I didn't use Barrett reduction, but maybe that's okay.‘

    No, it’s not. What the hell.

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

      Well, this problem has a lot of ways to improve the constant by a factor of 2 or 6 or something, and I think I didn't do any of those either. I think the limits were a little low, but it seems like essentially everyone passed, and most of them passed pretty comfortably under the time limit, so I don't really think there's too much to complain about.

      Also, the code written here tends to be constant time (not depend on input), so if you pass pretests, you're essentially guaranteed to pass systests in the same runtime.

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

    For 1B, I thought of 2 solutions, O(nm/k) and O(N sqrtN logN)...

    One fails for small k and the other fails for big k, so I chose the solution based on the value of k and it got AC.

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

Why is everyone calling problem C implementation heavy ? ig 50 lines of code is okay right? at least problem Ca was not that implementation heavy though I can't comment on problem Cb

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

Dont they have plans to update the ratings for div 2 contestants as well ?

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

What the heck is going on with the upvotes???

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

    I assume people who are frustrated with the contest, and in particular Div2C / Div1A are downvoting it.

    I do consider it a shame that huge rating swings which are perhaps unrepresentative of true ability are able to come out of single questions like that. I am of course biased, because my rating has taken a big hit today: I made the decision to gamble on solving the hard version, and I failed — it cost me a lot.

    At the same time it's important to remember that these guys gave up their time to write a contest for us, and once the initial frustration passes we should be grateful for that. I'd rather a world of hit-and-miss contests than a world of no contests.

    So thanks to everyone who gives up their time for our enjoyment.

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

    People didn't like problems so they downvote, what's wrong with that? div1A is tedious and too hard, div1B has very tight limits.

    Setters should be appreciated but it's ok that contest announcements are used as good/bad contest voting system.

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

      Congrats sir on becoming a legendary grandmaster again :-)

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

      Really problemset was good . I think this contest should get upvote more .

      thanks all setters

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

      I didn't mean they should not up/down vote, it's a nice thing that the contestant actually care about the votes and share their opinion. The thing is I was TOO shocked when I saw the blog's upvotes going down that fast and I couldn't help with not knowing it.

      P.S. I consider people(including you) misunderstood me so I wanted to clarify.

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

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

hope to see more contest related to data structure and algorithm in the future ...

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

I succeeded at problem A but got my rating disminished is it normal?

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

    The rating change is calculated based on your rank in the standings table, not on the number of solved problems.

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

Thank you for writing the contest :)

I dont understand how to solve div2D in O(n sqrt(n)) or how some solutions that seem like O(n*m) are fast enough (98734217) — they maintain a queue of vertices with degree < k and one by one delete them. When its degree k-1 there is potential for a clique so they just brute force check all pairs of neighbors. That seems like n*m even after you note that k~sqrt(m) right?

I hope the editorial will give me more insight.

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

    "They just brute force check all pairs of neighbors"

    But still, these pairs are the edges of the graph no? Whenever we found that some pair doesn't exists, we just break there only. So eventually, we have traversed all the edges only once. Hence it's not O(n*m).

    For better understanding, take a example of DFS traversal:

    • for every vertex we traverse all the adjacent vertices, no?

    Similarly time complexity there is O(n+m), not O(n*m);

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

Could anyone share their approach to solve problem B of Div2? Would be glad to know. :)

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

    the main array is sorted . for each small array try to fill its right to median from right of main array then for left part fill it from left of main array . its optimal . i used two pointers ,lo points to left of main array and hi points to right of main array.

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

/me patiently waiting for the editorial while everyone is busy criticizing the round

»
4 года назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

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

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

How many lines does your code have for binary table (hard)? Mine is over 200 and I spent over one hour for it(thought I only spent about 20 minutes to think).by the way , Is there any short solution for it ?

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

praise God, can't take these haters

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

Though I don't like DIV2C/DIV1A very much, but still we must appreciate the writers for the hard work they have done.Sometimes ideas work, and sometimes not as expected, but that doesn't mean the problem setters didn't work hard enough. And there were many good things about the contest, small queue,no changes in problem statements,strong pretests(atleast for Div2),nonetheless, I would like to thank you guys for the hard work and the contest.

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

When will the editorials be realised?

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

Can you give us the code also attached with the editorials, that will be very helpful !

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

Has editorial just been removed?

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

    I can't see the editorial either :(
    It shows me "You are not allowed to view the requested page"...

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

Seems like your god can’t really help with the contest quality

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

Could anyone please provide link to the editorial? It's showing you are not allowed to view the requested page.

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

Please explain how to solve Div2 D?

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

    So, if we ignore the clique part. The first part about subset is pretty standard and can do by following greedy algorithm.

    1. Check that our graph has node with degree < k or not
    2. If there exists such node, remove it and all its edge -> reduce degree its neighbors by 1
    3. Repeat until no node with degree < k exists

    If the final graph is not empty, then it’s done. This part could be execute in $$$O(m+n)$$$ by standard BFS.

    Now, let’s put clique into a picture. We want to prioritize answering the problem by the subset since it’s significantly easier. If not, when we remove node, if its degree is $$$k-1$$$ then it is a candidate for clique. We can just save this node and all its neighbors and deal with it after the first part returning that no subset such that exists.

    To solve this, let’s suppose we save candidate in list of list. We can test each set of candidate by $$$O(k^2 logm)$$$ (if using set) or $$$O(k^2)$$$ (if using unordered map) Each candidate is made by deleting $$$k-1$$$ edges. So, we have at most $$$O(\frac{m}{k})$$$ set of candidates. This combined together to get that we can answer the second part by $$$O(m/k)O(k^2) = O(mk)$$$

    This looks like it wouldn’t be fast enough, but for a clique to exists. $$$2m$$$ must be more than or equal $$$k(k-1).$$$ This give us a rough approximation that $$$k \approx O(\sqrt{n}).$$$ So, the second part is $$$O(n^{\frac{3}{2}})$$$ which is fast enough to pass.

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

Why so many downvotes.... I think the contest is very nice

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

Why I am not allowed to view the editorials ? I had registered for the contest and solved some problems, then why I am not allowed to view editorials ?

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

The ratings are taken back!! Why do they so? do they found something wrong?

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

I participated and div A and B with no wrong submissions and came very near to pupil(1070 rating), but now when i see, the contest is deleted from my graph and the contests section, even though it shows my submissions in the official submissions.

Is this a temporary glitch or im missing out on something?

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

The problem set deserves credit, though they could've managed the contest better.