Mo2men's blog

By Mo2men, history, 3 years ago, In English

Hello, Codeforces!

I'm glad to invite you to Codeforces Round #737 (Div. 2) , which will be held on Monday, August 9, 2021 at 16:35 UTC+2.

This round rated for the participants with rating lower than 2100.

You will be given 5 problems and 2 hours to solve them.all problems were prepared by me and AhmedEzzatG.

One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round.

I would like to thank -

  1. Aleks5d, for awesome coordination of our round and suggested one of the problems.

  2. Ahmed-Yasser for help us to prepare the problems. compiler_101 ,Kilani ,TripleM5da , and Omar_Elawady for discussing and testing the problems.

  3. MikeMirzayanov, for the amazing Codeforces and Polygon platforms.

  4. Testers physics0523 , BlueDiamond , Tlatoani ,mahmoudbadawy , Andreasyan , IsaacMoris , Error_404 , Basilhijaz , MagentaCobra , wxhtzdy , Blobo2_Blobo2 , elizkaveta , zetamoo , Muhammed_Atef_Hassan , tdpencil , mcdx9524 , mosemAlanfgar , _Hosam , Bakry , Abdo_Naser , kalki411 , Hemose , Uzumaki_Narutoo , and our VIP tester Monogon.

The statements are short and I have tried to make the pretests strong. I encourage you to read all the problems.

This is our first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.

Good luck and see you in the standings!

UPD1: I want to thank Aleks5d for translating statements into Russian and mouse_wireless author of one of tasks.

UPD2: Scoring distribution: 500 — 1000 — 1750 — 2500 — 3000

UPD3: Editorial

UPD4:

Winners

Congratulations to all our winners in the round!

Div.1 + Div.2:

  1. tourist

  2. jiangly

  3. m_99

  4. BigBag

  5. Geothermal

Div2:

  1. FengzhuJian

  2. juruo_cjl

  3. RGB_ICPC4

  4. End.

  5. Hanabi2333

  • Vote: I like it
  • +292
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Your profile picture is really good and meaningful.

»
3 years ago, # |
  Vote: I like it +125 Vote: I do not like it

Monogon was the VIP tester of 2 consecutive rounds!

Orz!

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

As a trainee for the author I am so excited and I am sure that the statements are short XD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

keep going from ur trainee.

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

As a trainee for the author I am so excited and I am sure that the contest will be amazing as the author is amazing XD

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Amazing!! It will be such a great contest!

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm excited! We are in a drought of contests, and I'm itching to compete more.

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

As a tester, problems are great for the participants who love the short statements and like to gain high ratings!

Good luck to everyone :)

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Finally a SA3EDY Round #1، I hope it will not be the last one. keep going our heroes♡♡ ♡‿♡.

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Egypt Foooooo2 :"D

»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

As a very cool tester, I would like to say that the problems are nice and the pretests are very strong. I think you'll enjoy doing this round.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +52 Vote: I do not like it

    So, shamelessly give me contribution.

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

      commenting again instead of editing, double contribution, smart move xD

»
3 years ago, # |
  Vote: I like it +113 Vote: I do not like it

with the power vested upon me as a tester, I hereby declare thy contest interesting.

»
3 years ago, # |
  Vote: I like it +195 Vote: I do not like it

Though I'm not a VIP tester, I tried hard testing as much as I can.

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

    Yes, I can assure that you did a great job.

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

    What's the difference between tester and VIP tester?

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

      VIP Tester is supposed to get more contribution than normal tester.

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

        No.. VIP tester is the one who follows 1-gon and of course, was a tester. Normal testers are those who still don't follow 1-gon.

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

As a contest tester for the first time :), the contest is great and joyful.

I hope you will enjoy it ;)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone explain me why the time of this post is showing like 2 days ago ,although it is just posted like 1 hr before i guess

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's going to be a great contest :)

»
3 years ago, # |
Rev. 4   Vote: I like it +12 Vote: I do not like it

As a trainee of the author i am sure that the problems are epic, Good luck

Give me and my coach contribution :)

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

I decided to write the ultimate "as a tester comment" since this is the first and hopefully not the last time to be a tester of an official round (except of course if you count #716 #717).

1) as a tester add me to your friend list

2) as a non-VIP tester I hope I can be a VIP tester one day

3) as a tester I assure you that you should give my friend mo2men contribution

4) as a tester... (recursion ;) )

5) as a tester I advise you to read all the problems

6) as a tester I think you should prepare everything you'd need throughout the round because you won't be able to move or blink during the round

7) as a tester this round is pure awesomeness (kung fu panda 2008 reference)

8) as a tester of this round I would like to test upcoming rounds... maybe the next is yours? who knows

9) as I am 50% of the specialist testers population in this round help me by upvoting this comment

10) as a tester I recommend everyone to eat jilaty (ice cream in Arabic)

Note: the profile picture was taken by my friend and the author Mo2men in the Arab collegiate programming contest 2020 (ACPC)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

cant be proud more my friends keep going [user:IsaacMoris][user:Uzumaki_Narutoo][user:Blobo2_Blobo2] i sure the contest will be so beautiful ♥♥

»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

As a tester give me contributions.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

tdpencil has hacked few of my solutions in the past, so for me he is orZ. yeah!! this orZ has curves.

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

تحيا مصر ❤️

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Wow you really host a div-2 contest when you are just specialist. ORZ

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

    Rating is just a number.

    Also, this man was a problem setter in the Arab collegiate programming contest (ACPC) 2020 and a coach for many CP students, these students are now experts and candidate masters.

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

      True Rating is just a number .

      P.S. if you have good contacts xdddd

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

      Yes, rating is just a number. You're right.

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

        Bro ,but you have announced to become CM in 2 months ,so for you it's pride now ,best of luck

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just hope I can become a "Pupil" through this competition.

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

    Bro, you are solving 1600 and some 2000+ level problems! you deserve more than that for sure

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

      But I can only solve 2 or 3 problems in Div.2.I am too poor and I am only Grade 6 as a Chinese.

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

      Ahh......I'm too low to solve div.2 .I think I need to do more div.3.(Rank 8000+)

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

        You are in grade 6! I am in my third year of CS degree and still able to solve 3 problems div2... so you are much better off cuz you have so much time at hand! Relax!

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

          Wait,what does "CS" mean?University?Or middle school?

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

            computer science...

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

              Thank you!But I often call it OI.

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

                No, oi is the short name for "Olympiad in Informatics". CS is computer science which is the name of a major in the university.

                小盆友加油 (ง •_•)ง

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

                  You are also a Chinese?So how many problems should I solve in a normal Codeforces Div.2 if I what to get tg1=?Or I need to solve Div.1?

                  当然,我知道tg1=肯定得等初二左右了...

                  Of course,I know that I should wait for 2 years if I want to get tg1=.

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

                  I start very late you see.. I am still a newbie now.. When I was at your age, I was playing mud back in the school yard and knew nothing about OI. So your age and your time are the most valuable thing. Try to solve more problems. Hope you will be the next WJMZBMR :)

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

                  First,you were a specialist. Second,my mother says that if I can not get >=300 marks in CSP-J and tg2=,she will let me to be a MOer.But the thing I like is program ,not that complex and annoying math.(Maybe I am extreme,but I hope you can understand what I mean.)

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

                  UPD:My highest prize is CSP-J 2= 135 marks,so it is a hard task for me.That's why I want to enhance my strength by CF and Luogu as fast as I can.

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

                  I am going to be Grade 9 now,and I got tg1= last year.You still have long time to study,so I don't think you need to worry about it.I was only a Specialist when I got tg1= :) To the honest,getting a tg2= is not difficult,you can even use brute force to get tg2= easily :)

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope to become "Pupil" through this contest.

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

Good luck to everyone!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As you get ready for the contest, I wish you all the best of luck

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Most valuable advice ❤️❤️

Cap-ture

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    As a tester ,please orz this guy with a lot of upvotes ,otherwise he is gonna comment frequently for getting upvotes.

    P.S. just kidding but upvote him.i was the 1st to do so :)

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

feels like ages since the last round it's like all problem setters are on a vacation or something

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

We are so proud of you all , keep going :")

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I will reach pupil in this contest.

Thank You

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so excited to participate in this round, hope everyone will gain rating

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From the score distribution, it looks like it's going to be speedforces for A, B, C.

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

    Lol maybe for high rated people like you it may seem as speedforces but i don't think that guys like me feel so :).best of luck

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

    I sense more like AB speeforces

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

      I missed the part where that's my problem.:)

      P.S. just kidding bro .i do feel the same bruder ,best of luck

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

      Author revised the score distribution. Previously it said C was 1250 points, that's why I included C as well. Now it looks better.

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -43 Vote: I do not like it

whenever specialist expert makes a contest they always make it hard. If u are actively giving contests u know what I mean. They think it's cooler to make a harder contest. These pathetic nerds cant solve the all question themselves.

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

    Your Comments suit your Name!

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

    He is true. This round is awful. Tests in E are so strong that every wrong solution can pass it :)

    Do they have better ideas?They got a interesting idea(problem E) and some "strong" tests.

    Bad ABCD,real “speedforces”. The worst round I've ever seen.

    Finally,thanks the writers for this "wonderful" round :):):)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Short problem statements, thats what we wanted

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

I always used to think that to increase rating one have to solve more and more problems. Mo2men has solved more than 2000 problems then why his rating is not increasing ( ・᷄ ︵・᷅ )

»
3 years ago, # |
  Vote: I like it -59 Vote: I do not like it

i hope i can get top 10 in this contest

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh interactive, is this binary search ? :V

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

    May or may not be, interactive problems need not be always binary search always :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like today their ll be more of a number theory problems.

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

As a participant I wish to gain some precious contribution through this comment.

»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

will be unbalanced contest , I can bet

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

    see I already said, unbalanced round, still got downvotes

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

    Your prediction really comes true :(

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

hope that a and b will not be interactive

»
3 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Last few days I faced a lot in my life, Can't reveal what exactly happent. But you can assume that the sadness is as same as when you lose your father or mother or see them cry.Couldn't give last 3 contests with proper emotional and mental strength.But skipping a contest has never been an option for me.It's the only thing I have in my life to live for.I will try my best today.Good luck to everyone too

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

    Come on bro! It's only a part of the life. I hope you can come out of the gloom and step into the light as soon as possible.

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

      Yes!!While there is life, there is hope...If the great Stephen Hawkins figured out life even after getting paralysed,Hopefully I can too.

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Is it just me? getting a TLE on tc2 for problem A

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

    Yeah, I got it as well. It's a stupid question. Finally figured out the problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      My O(n) got tle! Anyway good luck to you for rest of the contest.

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

        My O(n) got Ac.But I'm afraid of getting FST :(

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Remind me when I'm trying to take part in another weird round and get negative delta

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6. How to achieve this in Java ??

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

    use double, It'll take care of it automatically (if your approach is correct).

»
3 years ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

Why the gap between C and D was a lot ?

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

    toxic:(

    check his original comment

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

    How will you know the balance of the questions if you only solved A?

    Original comment : fuck you with your fucking unbalanced contest

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

      You can look at the gap of D and C in the standings after system tests :)

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

        Why even care when you even can't solve B? Your toxicity is full of shit

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

First experience of being able to do B but not A XD.

»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

giving combinatorics without some relatively big testcase — unethical:/

»
3 years ago, # |
  Vote: I like it -126 Vote: I do not like it
ll n;
cin >> n;
ll k;
cin >> k;
vector<ll>arr(n, 0);
for (ll i = 0; i < n; i++) {
    cin >> arr[i];
}
ll sz = 1;
for (ll i = 1; i < n; i++) {
    if (arr[i - 1] > arr[i]) {
        sz++;
    }
}
if (sz <= k) {
    cout << "YES\n";
}
else cout << "NO\n";

why I am getting wa for this..its the correct soln

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

    you are asking this during contest thats what you doing wroong

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I just erased my whiteboard 5th time full of test-cases for C and yet I am unable to decipher. I am almost sure it's gonna be a one-liner but I just can't figure it out :(

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think the gap between the problems is too big :(

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

plz answer me a question whether you like the weak samples just because you think they're cool???

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

    My D is failing pretest 4 though :P

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

      Seeing so bad testcases for C, its impossible to know if the solution is even remotely correct. All my submissions passed the samples and failed pretests.

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

        It's not tough to write a brute force solution for C to verify.

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

      Very relatable.

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

        What did you do to fix it?

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

          I just added more parameters into my segmentree nodes and it worked. (Previously I used a set to maintain values.)

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

            Wait, like I should compress values with some more like $$$l - 1$$$, $$$l$$$, $$$r$$$ and $$$r + 1$$$ instead of just $$$l$$$ and $$$r$$$? If this is the case I'll be sad for another few days :P

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

              No, I think I did the same thing as what you did, but instead of keeping the max values in the segment tree, I used minimum values, but I have no idea whether your approach is right or wrong, because I iterated through the rows from 1 to n, not n to 1.

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

How the hell are 2500 people able to solve C

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

    I'm also wondering this too... So overall I'm too weak...

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

    Telegram I guess

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

    My might fail in sys test, I checked the submissions of the people in my room and all of them have similar code but completely different logic than mine....Hope the pretests are strong

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

    I think about this issue like this :

    Consider sequentially from the high binary bits to the low binary bits.

    The i-th binary bit can be "decided" or "undecided".

    Decided means that the i-th binary digit a1 & ... an is already greater than a1 xor ... an, and no subsequent comparison is required at this time.

    Undecided means that the value of a1 & ... an and a1 xor ... an can be compared after the i-th binary digit.

    Undecided includes two situations : - n numbers are all 1 in the i-th binary digit and n is an odd number. - At least one of the n numbers in the i-th binary digit is 0 and there is an even number of 0s.

    Undecided means that all n numbers on the i-th binary bit are all 1 and n is an even number.

    The final answer is composed like this :

    • Undecided Decided Random
    • Undecided

    my code like this

    # include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int mo=1e9+7;
    int pow(int x,int n){
    	int ans=1;
    	while (n) {
    		if (n&1) ans=ans*x%mo;
    		x=x*x%mo;
    		n>>=1;
    	}
    	return ans;
    }
    signed main() {
    	int t; scanf("%lld",&t);
    	while (t--) {
    		int n,k; scanf("%lld%lld",&n,&k);
    		int res=pow(2ll,n-1);
    		if (n&1) res=res+1; else res=res-1;
    		int ans=pow(res,k);
    		if (!(n&1)) {
    			for (int i=1;i<=k;i++) {
    				ans=(ans+pow(res,i-1)*pow(pow(2ll,n),k-i)%mo)%mo;
    			}
    		}
    		printf("%lld\n",ans);	
    	}
    	return 0;
     } 
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

shitty problems, bad balance and there are only 5 problems AT ALL

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C?

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Am I the only one here who had 2 penalties because of ignoring the fact that $$$-10^9 \le A_i \le 10^9$$$

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

    I got soo many wrong answers on B because a[i] can be 0. Why they didn't make a[i] permutation of length n? Anyway, I think that problems were ok but samples and these constraints were horrible.

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

      I had the exact same issue, I got first WA because $$$A_i$$$ can be 0 and 2nd WA because $$$A_i$$$ can be -1

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Weak sample for C :(

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

In div2 B i was rearranging the elements inside subarray for half an hour.

Sad noises.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked B it wasn't clear why the simple solution is not working but C is so hard still a good problem though I will try to solve it later

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

    Why did the simple solution not working in B?

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

      1 3 2 <- try this test case

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

      consider this case

      4 2
      2 3 5 4

      simple solution output Yes but it's a No cause you need k=3 you can't put 4 in middle 2 3 5

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

        I compressed elements to 0 to n-1 and checked if a[i] — a[i-1] == 1.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there another way to solve problem D instead of using a dynamic segmentree, curious -.-.

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

    As long as the queries are not online, you can (almost) always use coordinate compression and use a normal segment tree.

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

UPD: my bug was that I had to declare the Segment Tree Array with 8n elements

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

Contrary to popular belief, I liked problem C. A good question based on bit contribution and combinatorics.

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

    Even though I couldn't solve it but it indeed feels like a good problem. I hope to learn something great from the problem

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So i had this idea and observation for problem C:

For every number >= 1 times that it occures must be even. For example: 02211, 02222, 22110 etc. Total number of possibilities that pair of numbers can occur is n*(n-1)/2. There can be n/2 pairs of numbers in array, so total number of posibilities for 1 number is n*(n-1)/2 * n/2. Multiply this by amount of numbers: (2^k) — 1 * (n*(n-1)/2 * n/2). There also can be n same numbers that make problem condition true. So i also add 2^k to answer.

Can someone told me if that make any sense :D? Thought that would work but it didn't :/. Maybe it was only right for small numbers dunno

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

    Misses cases like [1,2,3] e.g total xor = 0 total and = 0. Also misses the idea if n is even you can set the leading bit to 1 in all values and set all other bits to any values.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting problems. Is D a segment-tree problem? I think I could solve it if only I could implement a generic segment tree.

and btw. why a * b % c == (a * b) % c and a + b % c != (a + b) % c :<

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

How to solve problem D . I think it is similar to longest increasing subsequence problem in a way $$$a[j]>a[i]$$$ if $$$j>i$$$ and $$$ j^{th}$$$ row and $$$i^{th}$$$ row have some common intersection . I tried to use segment tree but could'nt implement in time

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Very clever to do tests with k = 1 and k = 0 on a combinatoric problem! Good job!!! Don't do any other contests please.

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

    There aren't any corner cases.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why in problem A a hack with: t = 1,n = 10^5 and all a[i] = 10^9 gives invalid input?

»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

I spend about 1 hour on D......the solution is easy but it's hard to code :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D any hints? do we construct some kind of graph?

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

    use dp

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

    Segment tree with DP is what I did. First compress all intervals, so that we can fit a normal segment tree in. Let $$$dp_i$$$ be the minimum number of rows we have to remove to make rows $$$1~i$$$ good, and keeping the i_th row. Then the dp recurrence is pretty simple: $$$dp_i = min(dp_j)+i-j-1$$$, where (j<i). We can rearrange the formula into $$$dp_i-i=dp_j-j-1$$$ then we can keep the value $$$f_i = dp_i -i$$$ in the segment tree. For the segment tree, we update the ranges of ones of that specific row with $$$f_i$$$ and for the queries to check the previous rows for the dp recurrence, we also query only the ranges where ones are located in the i_th row.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think the examples of the problems are so easy that it makes me be not able to find the bugs.

»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it

I just loved $$$E$$$. Nice puzzle. Here's a small hint for those interested:

Hint
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Okay, as the editorial solution is entirely different, I will describe my solution here (which I liked better).

    Solution

    Code: 125400662

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Solution for D
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I’m getting WA on Test Case 4 with this approach :(

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

      Yeah, I also got that first but I found the bug in my implementation and corrected it.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My solution on E seemed to read a direction other than the ones described in pretest 3. It's likely I got a bug somewhere, but did anyone notice any similar weird behavior, because I can't seem figure it out?

Edit: Found a bug and got AC, still not sure what my program managed to read after producing a wrong move.

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

How to solve C?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Your example is so stronger that every wrong code can pass!

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

What is the problem with MLE pretest 4 in Problem D? Was I the only one to struggle with this?

I used a lazy segment tree to build a graph then found the longest path in an acyclic graph. You only need to add an edge to the nearest row that intersects with your current interval. Is that approach wrong or what?

Edit: NVM, FeelsBadMan

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Got TLE on C because of 32-bit python.

Very annoying.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

why you bully me , codeforce ?

»
3 years ago, # |
Rev. 4   Vote: I like it +169 Vote: I do not like it

What the fuck? I randomly submitted this pattern in E and it passed pretests.

(Edit : It passed system test)

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

    This solution made me feel disappointed :(

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

    And now you will become CM XD. Congrats

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

    and now it's Accepted. wtf

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

      This might be somehow the solution..? Main test had 7000 individual games and it all worked.

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

        Nope. It's wrong. It's just hard to make an opponent to counter all such solutions I guess.

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

          Maybe because the opponent isnt an AI that makes its move optimally, but instead it makes its move randomly so the probability will be so low to fail?

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

        I really really dont think so because when you are on (2,1) and go to (3,1) i can be on (3,6) then move to (2,6) and then to (1,x) and its over. (1,1) is the point in the upper left corner.

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

    And it turns out to be AC in main test.

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

    I can think of a test case where this solution doesn't work. The system tests are weak.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +76 Vote: I do not like it

    If the gif doesn't work, go to here

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

    I just continue to go in reverse path and it passed main tests. Indeed the solution above fails only last test.

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

Nice round guys, I enjoyed the problems :D

AhmedEzzatG Mo2men

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? It looked like a DP-Tabulation type of problem, but all I could figure out is that

$$$dp[n][k]=(2^{n-1}+1)^k$$$ when $$$n$$$ is $$$odd$$$

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    Let $$$p = 2^{n-1}$$$. Then the answer is

    $$$\begin{cases} (p+1)^k & n\ \textrm{odd} \newline \dfrac{\left(2p\right)^k+p\cdot\left(\frac p2\right)^k}{p+1} & n\ \textrm{even} \end{cases}$$$

    How I got it:

    I brute-forced many small values (my brute force was $$$O(n2^{nk})$$$ and worked well enough for $$$n+k \leq 12$$$ (took only 80 seconds with pypy!). I immediately noticed the powers of $$$5$$$ and $$$17$$$, and checked for $$$65$$$ and $$$257$$$. For the evens, I noticed that $$$\textrm{ans}(2,k) = 3\cdot\textrm{ans}(2,k-1)-2$$$. I plugged this into Wolfram Alpha and got that it was $$$\frac{4^k+2}3$$$. Then, I tried brute forcing expressions in the form $$$\frac{a^k+b}c$$$ for $$$n = 4$$$, but found nothing. Then I tried changing the expression for $$$n=2$$$ to $$$\frac{4^k+2\cdot1^k}3$$$, and checked that form of expressions, and got $$$\textrm{ans}(4,k) = \frac{16^k + 8\cdot7^k}9$$$. From there I generalized it.

    The modular exponentiation makes the time complexity $$$O(\log n + \log k)$$$.

    Also, looking at submissions of random people, I've seen at least 4 different solutions other than mine (though they're all about $$$O(n+k)$$$, so mine is faster), so there are many ways to solve this problem.

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

    even is $$$\frac{\left(2^n\right)^k-\left(2^{n-1}-1\right)^k}{2^{n-1}+1}+\left(2^{n-1}-1\right)^k$$$.

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

    Video solution, you can also convert the recurrence into a 1D DP (DP solution).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll probably fall to Specialist, but I really loved this round! Problem C was interesting, bit-manipulation and combinatorics puzzled me oh so good.

Kudos to the entire problem-setting team!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be solved using DP?

I tried to implement via a 4-D dp dp[i][_and][_xor][eq].

At the ith bit (out of k), I have 4 ways of assigning bit combinations to the _and and _xor values -> 0 0, 0 1, 1 0, 1 1, and eq can be 0/1/2, denoting whether the & cumulative value until the ith bit is lesser, equal or greater than that of the ^ cumulative value. Couldn't implement the combinatorics part for each of the combinations in time. But, would this solution work?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Clean dp:

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

      not sure what I have done dp:

      ugly dp
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Count cEven the number of ways to pick an even number of 1's in an n-bit number. Then do dp on the most significant digits: if n is odd you have dp[i] = dp[i-1]*(cEven+1) (+1 is the case of all digits being ones). The second term is the number of ways the first digits can be equal. If n is odd then dp[i] = dp[i-1]*(cEven-1) + 2^(n*(i-1)). Here the second summand is the case of the first digit of the AND being larger than that of the XOR so any combination of digits other than the first works. The first summand is the digits being equals (you remove 1 because if all digits are 1 then there are an even number of them but then the AND term is larger). You can precompute the powers of 2 mod M as n is always the same.

»
3 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

great contest

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

    k = 0 should always be 1 independent of n. I think it's more about them screwing with you and putting k = 0 as a valid test case at all than anything else

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Well, it seems there is some disrespectful comments. Please respect the setter. For me C was good problem, and although I couldn't solve, E was also interesting. Thanks for the contest.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

one of the most balanced div 2s ever. Kudos to the authors !!

»
3 years ago, # |
Rev. 4   Vote: I like it +25 Vote: I do not like it

I thought constraints to be different for C, so I solved it for $$$T <= 10^5$$$.

Solution
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote a solution of C but it was giving wrong answer on test case 2. Can someone explain what is wrong with the logic. I used 1-d dp. dp[0]=1 and for i from 1 to k - When n is even, dp[i]=2^(n*(k-1))+(2^(n-1)-1)*dp[i-1] - when n is odd, dp[i]=(2^(n-1)+1)*dp[i-1]. here is the link to my code

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Here's my code full code: https://codeforces.me/contest/1557/submission/125410342

     int even(int n,int k){
         if(k==0)return 1;
        return  mod_add(modpow(modpow(2,k-1),n), (modpow(2,n-1)-1)*even(n,k-1));
    }
    
    int odd(int n,int k){
         return modpow( modpow(2,n-1)+1,k); 
    }
    
    void solve(){
    
        int n,k;
        cin>>n>>k;
    
        if(n%2==0)cout<<even(n,k)<<endl;
        else cout<<odd(n,k)<<endl;
    
    }
    
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      wth man. I think my code is exactly same as yours. You just used recursion and I used loop then why on earth it is giving me wrong answer!!!!

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        When n is odd:

        Because there won't be any case such that a1&a2&a3.... > a1^a1^a3

        Max, they can be equal.

        Proof:

        For a1&a1&a3 to be greater it needs to be all 1 at some ith bit (1&1&1) but at the same time, 1^1^1 will also be 1 therefore we conclude a1&a1&a3 can never be greater than a1^a2^a3

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

          Ya I get it sorry I changed the comment I think both the codes are same!!!

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

          Ohh man I wrote k in place of i in the even case (2^(n*(k-1)) that should be (2^(n*(i-1)). Really disappointed by this type of typo :( otherwise, code was correct:( By the way thanks for helping buddy :)

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

      Could you elaborate on your logic?

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

        You need to consider 2 cases.

        if n is even:

        if we are the kth bit we have 2 options

        • Either we put bits in such order that 'and of the kth bit =1 and xor=0. For this bits at the kth position of all numbers needs to be 1 and the rest for (0- k-1) bits we can put any sequence of bits that will be equal to modpow(modpow(2,k-1),n).

        • or, we put bits such that 'and' and 'xor' both are equal for that (number of 1 bit == no of 0 bits) or all bits ==0 and then recursively call for (n,k-1)

        if n is odd:

        • We can only make a1&a2&a3==a1^a2^a3. Just number of set bits needs to be even
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice round and keep going, guys :) It is sad to tell nowadays that many CF members don't like any problems, neither easy nor hard. They only like complaining and staying in comfort zone.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it -76 Vote: I do not like it

    I just want to know HOW MUCH dollars did you get from these writes?

    I don't think a man can say these words after participating. How dare you to comment these f...ing words without your brain. :)

    If I can earn dollars by posting comments like you,please tell me. :)

    Finally, I wish the author and you a long life, a happy family and good health. Thanks a lot :) :) :)

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

      May you get the most downvotes anyone has ever received!

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

        Thank you :) I just want to earn money like you guys :(

        If they aren't able to write a contest,please go to problemset and practise more,rather than giving us five naive problems. :)

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

          you are a div1 alt....go and participate in div1 if u have balls

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

            I have participated in div1.... But it has nothing to do with "div1". Anyway,this round is awful.

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

          Having participated myself I want to say that this round’s truly not-so-good. Have myself puzzled throughout the contest.

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

    Tell me,why do you think this round is nice?Say a reason rather than hurrying downvoting me.

    Or you guys just want a interesting problem that you can accpet by printf("rand()") ,or four problem that has been written years ago?

    Why do you lovely guys participate a codefoces round?To solve five cute naive problems and get nothing?:)

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

      at least we dont have the server down this time so calm down

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

One good thing about this contest is that I didn't face any lag today. The system was pretty smooth for me. The difficulty level of problem D was a bit on the hard side than a regular Div-2 D, to be honest. Overall, had a good time brainstorming. Thanks Mo2men & AhmedEzzatG for the contest.

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

What is the answer for this input in problem C: n= 1, k = 0. In my Accepted submission, it is 1. But I saw an accepted submission where it is 0.

https://codeforces.me/contest/1557/submission/125390194

I guess the setter didn't include this test in the system test.

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

Why the verdict of my submission is still Pretests passed? Problem B

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

why do tled guys not retested? seems like some correct solns for problem A got TL

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

A bad round:((((((

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Feedback for authors -
Personally, I didn't like "Left", "Right" etc as King's movement. Giving dx,dy would have been nice.
I did spend a good amount of time hardcoding direction to dx,dy twice. After hardcoding once I realised switch(s) in C++ only accepts integers. Then I had change switch to map.

Spoiler

I completed the code in the last 5 mins and even after that it had a bug with one specific direction and would have costed an AC.

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

    Authors have just detected if you are able to write easy-to-debug/support code

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

      Trying hard to learn/write easy-to-debug/support code. Thanks for the tip.

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

    I agree that it's important to make the problem statements in such a way that people can focus on the problem solving aspect, without getting too caught up in the coding "boilerplate".

    But this is competitive "programming" after all. Maybe it's just me, but I don't think it's bad to focus on the "programming" aspects from time to time ¯\_(ツ)_/¯

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

From HTI thanks Assiut university for the great ICPC community you made :)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I know I have poor abilities, but

How CRAZY the weak examples are!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gave this round could only solve 2, but expected I would at least not be unrated anymore. Why am I still unrated?

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

My solution for problem B remains the verdict "pretest passed". What's happening?

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

My solution for problem A got TLE on test case 2 on system tests (https://codeforces.me/contest/1557/submission/125328000)

After submitting the same code after system tests, it got AC (https://codeforces.me/contest/1557/submission/125407093)

If its possible to rejudge my submission, please do so.

UPD : Submission got rejudged and got AC!

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

    Your code passed with 998ms / 1s, so it is very risky to submit the soln. Though I don't know what caused the TLE in you code... I see no issue.

    Maybe sorting the vector with 300,000 elements caused the TLE?

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

      reading long doubles is slow, also it's common practice to retest some tled submissions after the contest, because of server load

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

      Printing floats with 20 precision. Just reduce it to 8. I too sorted but ACed in less than 100 ms.

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

    What if it continues to get tle

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

    I think I had a similar situation during the contest.

    TLE2: 125363145 (reading long double), AC: 125364892 (reading long long), AC after the contest: 125409423 (reading double using scanf).

    They are all the same solution, but it cost me $$$-50$$$. I can't figure out why :(

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

I don't understand why my solution to question B is still showing me a pretest passed . I think it was not evaluated by the system . please tell me what to do.

»
3 years ago, # |
  Vote: I like it +65 Vote: I do not like it

??? I wonder how this can be accepted 125408147

It just move like this ↓

And this worth 3000 points, the sum of Problem A, B, C.

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

    Just realised it's an interactive problem that supports hacking and there is no "Hacking format" section.
    Also, the problem statement doesn't mention if this problem is adaptive or not. It would be interesting if someone comments one can't hack this submission as well.

    Guessing hacking format from "Input" section in test cases and making one unsuccessful hack to validate hacking format I'm even sure one cant even hack any submissions because hacker cannot even control king's movement.

    The ideal format would have been hacker printing 131 king position with which interactor would have used to move king instead of hacker just supplying initial position and checker making decisions on rest 130 positions.

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

      Reasonable. It's more ideal if we can use custom interactor to hack in adaptive problems. Although no one can finish writing it during the contest lol.

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

    just realized this picture is from an earlier comment lul

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I'd say that the problems are not too bad,because for me the first 3 problems are pretty ok for Div2 ABC problems,and E seems interesting.

The examples are kinda weak but i blame myself for not double checking. Also the tests in C and the interactor in E is weak,letting some incorrect solutions to pass.

»
3 years ago, # |
  Vote: I like it +209 Vote: I do not like it

This is the best round I have ever seen, I can hardly imagine a round with a perfect balance and difficulty, the level of the authors is quite high, all levels of coders were able to get a perfect round, I felt physically and mentally happy when I played this game.

The questions in this cf were very interesting and I learned very many meaningful tricks from them, the difficulty slope was very reasonable, the sample coverage was very wide, and I even got a pass on the sample that only made the code pass.

What I admire about the author is that he has the courage to submit this kind of contest for review. If I had come up with such a topic, I would have been ashamed, but the author is open and honest, a real gentleman, he is the best courageous person I have ever met, bar none.

When I clicked on the leaderboard of the contest, I even wondered if I had clicked on the rating list. other low quality contests had purple and grey in the leaderboard, but in this contest, purple, blue, cyan and green were clearly defined, which made me admire the author from the bottom of my heart.

Finally, I wish the problem setter a long life, a happy family, good health and a speedy recovery from the loss of his mother.

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

    Although I haven't been online for a long time, I still heard about this f**king round. This article is very 'left', but I like it

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

    Can’t agree more :) The contest is so perfect that I even used my rating drop to gain contribution :)

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

    I've seen a lot of words spouted about the rounds, but I haven't seen such euphemisms.

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

Solution to E that passes tests with a limit of 21 queries per test case. 125414030

»
3 years ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

Deleted

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -32 Vote: I do not like it

    Hey. Your code is correct but somehow taking lot of "doubles" as input is affecting time and hence TLE.

    Take int as input (very fast) and cast them to double, still your code works.

    i.e int x; cin>>x a[i] = x where a is "double array" it will pass.

    proof:

    include <bits/stdc++.h>

    using namespace std;

    int main(){ long long tt; cin>>tt; bool show = tt==3; while(tt--){ long long n; cin>>n; double a[n] = {0.0}; for(int i=0;i<n;i++) {

    //3 "show" int c; cin>>c; a[i]=c;

    /* only 2 "show" cin>>a[i] */ }

    if(show) cout<<"show\n";

    sort(a, a+n, greater()); double ans=0; for(int i=1;i<n;i++) ans+=a[i];

    int temp=n-1; ans/=temp; ans+=a[0]; printf("%.6f\n", ans); } }

    Above prints only 2 "show" for 2 test cases, indicating that TLE happened while taking input od 3rd test case.

    replace

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

      Thanks for the help...understood it...taking input a double value takes longer time than int...so we should avoid it if possible :)

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

    It seems, you are using cin, cout which is pretty slower. And your execution time is significantly depending on I/O. If you use faster I/O (like scanf, printf), I think it will pass with double. FYI, Please just don't paste codes here, just link the submissions next time. :D

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problemset, hard and interesting

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of curiosity, how did problemsetters create interactor for problem E? Seems hard.

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

    how did problemsetters create interactor for problem E?

    Not very well clearly, looking at the amount of wrong solutions that passed. The absence of a note on whether the interactor is adaptive, and the even more egregious absence of an explanation on how hacks work on the problem were red flags suggesting that the preparation of E was somewhat sloppy IMO...

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

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

    Mike how can someone tell the authors Fu** you and his comment doesn't get deleted and he doesn't get penalty is everyone on codeforces on a vacation

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

      Everyone in codeforces doesn't have time to read every comment in every blog, unlike some people.

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

        Lol that's the contest blog such a comments always gets deleted

»
3 years ago, # |
  Vote: I like it -117 Vote: I do not like it

Good conpetition.But it's a pity that I miss it.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it -6 Vote: I do not like it

    i don't think that this is a good round, and i don't even understand why you think it's good round.

    I was hopeful about this race before it even started, but after the race, I thought this race was not a good contest.

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

      I am curious why you think the contest was bad?

      One of the few problems I have seen was that the checker of E was not very solid, allowing lots of random solutions to pass, luckily, it didn't impact the official standings that much since only 6 people in the official standings solved E and I doubt that reason was the primary cause of complaints by DIV2 participants.

      Another reason that comes to my mind is that the samples for C weren't very strong, but otherwise I found the problems, at least A-C, elegant, in terms of the thought-process. Also, I couldn't find any Failed System Issues in this contest? Neither did I find any issues with the statements

      What is the deal with a lot of people complaining? Is it just a lot of people ranting who weren't satisfied with their performance?

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

        Well, B was "simple problem hidden behind complecated statement". I am sure most of the participants who did not solve the problem immediately are upset about it.

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

        well, perhaps my words were too strong, i'm sorry about that.

        first, the samples are too weak; second, the 5th problem's data is very bad, allowing lots of random solutions to pass;

        i'm sorry to say this without careful analysis, but seriously, i dont like this round.

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

    I think you'd better evaluate the contest after reading the problems!

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

    It's really a GREAT CONTEST!!! especially THE EXCELLENT INTERACTOR of problem E!!! :(

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I have tried to make the pretests strong.

However, strong pretests ≠ weak example... :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem 1 have very obvious samples, some examiner doesn't realy understand it's principle but can accpect very quickly(true, include me ^_^).

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

In China, OIers have 'cordial greetings' to the people who write the questions

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Nice round and Nice music!!! https://www.youtube.com/watch?v=9tIFSo_bEVY

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think the strong present tests $$$\not =$$$ weak samples.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do we compress intervals in D ?

»
3 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Can you give me the reason for the weak samples and the weak system tests of problem E?

»
3 years ago, # |
Rev. 3   Vote: I like it -31 Vote: I do not like it

[deleted comment]

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice,I failed.I am still a newbie.

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

why am I unable to open the editorial. It's showing that you are not allowed to see the requested page.

»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Actually I think this round is not that bad. Problems except E are in normal range of difficulty. Why are many people annoyed? I think there're only a few contestants affected by E for the fake solution. As for the weak samples, there's no obligation for problem setters to provide strong samples.

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

    i dont think so. i think the strong example is an important part of a great contest.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +13 Vote: I do not like it

      Actually, one important skill for competitive programming is that you need to find the error of your code by yourself, without depending on the samples. Meanwhile, the function of the sample is not to check whether your code is correct or not, but to clearly describe the problem.

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

"You are not allowed to view the requested page" Why you do this :( ?

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

    I think they want us to solve the problem ourselves.

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I am unable to access the tutorial of this contest. Why is this happening can someone please help.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someOne please tell me what will be the answer if we slightly change the B problem.

change: you can also reorder the subarray elements & still we have to make exactly K subarray.

I found it so hard for me because it took almost 1 hour for me & I couldn't solve it. after that, I read the actual problem then solved it, but here I am more curious to know the modified problem solution.

I think it becomes a good problem after modification.

can anyone please..? I also want you all to tell your approach.

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

    I would keep adding elements to a subarray till we have a subarray which consists of all elements needed to make the sequence how it would look in the sorted array, then we can see this as a valid sequence and cut it here. Then repeat the process till the end of the array.

    The answer is Yes when we have created <= k subarrays, since we can still split an existing subarray

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

      can you please explain it with one example or drive run that example here...?

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

        example

        6 2

        3 1 2 6 4 5

        split it into two arrays:

        3 1 2 and 6 4 5

        reordering: 1 2 3 and 4 5 6

        got sorted array

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

          I assume here your code time complexity is O(n).

          so here what example you take is right but what about the below example is it still right to apply the above approach to this code..?

          Example :

          • 6 4
          • 1 4 6 3 5 2

          remember you have to split it in exactly 4 subarray that should be non-empty.

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

            well, that's impossible

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

Why is the tutorial blocked?

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

    Because what's claimed there to be a proof of the statement the solution for problem A is based on is not a proof of that statement by any stretch. :P

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why isn't the editorial visible ?

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

    Is it unavailable for you now? I tried an incognito tab and it looks good for me.

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Nice Contest :D