### Mo2men's blog

By Mo2men, history, 18 months ago,

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 ,El3ageed_Abu_Shehab ,DeadlyPillow , and Omar_Elawady for discussing and testing the problems.

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

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!

#### Div2:

• +292

| Write comment?
 » 18 months ago, # |   +41 Your profile picture is really good and meaningful.
•  » » 18 months ago, # ^ |   -45 what about problems' rating? If not a secret
•  » » 18 months ago, # ^ |   -22 Friend++ :)
 » 18 months ago, # |   +125 Monogon was the VIP tester of 2 consecutive rounds!Orz!
•  » » 18 months ago, # ^ |   +407 I agree. Orz me.
•  » » » 18 months ago, # ^ |   -51 Orz Monogon
•  » » » 18 months ago, # ^ |   -14 U don't need to say that ,people by default orz you
•  » » » » 18 months ago, # ^ |   0 he has to, for taking over codeforces(and the contribution).
•  » » » » 18 months ago, # ^ |   -7 So much downvotes,that's why i love cf but not cfiians
 » 18 months ago, # | ← Rev. 2 →   +15 As a trainee for the author I am so excited and I am sure that the statements are short XD
 » 18 months ago, # |   +3 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
 » 18 months ago, # |   +6 Amazing!! It will be such a great contest!
 » 18 months ago, # |   +5 I'm excited! We are in a drought of contests, and I'm itching to compete more.
 » 18 months ago, # |   +27 As a tester, problems are great for the participants who love the short statements and like to gain high ratings!Good luck to everyone :)
 » 18 months ago, # |   +13 Finally a SA3EDY Round #1، I hope it will not be the last one. keep going our heroes♡♡ ♡‿♡.
 » 18 months ago, # |   +17 Egypt Foooooo2 :"D
•  » » 18 months ago, # ^ |   +5 T3mya UP
 » 18 months ago, # |   +64 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +52 So, shamelessly give me contribution.
•  » » » 18 months ago, # ^ |   +35 commenting again instead of editing, double contribution, smart move xD
 » 18 months ago, # |   +113 with the power vested upon me as a tester, I hereby declare thy contest interesting.
 » 18 months ago, # |   +195 Though I'm not a VIP tester, I tried hard testing as much as I can.
•  » » 18 months ago, # ^ |   +57 Yes, I can assure that you did a great job.
•  » » 18 months ago, # ^ |   +17 What's the difference between tester and VIP tester?
•  » » » 18 months ago, # ^ |   +85 VIP Tester is supposed to get more contribution than normal tester.
•  » » » » 18 months ago, # ^ |   +1 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.
 » 18 months ago, # |   +32 As a contest tester for the first time :), the contest is great and joyful.I hope you will enjoy it ;)
 » 18 months ago, # |   0 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
 » 18 months ago, # |   +1 It's going to be a great contest :)
 » 18 months ago, # | ← Rev. 4 →   +12 As a trainee of the author i am sure that the problems are epic, Good luckGive me and my coach contribution :)
 » 18 months ago, # | ← Rev. 2 →   +67 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 list2) as a non-VIP tester I hope I can be a VIP tester one day3) as a tester I assure you that you should give my friend mo2men contribution5) as a tester I advise you to read all the problems6) 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 round7) 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 knows9) as I am 50% of the specialist testers population in this round help me by upvoting this comment10) 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)
•  » » 18 months ago, # ^ |   +8 I think you forget to say as a tester (◠‿◕)
•  » » 18 months ago, # ^ | ← Rev. 2 →   +2 Blobo2_Blobo2 u seem like :
•  » » 18 months ago, # ^ |   +6 ahm 7aga el jilaty ana megahez 3lba fe elfrazer XD
•  » » 18 months ago, # ^ |   +3 well deserved upvote xD
•  » » 18 months ago, # ^ |   +9 bruh when you will be a tester again what you will write those are all the "as a tester" comments human invented
 » 18 months ago, # |   +1 cant be proud more my friends keep going [user:IsaacMoris][user:Uzumaki_Narutoo][user:Blobo2_Blobo2] i sure the contest will be so beautiful ♥♥
•  » » 18 months ago, # ^ |   0 ;)
 » 18 months ago, # |   +99 As a tester give me contributions.
•  » » 18 months ago, # ^ |   +12
•  » » 18 months ago, # ^ |   +8 i know this tester and he is the best tester and setter i have met keep going my coash
 » 18 months ago, # |   +1 tdpencil has hacked few of my solutions in the past, so for me he is orZ. yeah!! this orZ has curves.
 » 18 months ago, # |   +25
 » 18 months ago, # |   +15 تحيا مصر ❤️
 » 18 months ago, # |   +26 Wow you really host a div-2 contest when you are just specialist. ORZ
•  » » 18 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 18 months ago, # ^ |   +9 True Rating is just a number .P.S. if you have good contacts xdddd
•  » » » 18 months ago, # ^ |   +3 Yes, rating is just a number. You're right.
•  » » » » 18 months ago, # ^ |   +9 Bro ,but you have announced to become CM in 2 months ,so for you it's pride now ,best of luck
•  » » » » » 18 months ago, # ^ |   0 There are still 8 weeks to go bro.
•  » » » » » » 18 months ago, # ^ |   +16 There are just 8 weeks to go bro :)
•  » » » » » » 18 months ago, # ^ |   0 I want to get CM too in 2 months, lets race to CM :O
•  » » » » » » » 18 months ago, # ^ |   +1 I am in too
 » 18 months ago, # |   0 I just hope I can become a "Pupil" through this competition.
•  » » 18 months ago, # ^ |   +1 Bro, you are solving 1600 and some 2000+ level problems! you deserve more than that for sure
•  » » » 18 months ago, # ^ |   0 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.
•  » » » 18 months ago, # ^ |   0 Ahh......I'm too low to solve div.2 .I think I need to do more div.3.(Rank 8000+)
•  » » » » 18 months ago, # ^ |   +1 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!
•  » » » » » 18 months ago, # ^ |   +3 Wait,what does "CS" mean?University?Or middle school?
•  » » » » » » 18 months ago, # ^ |   0 computer science...
•  » » » » » » » 18 months ago, # ^ |   0 Thank you!But I often call it OI.
•  » » » » » » » » 18 months ago, # ^ |   +3 No, oi is the short name for "Olympiad in Informatics". CS is computer science which is the name of a major in the university.小盆友加油 (ง •_•)ง
•  » » » » » » » » » 18 months ago, # ^ |   0 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=.
•  » » » » » » » » » 18 months ago, # ^ |   0 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 :)
•  » » » » » » » » » 18 months ago, # ^ |   0 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.)
•  » » » » » » » » » 18 months ago, # ^ |   0 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.
•  » » » » » » » » » 18 months ago, # ^ |   0 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 :)
 » 18 months ago, # |   +8 Hope to become "Pupil" through this contest.
 » 18 months ago, # |   +3 Good luck to everyone!
 » 18 months ago, # |   0 As you get ready for the contest, I wish you all the best of luck
 » 18 months ago, # |   0 Most valuable advice ❤️❤️
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 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 :)
 » 18 months ago, # |   +20 feels like ages since the last round it's like all problem setters are on a vacation or something
 » 18 months ago, # |   +5 We are so proud of you all , keep going :")
 » 18 months ago, # |   0 Auto comment: topic has been updated by Mo2men (previous revision, new revision, compare).
 » 18 months ago, # |   0 I will reach pupil in this contest.Thank You
 » 18 months ago, # |   0 I am so excited to participate in this round, hope everyone will gain rating
 » 18 months ago, # |   0 From the score distribution, it looks like it's going to be speedforces for A, B, C.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 18 months ago, # ^ |   +2 I sense more like AB speeforces
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 I missed the part where that's my problem.:)P.S. just kidding bro .i do feel the same bruder ,best of luck
•  » » » 18 months ago, # ^ |   0 Author revised the score distribution. Previously it said C was 1250 points, that's why I included C as well. Now it looks better.
 » 18 months ago, # |   +9 Auto comment: topic has been updated by Mo2men (previous revision, new revision, compare).
 » 18 months ago, # |   -43 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.
•  » » 18 months ago, # ^ |   0 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 ：）：）：）
 » 18 months ago, # |   +1 Short problem statements, thats what we wanted
 » 18 months ago, # | ← Rev. 2 →   0 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 ( ･᷄ ︵･᷅ )
•  » » 18 months ago, # ^ |   +3 Maybe mo2men cares about solving problems more than having good ratings! ¯\_(ツ)_/¯
•  » » » 18 months ago, # ^ |   0 But still +delta motivates a lot
 » 18 months ago, # |   -59 i hope i can get top 10 in this contest
•  » » 18 months ago, # ^ |   +39 why?
•  » » » 18 months ago, # ^ |   0 This is what you call stalking*100
•  » » 18 months ago, # ^ |   +110 i hope i can get top 10 in this contest,too.
 » 18 months ago, # |   0
 » 18 months ago, # |   0 Oh interactive, is this binary search ? :V
•  » » 18 months ago, # ^ |   -6 May or may not be, interactive problems need not be always binary search always :)
•  » » » 18 months ago, # ^ |   +10 I know, this is a joke
 » 18 months ago, # |   0 Looks like today their ll be more of a number theory problems.
•  » » 18 months ago, # ^ |   0 How do you know?
•  » » » 18 months ago, # ^ |   -6 just guessing bro .
 » 18 months ago, # |   -11 As a participant I wish to gain some precious contribution through this comment.
•  » » 18 months ago, # ^ |   0 Please take good care of this precious contribution that you've received.
•  » » 18 months ago, # ^ |   0 nope :D
 » 18 months ago, # |   -20 will be unbalanced contest , I can bet
•  » » 18 months ago, # ^ |   +26 see I already said, unbalanced round, still got downvotes
•  » » 18 months ago, # ^ |   0 Your prediction really comes true :(
 » 18 months ago, # |   +3 hope that a and b will not be interactive
 » 18 months ago, # |   +45 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
•  » » 18 months ago, # ^ |   0 Good luck bro ull get to specialist today :)
•  » » » 18 months ago, # ^ |   0 I hope so.I will try my best.Thanks for your kind words
•  » » 18 months ago, # ^ |   +5 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.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +2 Yes!!While there is life, there is hope...If the great Stephen Hawkins figured out life even after getting paralysed,Hopefully I can too.
 » 18 months ago, # |   -16 Is it just me? getting a TLE on tc2 for problem A
•  » » 18 months ago, # ^ |   -17 Yeah, I got it as well. It's a stupid question. Finally figured out the problem.
•  » » » 18 months ago, # ^ |   -19 My O(n) got tle! Anyway good luck to you for rest of the contest.
•  » » » » 18 months ago, # ^ |   0 My O(n) got Ac.But I'm afraid of getting FST :(
 » 18 months ago, # |   +28 Remind me when I'm trying to take part in another weird round and get negative delta
 » 18 months ago, # |   0 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 ??
•  » » 18 months ago, # ^ |   +1 use double, It'll take care of it automatically (if your approach is correct).
 » 18 months ago, # | ← Rev. 3 →   +27 Why the gap between C and D was a lot ?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +16 toxic:(check his original comment
•  » » 18 months ago, # ^ | ← Rev. 2 →   +7 How will you know the balance of the questions if you only solved A?Original comment : fuck you with your fucking unbalanced contest
•  » » » 18 months ago, # ^ |   0 You can look at the gap of D and C in the standings after system tests :)
•  » » » » 18 months ago, # ^ |   +2 Why even care when you even can't solve B? Your toxicity is full of shit
 » 18 months ago, # |   -9 First experience of being able to do B but not A XD.
 » 18 months ago, # |   +64 giving combinatorics without some relatively big testcase — unethical:/
 » 18 months ago, # |   -126 ll n; cin >> n; ll k; cin >> k; vectorarr(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
•  » » 18 months ago, # ^ |   +23 you are asking this during contest thats what you doing wroong
•  » » » 18 months ago, # ^ |   -58 give logic atleast
•  » » » » 18 months ago, # ^ |   +22 Dude, you don't ask for help during a contest!!
 » 18 months ago, # |   +1 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 :(
 » 18 months ago, # |   +5 I think the gap between the problems is too big :(
 » 18 months ago, # | ← Rev. 2 →   +45 plz answer me a question whether you like the weak samples just because you think they're cool???
•  » » 18 months ago, # ^ |   +6 My D is failing pretest 4 though :P
•  » » » 18 months ago, # ^ |   0 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.
•  » » » » 18 months ago, # ^ |   0 It's not tough to write a brute force solution for C to verify.
•  » » » 18 months ago, # ^ |   0 Very relatable.
•  » » » » 18 months ago, # ^ |   0 What did you do to fix it?
•  » » » » » 18 months ago, # ^ |   0 I just added more parameters into my segmentree nodes and it worked. (Previously I used a set to maintain values.)
•  » » » » » » 18 months ago, # ^ |   0 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
•  » » » » » » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   +27 How the hell are 2500 people able to solve C
•  » » 18 months ago, # ^ |   0 I'm also wondering this too... So overall I'm too weak...
•  » » 18 months ago, # ^ |   +4 Telegram I guess
•  » » » 18 months ago, # ^ |   0 What do you mean?
•  » » » » 18 months ago, # ^ |   0 Cheater , not all but some
•  » » 18 months ago, # ^ |   +1 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
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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 # 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; } 
 » 18 months ago, # |   0 shitty problems, bad balance and there are only 5 problems AT ALL
 » 18 months ago, # |   +6 How to solve C?
 » 18 months ago, # |   +13 Am I the only one here who had 2 penalties because of ignoring the fact that $-10^9 \le A_i \le 10^9$
•  » » 18 months ago, # ^ |   +3 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.
•  » » » 18 months ago, # ^ | ← Rev. 3 →   +3 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
 » 18 months ago, # |   +8 Weak sample for C :(
 » 18 months ago, # |   +10
 » 18 months ago, # |   +17 In div2 B i was rearranging the elements inside subarray for half an hour.Sad noises.
•  » » 18 months ago, # ^ |   +6 Same I did , for around 10 minutes.
 » 18 months ago, # |   0 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
•  » » 18 months ago, # ^ |   0 Why did the simple solution not working in B?
•  » » » 18 months ago, # ^ |   +1 1 3 2 <- try this test case
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +3 consider this case4 2 2 3 5 4simple solution output Yes but it's a No cause you need k=3 you can't put 4 in middle 2 3 5
•  » » » » 18 months ago, # ^ |   +3 I compressed elements to 0 to n-1 and checked if a[i] — a[i-1] == 1.
 » 18 months ago, # |   0 Is there another way to solve problem D instead of using a dynamic segmentree, curious -.-.
•  » » 18 months ago, # ^ |   +3 As long as the queries are not online, you can (almost) always use coordinate compression and use a normal segment tree.
 » 18 months ago, # | ← Rev. 2 →   +1 UPD: my bug was that I had to declare the Segment Tree Array with 8n elements
 » 18 months ago, # | ← Rev. 2 →   +7 Contrary to popular belief, I liked problem C. A good question based on bit contribution and combinatorics.
•  » » 18 months ago, # ^ |   +5 Even though I couldn't solve it but it indeed feels like a good problem. I hope to learn something great from the problem
 » 18 months ago, # |   0 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
•  » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 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 :<
•  » » 18 months ago, # ^ |   +3 operator precedence
•  » » » 18 months ago, # ^ |   0 I know i know
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 % has the same precedence as /, and a + b / c wouldn't be (a+b) / c now, would it?
 » 18 months ago, # |   +17 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
 » 18 months ago, # |   +8 Very clever to do tests with k = 1 and k = 0 on a combinatoric problem! Good job!!! Don't do any other contests please.
•  » » 18 months ago, # ^ |   +1 There aren't any corner cases.
 » 18 months ago, # |   +6 Why in problem A a hack with: t = 1,n = 10^5 and all a[i] = 10^9 gives invalid input?
 » 18 months ago, # |   +53 I spend about 1 hour on D......the solution is easy but it's hard to code :(
•  » » 18 months ago, # ^ |   +8 Cant' agree more.
 » 18 months ago, # |   0 How to solve D any hints? do we construct some kind of graph?
•  » » 18 months ago, # ^ |   0 use dp
•  » » 18 months ago, # ^ |   +1 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
 » 18 months ago, # |   +8 I think the examples of the problems are so easy that it makes me be not able to find the bugs.
 » 18 months ago, # |   +46 I just loved $E$. Nice puzzle. Here's a small hint for those interested: HintSay you try to trap the king in a rectangle and slowly try to make this rectangle smaller. The issue here is that the king might escape this rectangle if you reach it's column or row. To avoid that, can you try to keep the column parity and row parity of the queen and king different after every queen's move?
•  » » 18 months ago, # ^ |   +19 Okay, as the editorial solution is entirely different, I will describe my solution here (which I liked better). SolutionLet's say you are at $(1, 1)$ and you don't know exact current coordinates of the king, but let's assume they are both even and it's the king's move now. We will try to maintain that the king's coordinates are both always of parity different than the queen's after our move.In the king's move, the king will have to change the parity of either it's row or column or both. Whatever he does, we maintain the opposite parity of both the row and column, moving towards the king. Specifically, let $dx$ be $1$ if and only if the king changes row parity and $dy$ be $1$ if and only if king changes column parity. If we are at $(x, y)$ right now, we move to $(x+dx, y+dy)$.Note that we never stay at the same place. Also, note that we never match the king's row or column. This ensures that the king remains trapped in a rectangle, whose size we keep reducing. We can see that in at most $12$ moves, we definitely trap the king.But, this is all fine considering the big assumption we made about the parities regarding the king's initial position. How do we trap the king without this additional info? The trick is that we can repeat a similar process assuming all the $4$ different possibilities for the king's initial position, with small changes.Overall we take at most $4 \times 12$ moves to trap the king over all attempts, and at most $3 \times 2$ moves to initialize the condition based on assumed parities for the next attempt. Thus, we need at most $54$ moves.Code: 125400662
 » 18 months ago, # |   +3 Solution for DFirst of all convert all the given ranges to <= 6e5 by hashing. Let's take an array dp with size of the maximum value in ranges and iterate rows from 1 to n. dp[i] indicates the maximum length of the rows taken in the grid where the last row contains 1 at index i. Now for ith row we need to find max(dp[k]) where ith row kth column contains 1 and we need to set dp[k] = max+1. Finally the answer is the maximum value in the dp array. You can do backtracing similarly to find what all rows we should take. We can use segment trees with lazy propagation for range maximum and range set queries.
•  » » 18 months ago, # ^ |   0 I’m getting WA on Test Case 4 with this approach :(
•  » » » 18 months ago, # ^ |   0 Yeah, I also got that first but I found the bug in my implementation and corrected it.
 » 18 months ago, # | ← Rev. 3 →   0 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.
 » 18 months ago, # |   +2 How to solve C?
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 SpoilerFor ith bit let the win be b[1]&b[2]...&b[n]>b[1]^...^b[n] and draw be b[1]&b[2]...&b[n]=b[1]^...^b[n] where b[j] is the ith bit of the jth element. Let dp[i] be the answer till ith bit (all elements < pow(2,i). Iterate from 1st bit to kth bitif i == 1 => dp[i] = number of ways to draw + number of ways to win for ith bit. else => dp[i] = (number of ways to win for ith bit)*(all possible values before ith bit = pow(2,i*n)) + (number of ways to draw for ith bit)*dp[i-1]dp[k] is the ans.
 » 18 months ago, # |   +28 Your example is so stronger that every wrong code can pass!
•  » » 18 months ago, # ^ |   0 Weak example,STRONG pretest.
 » 18 months ago, # | ← Rev. 2 →   +3 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
 » 18 months ago, # |   -11 Got TLE on C because of 32-bit python.Very annoying.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 nevermind
 » 18 months ago, # |   +8 why you bully me , codeforce ?
 » 18 months ago, # | ← Rev. 4 →   +169 What the fuck? I randomly submitted this pattern in E and it passed pretests.(Edit : It passed system test)
•  » » 18 months ago, # ^ |   +28 This solution made me feel disappointed :(
•  » » 18 months ago, # ^ |   +3 And now you will become CM XD. Congrats
•  » » 18 months ago, # ^ |   0 and now it's Accepted. wtf
•  » » » 18 months ago, # ^ |   0 This might be somehow the solution..? Main test had 7000 individual games and it all worked.
•  » » » » 18 months ago, # ^ |   +20 Nope. It's wrong. It's just hard to make an opponent to counter all such solutions I guess.
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 18 months ago, # ^ |   0 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.
•  » » 18 months ago, # ^ |   0 And it turns out to be AC in main test.
•  » » 18 months ago, # ^ |   +6 I can think of a test case where this solution doesn't work. The system tests are weak.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +76 If the gif doesn't work, go to here
•  » » » 18 months ago, # ^ | ← Rev. 3 →   -30 ok
•  » » 18 months ago, # ^ |   +3 I just continue to go in reverse path and it passed main tests. Indeed the solution above fails only last test.
 » 18 months ago, # |   +3 Nice round guys, I enjoyed the problems :D
 » 18 months ago, # |   0 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$
•  » » 18 months ago, # ^ | ← Rev. 3 →   +4 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.
•  » » 18 months ago, # ^ |   +4 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$.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +5 Video solution, you can also convert the recurrence into a 1D DP (DP solution).
 » 18 months ago, # |   0 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!
 » 18 months ago, # |   0 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?
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Clean dp: dpint main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif using mint = modint; auto solve = [&]() { int N, K; cin >> N >> K; mint eve = qpow(mint(2), N - 1), q = eve * 2; if (N % 2 == 0) { eve--; } array dp = {0, 1}; for (int i = 0; i < K; i++) { array ndp = {dp[0] * q, dp[1] * eve}; ndp[N % 2] += dp[1]; swap(ndp, dp); } cout << dp[0] + dp[1] << '\n'; }; int t = 1; cin >> t; while (t--) { solve(); } return 0; } 
•  » » » 18 months ago, # ^ |   +2 not sure what I have done dp: ugly dpint n, k; cin >> n >> k; if(k == 0){ cout << "1\n"; return; } int pown = power(2, n); vector pow_2(k); for(int i = 0; i < k; i++){ if(i == 0) pow_2[i] = 1; else{ pow_2[i] = pow_2[i-1]*pown; } pow_2[i]%=mod; } int ans = 0; int pref = 1; int odd=0; int even = 0; for(int i = 0; i < n; i++){ if(i%2 == 0) even += C(n, i); else odd += C(n, i); even %= mod; odd %= mod; } if(n%2 == 1)even++, even%=mod; //debug(even, odd); for(int i = k-1; i >= 0 ; i--){ int curr = pref; curr *= odd; curr %= mod; curr *= pow_2[i]; curr %= mod; pref *= even; pref%=mod; ans += curr; ans %= mod; } //debug(ans); ans = power(2, n*k)-ans; if(ans < 0)ans+=mod; ans %= mod; //debug(ans); cout << ans << '\n'; 
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 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.
 » 18 months ago, # | ← Rev. 2 →   -14 great contest
•  » » 18 months ago, # ^ |   0 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
 » 18 months ago, # |   +35 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.
 » 18 months ago, # |   +8 one of the most balanced div 2s ever. Kudos to the authors !!
 » 18 months ago, # | ← Rev. 4 →   +25 I thought constraints to be different for C, so I solved it for $T <= 10^5$. Solution$ans = 2 ^ {N*K} - loss * {(L ^ K - 1) / ({L - 1})} * draw ^ {K - 1}$Where $L = 2 ^ n / draw$ Draw is the number of ways in which $N$ bits can be set such that $cumulative and = cumulative xor.$ Loss is the number of ways in which $N$ bits can be set such that $cumulative and < cumulative xor.$ Code: 125392751
 » 18 months ago, # |   0 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
•  » » 18 months ago, # ^ | ← Rev. 3 →   +1 Here's my code full code: https://codeforces.com/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<
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 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!!!!
•  » » » » 18 months ago, # ^ | ← Rev. 5 →   0 When n is odd:Because there won't be any case such that a1&a2&a3.... > a1^a1^a3Max, 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
•  » » » » » 18 months ago, # ^ |   0 Ya I get it sorry I changed the comment I think both the codes are same!!!
•  » » » » 18 months ago, # ^ |   0 here's using loop :https://codeforces.com/contest/1557/submission/125409932
•  » » » » » 18 months ago, # ^ |   0 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 :)
•  » » » 18 months ago, # ^ |   0 Could you elaborate on your logic?
•  » » » » 18 months ago, # ^ | ← Rev. 3 →   +3 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
 » 18 months ago, # |   +10 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   -76 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 :) :) :)
•  » » » 18 months ago, # ^ |   +3 May you get the most downvotes anyone has ever received!
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +9 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. :)
•  » » » » » 18 months ago, # ^ |   0 you are a div1 alt....go and participate in div1 if u have balls
•  » » » » » » 18 months ago, # ^ |   0 I have participated in div1.... But it has nothing to do with "div1". Anyway,this round is awful.
•  » » » » » 15 months ago, # ^ |   0 Having participated myself I want to say that this round’s truly not-so-good. Have myself puzzled throughout the contest.
•  » » » » » » 15 months ago, # ^ |   0 Had,not have. Sorry:)
•  » » 18 months ago, # ^ |   0 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？:)
•  » » » 12 months ago, # ^ |   0 at least we dont have the server down this time so calm down
 » 18 months ago, # |   +3 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.
 » 18 months ago, # | ← Rev. 2 →   +3 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.com/contest/1557/submission/125390194I guess the setter didn't include this test in the system test.
•  » » 18 months ago, # ^ |   0 1
•  » » » 18 months ago, # ^ |   0 https://codeforces.com/contest/1557/submission/125390194This accepted code gives 0.
•  » » » » 18 months ago, # ^ |   0 Weak system tests ig
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 K>=1UPD: K>=0 Looked at the wrong problem. My bad.
•  » » » 18 months ago, # ^ |   0 No it clearly says $0 \leq k \leq 2\cdot10^5$https://codeforces.com/contest/1557/problem/CAnd the third sample case even has $k=0$, so idk what you're talking about.
•  » » 18 months ago, # ^ |   -9 Mo2men MikeMirzayanov Sorry for tagging.
 » 18 months ago, # |   +3 Why the verdict of my submission is still Pretests passed? Problem B
•  » » 18 months ago, # ^ |   0 Lol
•  » » 18 months ago, # ^ |   0 I have the same problem too, please rejudge!
 » 18 months ago, # | ← Rev. 2 →   0 why do tled guys not retested? seems like some correct solns for problem A got TL
•  » » 18 months ago, # ^ |   +3 They got TLE as they used double/long double to take input if they take int/long long to take input they will passhttps://codeforces.com/contest/1557/submission/125409517 (77 ms with int)https://codeforces.com/contest/1557/submission/125406647 (998 ms because of long double)
•  » » » 18 months ago, # ^ |   +3 998ms still passes, but on systests it wouldn't pass
 » 18 months ago, # | ← Rev. 2 →   +12 A bad round:((((((
•  » » 18 months ago, # ^ |   +8 Yes I agree.
 » 18 months ago, # |   +20 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. Spoilermap Results={ {"Done",DONE}, {"Right",{0,1}}, {"Left",{0,-1}}, {"Up",{-1,0}}, {"Down",{1,0}}, {"Down-Right",{1,1}}, {"Down-Left",{1,-1}}, {"Up-Left",{-1,-1}}, {"Up-Right",{-1,1}}, }; 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.
•  » » 18 months ago, # ^ |   +27 Authors have just detected if you are able to write easy-to-debug/support code Clickif (s.find("Left") != string::npos) y--; if (s.find("Right") != string::npos) y++; if (s.find("Up") != string::npos) x--; if (s.find("Down") != string::npos) x++; 
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +8 Trying hard to learn/write easy-to-debug/support code. Thanks for the tip.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +1 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 ¯\_(ツ)_/¯
 » 18 months ago, # |   +1 From HTI thanks Assiut university for the great ICPC community you made :)
 » 18 months ago, # |   +1 I know I have poor abilities, butHow CRAZY the weak examples are!
 » 18 months ago, # |   0 Gave this round could only solve 2, but expected I would at least not be unrated anymore. Why am I still unrated?
•  » » 18 months ago, # ^ |   0 wait for a few hours
 » 18 months ago, # | ← Rev. 2 →   0 My solution for problem B remains the verdict "pretest passed". What's happening?
 » 18 months ago, # | ← Rev. 2 →   +30 My solution for problem A got TLE on test case 2 on system tests (https://codeforces.com/contest/1557/submission/125328000)After submitting the same code after system tests, it got AC (https://codeforces.com/contest/1557/submission/125407093)If its possible to rejudge my submission, please do so.UPD : Submission got rejudged and got AC!
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 18 months ago, # ^ |   +3 reading long doubles is slow, also it's common practice to retest some tled submissions after the contest, because of server load
•  » » » 18 months ago, # ^ |   +6 Printing floats with 20 precision. Just reduce it to 8. I too sorted but ACed in less than 100 ms.
•  » » 18 months ago, # ^ |   0 What if it continues to get tle
•  » » 18 months ago, # ^ |   0 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 :(
 » 18 months ago, # |   +3 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.
 » 18 months ago, # |   +65 ??? I wonder how this can be accepted 125408147It just move like this ↓And this worth 3000 points, the sum of Problem A, B, C.
•  » » 18 months ago, # ^ |   +19 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.
•  » » » 18 months ago, # ^ |   +16 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.
•  » » 18 months ago, # ^ |   0 just realized this picture is from an earlier comment lul
 » 18 months ago, # |   +9 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.
 » 18 months ago, # |   +209 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.
•  » » » 18 months ago, # ^ |   +15 Yes commonly I'm a gentle girl but this round really annoy me.
•  » » 18 months ago, # ^ |   +4 Can’t agree more :) The contest is so perfect that I even used my rating drop to gain contribution :)
•  » » 18 months ago, # ^ |   +8 I've seen a lot of words spouted about the rounds, but I haven't seen such euphemisms.
 » 18 months ago, # | ← Rev. 2 →   +11 Solution to E that passes tests with a limit of 21 queries per test case. 125414030
 » 18 months ago, # | ← Rev. 2 →   -39 Deleted
• »
»
18 months ago, # ^ |
Rev. 2   -32

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

•  » » » 18 months ago, # ^ |   0 Thanks for the help...understood it...taking input a double value takes longer time than int...so we should avoid it if possible :)
•  » » 18 months ago, # ^ |   +1 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
 » 18 months ago, # |   0 nice problemset, hard and interesting
 » 18 months ago, # |   0 Out of curiosity, how did problemsetters create interactor for problem E? Seems hard.
•  » » 18 months ago, # ^ |   +31 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...
 » 18 months ago, # |   +27 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 18 months ago, # ^ |   +20 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
•  » » » 18 months ago, # ^ |   0 Everyone in codeforces doesn't have time to read every comment in every blog, unlike some people.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 Lol that's the contest blog such a comments always gets deleted
 » 18 months ago, # |   -117 Good conpetition.But it's a pity that I miss it.
•  » » 18 months ago, # ^ | ← Rev. 3 →   -6 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.
•  » » » 18 months ago, # ^ |   +33 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 statementsWhat is the deal with a lot of people complaining? Is it just a lot of people ranting who weren't satisfied with their performance?
•  » » » » 18 months ago, # ^ |   -8 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.
•  » » » » 18 months ago, # ^ |   0 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.
•  » » 18 months ago, # ^ |   +29 I think you'd better evaluate the contest after reading the problems!
•  » »