### AliShahali1382's blog

By AliShahali1382, history, 11 days ago,
$~-\text{In the name of God}~-$

Hello Codeforces,

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

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

Thanks for our testers 300iq, growup974, Atreus, Shayan.P, postscript, morzer, BledDest, UnstoppableChillMachine, MAMBA, Prabowo, WNG for testing and giving very helpful advice.

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

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

Scoring distribution:

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

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

UPD : Editorial is out.

• -371

 » 11 days ago, # |   +169 Auto comment: topic has been updated by AliShahali1382 (previous revision, new revision, compare).
•  » » 10 days ago, # ^ |   +118 100 upvote just for update :(
•  » » » 10 days ago, # ^ |   +59 I dont know why but Im ok with it :))
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   +144 ()
•  » » 7 days ago, # ^ |   +68 Sir, editorial isn't accessible. Could you please look into it?
 » 11 days ago, # |   +550 As a Monogon give me contribution.
•  » » 11 days ago, # ^ |   +420 give me too :))
•  » » 11 days ago, # ^ |   +496 That doesn't even make sense but ok.
•  » » 10 days ago, # ^ |   +83 Would you mind if I steal this comment next round announcement
•  » » » 10 days ago, # ^ |   +60 No bro
•  » » 10 days ago, # ^ |   +99 :)
•  » » 10 days ago, # ^ |   +139 Experience has shown that it always works to get contribution.
•  » » » 10 days ago, # ^ |   +137 Even this comment is just for contributions:)
•  » » » » 10 days ago, # ^ |   -50 And this one ???
•  » » » » 10 days ago, # ^ |   +16 Fun posts? khkhkhkhkhkhkh
•  » » » » 9 days ago, # ^ |   0 I think I must become master to get more upvotes and respects from newbies. XD lol kek wtf omg
•  » » » » 8 days ago, # ^ |   -11 Dahane maro saf kardi ba contribution Translate:you just want contribution it sesms you never had contribution!!
•  » » 9 days ago, # ^ |   -30 me too!
 » 11 days ago, # |   +146 Been waiting for these guys' contest for a long time now! Hope y'all ready for a fun contest :)
•  » » 10 days ago, # ^ |   +17 AYYYY
 » 11 days ago, # |   -46 It's time to return an expert
•  » » 10 days ago, # ^ |   +9 I became 1899 Expert yesterday just to lose the div 1 contest. FeelsBadMan
•  » » » 10 days ago, # ^ |   +10 No Problem. It will be great round for you as you know...
•  » » » » 10 days ago, # ^ |   +3 I hope.
•  » » 10 days ago, # ^ |   +18 Hey, at least you could get a girlfriend.
•  » » » 10 days ago, # ^ |   +8 I must say that this post has many truths
•  » » » 9 days ago, # ^ |   0 Now, I have one more reason to become Blue.
•  » » » 9 days ago, # ^ |   0 just needed this sort of motivation
 » 11 days ago, # |   +242 As a student of the writers, i'm sure the contest will be good because they are geniuses.
•  » » 10 days ago, # ^ |   +166 Yeah and we are forced to participate and upvote the blog and all of the comments XD
•  » » » 10 days ago, # ^ |   +73 yeah because they're teaching you to respect to older's contests
•  » » » » 10 days ago, # ^ |   +56 they are one year older but yes youre right. : )
•  » » » » » 10 days ago, # ^ |   +69 sure I am. because I'm one year older than you too.
•  » » » 10 days ago, # ^ |   +28 :)))i'll see you next week
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   +49 Aria 2003-2020
•  » » » » » 10 days ago, # ^ |   +8 RIP
•  » » » 10 days ago, # ^ |   +4 It is fun to participate in our seniors contest. I hope it will be good. but there is a high chance that it will be bad. Hope it wont get unrated. XD
•  » » » » 10 days ago, # ^ |   +11 If it get unrated you should pay us (300$) :)) •  » » » » » 10 days ago, # ^ | +8 there are 15 students in the class. why do you always want to get the money from me? •  » » » » » » 10 days ago, # ^ | +9 ok. each of you pay us 300$ :))
•  » » » » » » » 10 days ago, # ^ | ← Rev. 2 →   +3 thats bad but atleast fair!!!
•  » » » » » » » 10 days ago, # ^ |   0 except MahdiGMK
•  » » » » » » » » 10 days ago, # ^ |   0 XDDDD
•  » » » » » » » 10 days ago, # ^ |   0 first of all they must give you pizza for the contest
•  » » » » » » » » 10 days ago, # ^ |   +8 they are getting the money for the contest! why should we give them a pizza??? they should give us pizza!!!
•  » » » » » » » » » 9 days ago, # ^ |   +7 Maybe you guys should try harder for the pizza =)
•  » » 10 days ago, # ^ |   +12 are you a fan of FC barcelona?
•  » » » 10 days ago, # ^ |   +63 yes.
•  » » » » 10 days ago, # ^ |   +37 i was also ,but after last three years it is very hard to support barca.SED LIFE
•  » » » » » 10 days ago, # ^ |   +68 as a fan, you have to support the team to get back to its good days. given the current situation and the change of manager, I believe in this team : )
•  » » » » » » 10 days ago, # ^ |   +39 yes i also believe.visca el barca
•  » » » » » » » 10 days ago, # ^ |   +58 orz
•  » » » 10 days ago, # ^ |   +2 Yes
•  » » » 10 days ago, # ^ |   +14 As a problem setter : Two of problem seters is fan of barca :)
•  » » 10 days ago, # ^ |   -10 Dogs are coming...
 » 11 days ago, # |   +1 Why is Postscript a tester in soo many rounds? Is he really friends with so many contest writers? Hmm.. strange
•  » » 11 days ago, # ^ |   +59 People with testing experience are often asked to be testers again.
•  » » 11 days ago, # ^ |   +137 And I am testing the rounds without asking for you know what I want.
 » 11 days ago, # |   +129 As a tester(Don't down vote!), I think it would be an interesting round!
•  » » 10 days ago, # ^ |   +44 Do not think, be sure
•  » » » 10 days ago, # ^ |   +27 you forgot to write "as a problem setter" in the beginning of your comments.
•  » » » » 10 days ago, # ^ |   0 :) :)
 » 10 days ago, # |   0 So we have a subtask in problem A of Div2?
•  » » 10 days ago, # ^ |   +5 I guess you saw the Div 1 scoring, for us its on Problem C that we have two subtask
•  » » » 10 days ago, # ^ |   0 yeah Sorry my bad :P
•  » » 10 days ago, # ^ |   +8 No. In problem C actually.
•  » » 9 days ago, # ^ |   0 There is a subtask in problem C of Div2 and problem A of Div1. Actually Div2 problem C is the problem of A of Div1.
 » 10 days ago, # |   +4 Can someone tell me why div3 is not happening ??
•  » » 9 days ago, # ^ |   0 It will happen very soon.
 » 10 days ago, # |   0 what does (750+750) mean , is it its a combination of 2 750 problems or just 1500 level problem ?
•  » » 10 days ago, # ^ |   +13 it means problem c in div 2 has two parts
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 10 days ago, # ^ |   0 In problem D1 and D2 of Codeforces Round #671 (Div. 2).
•  » » » » » 10 days ago, # ^ | ← Rev. 2 →   0 also in last contest div 2's problem F had two versions
•  » » 10 days ago, # ^ |   0 it always means problem c has two different situations need to be solved.or problem c should be like just (1000+500) or something else.
 » 10 days ago, # |   +27 Good luck bruh!
 » 10 days ago, # |   0 I guess I should say, OMG another Iranian round!!!
•  » » 9 days ago, # ^ |   -14 NO MORE IRANIAN ROUND!
 » 10 days ago, # |   -139 IslamForces
•  » » 10 days ago, # ^ |   +29 Religion is free of CodeForce or anything unrelated to it
•  » » 9 days ago, # ^ |   0 Wrong comment bro ,both morally and statistically
 » 10 days ago, # |   +15 Ahsant! =)
•  » » 10 days ago, # ^ |   -56 احسنت
 » 10 days ago, # | ← Rev. 2 →   +3 See you tomorrow night :)(P.S UTC 14:35 = UTC+8 22:35)
 » 10 days ago, # |   +3 I am really excited to see what my friends have prepared after putting a lot of effort into it :)))
 » 10 days ago, # |   +3 I wish you write a lot of rounds from now
 » 10 days ago, # |   -28 plz put some good easy problems for interview prep.
•  » » 10 days ago, # ^ |   +3 For Interview type Questions goto leetcode,gfg or interviewbit.
•  » » » 10 days ago, # ^ |   +3 yeah bruh btw what is ur rating on codechef?
•  » » » » 10 days ago, # ^ |   +3 I don't know what you will do with it but anyway, 1854.
 » 10 days ago, # |   -41 Good luck for GodForces!
 » 10 days ago, # |   -47 −In the name of God −Very happy to see that
•  » » 10 days ago, # ^ |   -26 god would be proud XD
•  » » » 10 days ago, # ^ |   -31 I'm pretty sure god never said anything about codeforces contests... these people talking in his name... must be frustrating for him
•  » » » » 10 days ago, # ^ |   0 You guys are talking about the God as a person!that's a pity
•  » » » » » 10 days ago, # ^ |   -27 Because he shouldn't be brought here in CF... what is the plus value of writing "In the name of God", this is literally believing without understanding
•  » » » » » » 9 days ago, # ^ |   +8 Before everything we say "In the Name of God" that's the real believing
•  » » » » » » » 9 days ago, # ^ | ← Rev. 2 →   -8 Whatever.
•  » » » » » » » » 9 days ago, # ^ |   +4 Reply to your Rev.1no one did "targeting Non-Muslim people" and it isn't what Muslims do. what you said at the first was considered offensive (at least to some people's beliefs) and what you said now...look, it's obvious that you don't know Muslims and that's the reason you think like that"being an honest and good person" is what a real Muslim try to be and seriously you're wrong when you say "I'm pretty sure you like to do these things to get free Hassanate" because that's not what they're doing they're just defending their beliefs without expecting "Hassanate".I offer to finish talking about this in CF and research and read about other religions before commenting about them (not just talking about what we heard about them)
•  » » » » » » » 9 days ago, # ^ |   +19 Telling people what "real believing" is. Very clever.Did you notice that we no longer live in the Middle Ages?
•  » » » » » » » » 9 days ago, # ^ |   0 Actually, there're some people still living in the Middle Ages or even before that :)
•  » » » » » » » » » 9 days ago, # ^ |   0 it's very funny hearing that from you XD
•  » » » » 9 days ago, # ^ |   -8 we muslims do everything In the name of god so we never forget about god and be thankful that we can do this!!!
•  » » » » » 9 days ago, # ^ |   +5 everything?
•  » » » » » » 9 days ago, # ^ |   -6 Yup. There are even dua's regarding pissing, pooping, sex etc.
•  » » » » » » » 8 days ago, # ^ | ← Rev. 2 →   0 This is racism!!! If you wanna know about islam you can go research! But saying things like this is too offensive
•  » » » » » » » » 8 days ago, # ^ |   +10 what is the relation between racism and this? gheime haro tu masta nariz pls :<
•  » » » » » » » » » 8 days ago, # ^ |   -9 kids pls dont come to adults conversations!
•  » » » » » » » » » 7 days ago, # ^ |   0 Because Islam is a race. /s
•  » » » » » 9 days ago, # ^ |   0 Why not put some more exclamation marks behind it? Looks super clever.
•  » » » » » » 9 days ago, # ^ |   +3 Good question
 » 10 days ago, # | ← Rev. 2 →   -32 Yeah...... Again, some of the medalists of the Iranian Computer Olympiad I wish we had this again!
•  » » 9 days ago, # ^ |   -8 Why did you give a negative rating to my comment? Did I say something bad?
•  » » » 9 days ago, # ^ |   +11 Laughing My Freaking A*s Off :)
 » 10 days ago, # |   -35 .
 » 10 days ago, # |   0 Wa alaykumu s-salam AliShahali1382
•  » » 10 days ago, # ^ | ← Rev. 3 →   +7 we speak persian, we just say salam. thats arabic.
•  » » » 10 days ago, # ^ |   0 salam suto82
•  » » » » 10 days ago, # ^ |   +32 salam be rooye mahet.
•  » » » » » 9 days ago, # ^ |   +18 Be cheshmune siahet =)
•  » » » » » » 9 days ago, # ^ |   +3 lol
 » 10 days ago, # |   0 nice contest *2
 » 10 days ago, # |   +2 Peaceful Round !
 » 10 days ago, # |   +25 I hope these guys would be as much good writers as they are great people and contestants.
•  » » 10 days ago, # ^ |   +37 ‌But I hope these guys would be good writers.
•  » » 10 days ago, # ^ |   0 I think the hardest part of the questions is to understand the statements. be ready for it!!!
•  » » » 10 days ago, # ^ |   +6 Thanks to isaf27 statements are easy to understand
 » 10 days ago, # |   -44 I am an atheist. Am i allowed to participate ?
•  » » 10 days ago, # ^ |   +7 Everyone can participate in the contest
 » 10 days ago, # |   -140 Problem D's Title: SpoilerRabin Carp and Allahu AkhbarProblem E's Title: SpoilerRabin Carp is no more
•  » » 10 days ago, # ^ |   +36 HAHA That's not funny
•  » » 9 days ago, # ^ |   0 Is it really funny to do that???
 » 10 days ago, # |   -67 why grey coder when comment anything gets down votes and whereas Red coders get up votes.I have already negative contribution I am sure I will increase more from this comment as well.
•  » » 10 days ago, # ^ |   +31 because they write comments related to the blog post :)
•  » » 10 days ago, # ^ |   -62 Not gonna let you down bro. U have my upvote , this world is not a nice place.
•  » » 9 days ago, # ^ |   +13 ratism
•  » » 9 days ago, # ^ |   -9 well simply becoz they are red. that's how it goes
•  » » » 9 days ago, # ^ |   -12 lol, now you ready to loose contribution.
•  » » » » 9 days ago, # ^ |   -11 u never know ,after all, humanity is still left in this world
 » 10 days ago, # |   -38 I like the starting — In the name of God.
•  » » 9 days ago, # ^ |   +31 no one cares
•  » » » 9 days ago, # ^ |   -9 What causes a person to be toxic?
•  » » » » 9 days ago, # ^ |   +7 This penetrating display of one's own faith. It's like waving your penis. Nobody wants to be bothered with it.
 » 10 days ago, # |   -51 −In the name of God −i am happy to see that, thank u ^^
 » 10 days ago, # |   +8 what is polygon platform that is mentioned in post?(I am new I don't know, I am sorry if i asked wrong question!!)
•  » » 10 days ago, # ^ |   +3 Polygon is a service to prepares programming problems and contests
•  » » » 10 days ago, # ^ |   0 ohk got it thanks Mohammad.H915 and rifatrraazz
•  » » 10 days ago, # ^ |   +7 Polygon is the problem setting platform of CodeForces. There you can prepare problems. Write statement, checker code, validator code, generate testcases, add different types of solutions (ac, wa, tle etc) and run them. Explore ownself: Polygon
 » 10 days ago, # |   0 After a long break i am again join in CF contest. I hope now i can give a rank push :)
 » 10 days ago, # |   0 Great to see few consecutive rounds, I must say I started losing confidence in between last 2weeks gap, regular contests are fun in many aspects. Hopefully I would be able to increasing my rating, and most importantly enjoy solving the tasks.
•  » » 9 days ago, # ^ |   0 Yes, you will be able to increase your rating. Hopefully me too. I want to reach specialist again.
•  » » 8 days ago, # ^ |   +5 good luck
 » 10 days ago, # |   0 how should i prepare with my strong arms??!
 » 9 days ago, # |   0 Yeah Again, some of the medalists of the Iranian Computer Olympiad I wish we had this again! Good luck! Just do not take photos of the comments and send them to the groups :)
 » 9 days ago, # |   +1 I have a doubt. I registered for this contest before last one as a candidate master but now i am expert and it is showing me as registered in div1. Can i participate in div1 if i want to do so by not unregistering myself from div1? And if i do so what about rating changes, will they be changed relative to div1 participants only?
•  » » 9 days ago, # ^ |   +2 There is also some purple participants in div2 as wellhttps://codeforces.com/contestRegistrants/1440?order=BY_RATING_DESC
•  » » » 9 days ago, # ^ |   0 Yes, i meant in both cases (mine as well as vice-versa). Definitely, we have option of registering with correct divisions too. I wanted to ask whether there is any guideline or rule which we need to follow in such scenario or it completely depends on our wish?
•  » » » » 9 days ago, # ^ |   0 I would suggest that you participate in the correct division. The fact that is technically possible to register for the wrong one is a weak legitimation to do so. I mean, what rule would make sense to you?
 » 9 days ago, # | ← Rev. 2 →   -58 apparently, not many people liked this light joke.
•  » » 9 days ago, # ^ |   -19 Nope, no one does, do you think being edgy is funny? Grow the fuck up orphan
 » 9 days ago, # |   +11 Excited for this contest?please don't make it unrated.
 » 9 days ago, # |   -13 Hey Guys, check https://gameofcodes.herokuapp.com for practicing weak and strong topics and much more!
 » 9 days ago, # |   -15 few bad comments on (In the name of the god)where did these people go? are you ok?
•  » » 9 days ago, # ^ |   0 Of course But I think these were jokes :) But in any case, it was not the right thing to do !!
 » 9 days ago, # |   0 what is special about problem C?
•  » » 9 days ago, # ^ |   0 There will be an easy and a hard version of this problem.
 » 9 days ago, # |   0 Wish you high scores and good luck! Little wish to become blue:)
 » 9 days ago, # | ← Rev. 6 →   -7 I think there will be two versions of problem C based on constraints. Which one is better to solve? 1.Solving C1 and C2 both at a time. 2.Solving C1 first and then move to C2.
 » 9 days ago, # |   -35 newbie needs some contribution here.....
•  » » 9 days ago, # ^ |   -18 a man sees newbie................. a man immediately downvotes...............
•  » » 9 days ago, # ^ |   0 what's the point of getting free contributions ??
•  » » » 9 days ago, # ^ |   +5 Why don't u ask Monogon that question xD
•  » » » » 9 days ago, # ^ |   +7 100 upvotes and I'll answer.
•  » » » » » 9 days ago, # ^ |   0 ok i have already contributed to your score
•  » » » » » 9 days ago, # ^ |   +3 Btw this is the first time a red coder has replied to me xD(I know I tagged you but still)
•  » » » » » » 9 days ago, # ^ |   +3 Is this the second time?
•  » » » » » » » 9 days ago, # ^ |   0 third time my watch is 20 minutes fast
•  » » » » » » » 9 days ago, # ^ |   +23 Pussy+ lots of salt
•  » » » » » » 9 days ago, # ^ |   0 LOL! do you consider them same as verified account on twitter?
•  » » » » » » » 9 days ago, # ^ |   0 Nah,just it was a first time
•  » » » » » 9 days ago, # ^ |   +26 That doesn't even make sense but ok.
 » 9 days ago, # |   -52 Upvote my comment and i ll pray for you to solve atleast 3.
 » 9 days ago, # |   +18 My first time participating in a Div 1 contest. Very Excited to participate in this round and also do let me know if there are any new strategies that I need to employ in Div1 contests xD :)
•  » » 9 days ago, # ^ |   +9 Yeah just ask for strategies from your competitors, don't see how that can go wrong.PS: Jk ofc, most of the people here help each other for healthy competition.
 » 9 days ago, # |   -58 Dear scrollers, Stop ! Would you make my contribution positive ? No -> Keep scrolling Yes -> Upvote this commentThanks regardless May the force be with you
 » 9 days ago, # |   -52 Guys actually this is my 2nd account my first account is red ....so i want to all to spam that upvote button and as a return gift i will wish for your best performance . PS: I am a GodMan ....my wishes are always fullfilled.
•  » » 9 days ago, # ^ |   +17 solve atleast 3 problems and i will upvote you.
•  » » » 9 days ago, # ^ |   0 Ok bro i will... :-)
•  » » » » 9 days ago, # ^ |   +7 So how many have you solved?? XXDDD
•  » » » » » 9 days ago, # ^ |   -51 Shutup you idiot bot
•  » » 9 days ago, # ^ |   0 Gave 5 contests and still a newbie XD, and says that he is red, ohh come onnnnn XD
 » 9 days ago, # |   +6 best of luck everyone 5 min left!!!!!!!!!!!!!!!!!
 » 9 days ago, # |   -9 May God provide a higher rating to all and me.
 » 9 days ago, # |   -29 is it rated ?
•  » » 9 days ago, # ^ |   +3 Why we still here, just to suffer.....
 » 9 days ago, # |   +14 For Div2C2/Div1A2, I write more than 200+ lines of code to handle edge case when n or m is odd. Although I can think clear how to solve it, but it is too complicated and I give up. There must be some simpler ways, good question!
•  » » 9 days ago, # ^ |   0 I bricked on only one case where the grid is full filled and both n and m are odd, in that case I print the answer as nm + 2. Man it took me ages to compensate this 2, still dont know how do we do it :(
•  » » » 9 days ago, # ^ |   0 You only need to solve the 2x2, 2x3 and 3x2 cases. You can then model all n, m into those cases. I bruteforced all costs of strings, made them into linear string instead of grid and tried implementing. I had this one bug in both n and m odd case which I couldn't find which made me mad and I gave up.
•  » » » » 9 days ago, # ^ |   0 I see some hints from other reviews, actually we just need to transform the last odd row and column to all zero first, then solve remaining grid by 2x2 as previous did
•  » » » » » 9 days ago, # ^ | ← Rev. 2 →   +5 that's exactly what I did.but the implementation costed a total of 90 mins (debugging time included) Accepted - XXL size code#include using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* ch) { return to_string((string)ch); } string to_string(char ch) { return (string)"'" + ch + (string)"'"; } string to_string(bool b) { return (b ? "true" : "false"); } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(A a) { string res = "{"; bool first = true; for(const auto& x: a) { if(first == false) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug() {cerr << "]\n";} template void debug(H head, T... tail) { cerr << to_string(head) << " "; debug(tail...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << " ] = ["; debug(__VA_ARGS__); #else #define debug(...) #endif const int maxn = 111; vector a (maxn); vector> ans; void F (char &c) { if (c == '0') c = '1'; else c = '0'; } pair ff(int x, int y, int code) { if (code == 0) { x--, y--; F(a[x][y]); return make_pair(x, y); } if (code == 1) { x--; F(a[x][y]); return make_pair(x, y); } if (code == 2) { x--, y++; F(a[x][y]); return make_pair(x, y); } if (code == 3) { y++; F(a[x][y]); return make_pair(x, y); } if (code == 4) { x++, y++; F(a[x][y]); return make_pair(x, y); } if (code == 5) { x++; F(a[x][y]); return make_pair(x, y); } if (code == 6) { x++, y--; F(a[x][y]); return make_pair(x, y); } y--; F(a[x][y]); return make_pair(x, y); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; int N = n; int M = m; ans.clear(); for (int i = 0; i < n; i++) { cin >> a[i]; } int CNT = 0; auto f = [&] (int x, int y, vector code) { CNT++; // x++, y++; vector ret; for (auto& i: code) { pair p = ff(x, y, i); ret.push_back (p.first + 1); ret.push_back (p.second + 1); } assert ((int) ret.size() == 6); ans.push_back (ret); // return ret; }; if (n % 2 == 1 && m % 2 == 1 && a[n - 1][m - 1] == '1') { f (n - 2, m - 1, {5, 6, 7}); } if (n % 2 == 1) { // if (a[n - 1][0] == '1') { // f (n - 1, 0, {1, 2, 3}); // } for (int j = 0; j < m; j += 2) { int x = j; int y = j + 1; if (y >= m) continue; if (a[n - 1][x] == '1' && a[n - 1][y] == '1') { f (n - 1, x, {1, 2, 3}); f (n - 1, y, {7, 0, 1}); } else if (a[n - 1][x] == '0' && a[n - 1][y] == '0') { // nothing } else if (a[n - 1][x] == '0') { f (n - 1, x, {1, 2, 3}); } else if (a[n - 1][y] == '0') { f (n - 1, y, {7, 0, 1}); } else { assert (false); } } // n--; } if (m % 2 == 1) { // if (a[0][m - 1] == '1') { // f (0, m - 1, {5, 6, 7}); // } for (int i = 0; i < n; i += 2) { int x = i; int y = i + 1; if (y >= n) continue; if (a[x][m - 1] == '1' && a[y][m - 1] == '1') { f (x, m - 1, {5, 6, 7}); f (y, m - 1, {7, 0, 1}); } else if (a[x][m - 1] == '0' && a[y][m - 1] == '0') { // nothing } else if (a[x][m - 1] == '0') { f (x, m - 1, {5, 6, 7}); } else if (a[y][m - 1] == '0') { f (y, m - 1, {7, 0, 1}); } else { assert (false); } } // m--; } auto get_block = [&] (int i, int j) -> vector { vector aaa; string s1 = string (1, a[i][j]); string s2 = string (1, a[i][j + 1]); string s3 = string (1, a[i + 1][j]); string s4 = string (1, a[i + 1][j + 1]); aaa.push_back (s1 + s2); aaa.push_back (s3 + s4); return aaa; }; function)> F = [&] (int i, int j, vector aa) { vector aaa = {0, 0, 1, 1}; vector bbb = {0, 1, 0, 1}; vector> A; vector> B; for (int I = 0; I < 4; I++) { int x = aaa[I]; int y = bbb[I]; if (aa[x][y] == '1') { A.emplace_back (x + i, y + j); } else { B.emplace_back (x + i, y + j); } } int cnt = (int) A.size(); if (cnt == 0) { return; } else if (cnt == 1) { if (aa[0][0] == '1') { f (i, j + 1, {5, 6, 7}); F (i, j, get_block(i, j)); } else { f (i, j, {3, 4, 5}); F (i, j, get_block(i, j)); } } else if (cnt == 2) { if (aa[0][0] == '1') { f (i, j, {3, 4, 5}); F (i, j, get_block(i, j)); } else if (aa[0][1] == '1') { f (i, j + 1, {5, 6, 7}); F (i, j, get_block(i, j)); } else if (aa[1][0] == '1') { f (i + 1, j, {1, 2, 3}); F (i, j, get_block(i, j)); } else if (aa[1][1] == '1') { f (i + 1, j + 1, {7, 0, 1}); F (i, j, get_block(i, j)); } } else if (cnt == 3) { if (aa[0][0] == '0') { f (i, j, {3, 4, 5}); F (i, j, get_block(i, j)); } else if (aa[0][1] == '0') { f (i, j + 1, {5, 6, 7}); F (i, j, get_block(i, j)); } else if (aa[1][0] == '0') { f (i + 1, j, {1, 2, 3}); F (i, j, get_block(i, j)); } else if (aa[1][1] == '0') { f (i + 1, j + 1, {7, 0, 1}); F (i, j, get_block(i, j)); } } else if (cnt == 4) { f (i, j, {3, 4, 5}); F (i, j, get_block(i, j)); } else { assert (false); } }; vector AA (n); for (int i = 0; i < n; i++) { string S = ""; for (int j = 0; j < m; j++) { S += string (1, a[i][j]); } AA[i] = S; } debug ("after_odd", AA); for (int i = 0; i < (n - n % 2); i += 2) { for (int j = 0; j < (m - m % 2); j += 2) { vector aaa = get_block(i, j); // debug (aaa); F (i, j, aaa); aaa = get_block(i, j); debug (aaa); } } assert (CNT <= N * M); for (int i = 0; i < n; i++) { string S = ""; for (int j = 0; j < m; j++) { S += string (1, a[i][j]); } AA[i] = S; } debug (AA); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { assert (a[i][j] == '0'); } } assert ((int) ans.size() == CNT); cout << CNT << '\n'; for (auto& i: ans) { for (auto& j: i) cout << j << ' '; cout << '\n'; } } return 0; } 
•  » » 9 days ago, # ^ |   +3 Same. I wrote 446 lines of C related code (not counting code template) before giving up and moving to E (which seemed easier to implement). Some part of the cancer code// handling different costs std::vector > costs (5); auto init = [] () -> bool { costs [0].insert("0000"); costs [0].insert("000000"); costs [1].insert("1110"); costs [1].insert("1101"); costs [1].insert("1011"); costs [1].insert("0111"); costs [1].insert("111000"); costs [1].insert("110100"); costs [1].insert("101100"); costs [1].insert("011100"); costs [1].insert("001110"); costs [1].insert("001101"); costs [1].insert("001011"); costs [1].insert("000111"); costs [2].insert("0101"); costs [2].insert("1010"); costs [2].insert("0110"); costs [2].insert("1001"); costs [2].insert("010100"); costs [2].insert("101000"); costs [2].insert("011000"); costs [2].insert("100100"); costs [2].insert("000101"); costs [2].insert("001010"); costs [2].insert("000110"); costs [2].insert("001001"); costs [2].insert("111111"); costs [3].insert("0001"); costs [3].insert("0010"); costs [3].insert("0100"); costs [3].insert("1000"); costs [3].insert("000100"); costs [3].insert("001000"); costs [3].insert("010000"); costs [3].insert("100000"); costs [3].insert("000001"); costs [3].insert("000010"); costs [3].insert("000100"); costs [3].insert("001000"); costs [3].insert("111011"); costs [3].insert("110111"); costs [3].insert("101111"); costs [3].insert("011111"); costs [3].insert("111110"); costs [3].insert("111101"); costs [3].insert("111011"); costs [3].insert("110111"); costs [4].insert("1111"); costs [4].insert("111100"); costs [4].insert("001111"); return true; }; 
•  » » » 9 days ago, # ^ |   0 Lol I had only 80 lines or so
•  » » » » 9 days ago, # ^ |   +7 Spoileryou are lucky
•  » » 9 days ago, # ^ |   0 Well, what I did was first make all the frame equal to zero (the corner, if needed to fix, is tricky), and then solve the rest of the matrix in blocks of 2. I had 4 functions — handle_4_ones calls handle_1_ones calls handle_2_ones calls handle_3_ones.What fucked me over was a bug in my corner case. But now I realize that if the 3 in the corner are all '1's, then we don't do anything, but if it isn't we can just make the whole square 0 in <= 3 moves (and not do if else 8 times and lose because of it :( ).
•  » » 9 days ago, # ^ |   0 I wrote 257 line of code but got wrong answer on pretest 1 just because i used 0 based indexing at the last second, now i feel like crying :(
•  » » 9 days ago, # ^ |   0 My approach:1. First of all I pushed all 1s to the bottom two rows2. Then pushed all 1s to the right bottom 4 cells3. Then handle the last four cells manuallyMy submission https://codeforces.com/contest/1440/submission/98733831
 » 9 days ago, # |   +20 Easiest problem of contest: C (idea)Hardest problem of contest: C (implementation)Can anyone who used segment tree for E suggest how to handle the lazy updates? What information did you store in nodes? The second type of query was easy to handle and implement. The first, not so much.
•  » » 9 days ago, # ^ |   0 As array is nonincreasing updates are assign y on some suffix of [1;x]
•  » » » 9 days ago, # ^ |   0 I stored the min, max, suffix sum at each node. Would that have been enough? I did eventually implement the lazy updates but it was linear and not constant due to bad implementation :(
•  » » » 9 days ago, # ^ |   0 Can you please give some hints fo Query 2 of E?
 » 9 days ago, # | ← Rev. 2 →   +13 for Div2D/Div1B After finding that "a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset" does not exist how to find if clique of size k exist or not? Anyone Please!
 » 9 days ago, # |   +4 What is the Pretest 2 of D2-C2 :(
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 Maybe this one? 1 3 3 000 011 011 My solution failed on this test case initially.
•  » » » 9 days ago, # ^ |   0 No not this. I print the answer for this to be 4. One case as of now I am aware of when both n and m are odd and the grid is full filled where I print the answer as 2 more.For eg : 1 3 3 111 111 111 here I print the answer as 11 moves
•  » » » » 9 days ago, # ^ | ← Rev. 3 →   -30 ...:(
•  » » » » » 9 days ago, # ^ | ← Rev. 2 →   +1 Exact same thing but in Python . I still don't get the meaning of the easier sub-task?
•  » » » » » » 9 days ago, # ^ |   +1 indeed, and i know you from codechef discuss. :D
•  » » 9 days ago, # ^ |   +3 After I've solved this edge case I've managed to pass pretest 2 1 3 2 11 11 01 
•  » » 9 days ago, # ^ |   0 Here's a couple from Pretest2 of Div2-C2 that may be worth trying : 2 2 3 011 000 2 3 111 100 
•  » » » 9 days ago, # ^ |   0 Ok thanks, actually my code runs fine on this (giving 2 and 4 moves respectively), but I found a case inpired from your test that breaks my code. 1 2 3 111 110 Here I print 7 (not possible to constraints)
•  » » » » 9 days ago, # ^ |   0 https://youtu.be/c3FUlV2Fm6g I made this video on C2 for the very first time. I think it might help you.
 » 9 days ago, # |   0 Can someone give a hint for D.2 E?
 » 9 days ago, # |   +36 took me 200 years to implement div2 c ...
 » 9 days ago, # |   +11 I wrote a 250 Line code for Div2C1 and still managed to fail on pretest 2 :sob:
•  » » 9 days ago, # ^ |   0 Mine is exactly 250 lines and to no surprise that it fails at pretest 2 :(
•  » » 9 days ago, # ^ |   0 yea Div2 C1 is pretty f*cked up ngl
•  » » 9 days ago, # ^ |   +2 80% of my code was just push_back();
 » 9 days ago, # |   0 Was div 2 E going to be solved using segment tree?
•  » » 9 days ago, # ^ |   0 Square Root Decomposition I suppose
•  » » » 9 days ago, # ^ |   +10 Nope. Segment tree that simulates binsearch, or treap. Kinda tough to implement.
•  » » 9 days ago, # ^ |   +8 I solved it like that, yes. The hungry man takes from no more than $O(\log n)$ continuous segments and you can find those using the "binary search on segment tree in $O(\log n)$" technique.
•  » » » 9 days ago, # ^ |   0 Nice can you give any refrence to "binary search on segment tree in $O(logn)$" please?
•  » » » » 9 days ago, # ^ |   +6 I only know of this tutorial. Unfortunately it's only for Fenwick tree but the idea is the same — the tree already as a "binary-search-like" structure so you can descend in the tree instead of of making separate queries for each binary search step.
•  » » » » » 9 days ago, # ^ |   0 You are life saver!
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   0 for this problem I think you can do usual binary search (like middle=(x+n)/2) and the find range sum in [x,m] then accordingly change the range. but time complexity will be $O(n(logn)^2)$ but time limit is 3 sec so should be sufficient..
•  » » » » » 9 days ago, # ^ |   0 You can't, because every query in the problem requires $O(\log n)$ such binary searches.
•  » » » » » » 9 days ago, # ^ |   0 Please can you answer this any reference or just idea? means how should I approach.
•  » » » » 9 days ago, # ^ |   0 "Seg Descend" might be helpful, though I haven't solved the problem yet so i don't know for sure. You can find it in this page https://cp-algorithms.com/data_structures/segment_tree.html under the heading "Searching for the first element greater than a given amount".
•  » » » 9 days ago, # ^ |   0 Can you please elaborate more on the part "The hungry man takes from no more than $O(logn)$ continuous segments".
•  » » » » 9 days ago, # ^ |   +3 When he has bought food in some segment and can't buy food at the next one, the amount of money he has must have been at least halved since the start of the segment (because the array is nonincreasing and the updates maintain that).Oh,I guess it's actually $\log C$, but it's not very important.
 » 9 days ago, # |   +197
 » 9 days ago, # |   +19 My fingers are hurting after writing code for div2 C.
 » 9 days ago, # |   +17 Am I the only one who felt that problem C1 (Div-2) was totally hardcore implementation problem?
•  » » 9 days ago, # ^ |   0 I don't think C1 was. But, definitely C2 imo
•  » » 9 days ago, # ^ |   0 I don't think so. https://codeforces.com/contest/1440/submission/98728859
•  » » » 9 days ago, # ^ |   +16 Maybe you can take a loot at jiangly's submission and see that it is not that long, but still dumb implement problem.
•  » » » » 9 days ago, # ^ |   0 yeah it 's for sure that it is not that long if we see jiangly submission , jiangly writes beautiful implementation for each and every problems . But newbies like me writes terrible code see around 388 lines — spaces . Submission link : https://codeforces.com/contest/1440/submission/98743493 It is really nice to see someone mentions the highness of jiangly which in my mind is one of the best coder in the world right now . Sorry jiangly for mentioning your name and an annoying notification of mine :)
•  » » » » » 9 days ago, # ^ |   +10 Yep jiamgly made me learn. Everything I finishing upsolving I always look at jiangly's submission.
•  » » » » » 9 days ago, # ^ | ← Rev. 2 →   +19 Yes, indeed!Does there really exist anyone who don't love jiangly-chan?jiangly-chan, we love you! <3 <3 <3 <3Just join "jiangly fan-club"! ;P btw you can check my submission also
•  » » » » » » 9 days ago, # ^ |   +10 How to join that club ? I don't know that they will gonna take a pupil like me in their club but anyway i have learnt a lot from jiangly coding . The way of writing inner lambda functions in main and lots of simple coding style too . Only thing i don't do is writing std:: again and again . I respect and love jiangly way of writing code a lot (infinite times repeat) . I wish that one day jiangly be the best coder in the world . Sorry if anyone finds my words and complements annoying in advance .
•  » » » » » » » 9 days ago, # ^ | ← Rev. 2 →   0 It seems that the club is not in the "Organizations" of Codeforces.But you can create a brand new organization named "jiangly fan-club" for sure! (just like Ildar Gainullin fun-club, btw Ildar Gainullin is 300iq)I'm sure lots of coders who learnt from jiangly's code will be glad to join!
•  » » » » » » 9 days ago, # ^ |   0 Its too short!
•  » » » » » 9 days ago, # ^ |   +5 Ever since I found jiangly, I never looked others' code :) (no offense to other people who write beautiful code)
 » 9 days ago, # |   +2 I am an idiot. I debugged C2 like crazy, submitted in the last 20 seconds, and forgot to submit C1 :(Btw, great problem — NO IF ELSE IN C2, NO CASES, REALLY EASY IMPLEMENTATION.obviously now when I look at it I could have saved a lot of the code, but still...
•  » » 9 days ago, # ^ |   0 I did a similar approach in my implementation. I still don't know why I got RTE on pretest 2. I spent the last 10 minutes trying to figure that out.
 » 9 days ago, # |   0 Hey, isn't finding a clique of size k NP-complete? I lost my mind after reading D cuz of that and not to mention I left C behind long long ago XD
•  » » 9 days ago, # ^ |   0 I think you can have a clique if and only if you can solve the second task of the problem with k-1. And I think you can do the transition somehow..
•  » » » 9 days ago, # ^ |   0 Then someone please explain why the problemsetter hasn't been given a million dollars to have shown a poly time solution to an NP complete problem.
•  » » 9 days ago, # ^ |   0 There is bron-kerbosch algo, but I think complexity does not allow it to run on 1e5 vertex.
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 the trick was realizing that for having a clique of size k, you need at least k * (k — 1) vertices
•  » » » » 9 days ago, # ^ |   0 ok yes. but how to implement that?
 » 9 days ago, # |   +16 I think extremely easy idea but extremely heavy implementation problems should be reduced (as least just give m,n even).
 » 9 days ago, # |   +21 B and C were so uninteresting. You could easily see the idea (or at least the pattern) in both of them but it all came down to who could implement them faster.
•  » » 9 days ago, # ^ |   +3 I mean... you're right about C but B was pretty easy to implement... You just sum up elements in a single (kind of-)simple for loop.
•  » » » 9 days ago, # ^ |   +8 I don't think it was very easy to see that, took me 10 minutes to observe it and then another 20 minutes to debug my code. Also, I think C was very implementation heavy, some typos and you will have to spend another 30 minutes figuring it out. PS: my personal opinion.
•  » » » » 9 days ago, # ^ |   -11 Don't worry bro, you'll still get Google in your campus placements.
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   0 I never said B was easy... I was it was pretty easy to implement. I mean, the shortest and most simple implementation for C was at least 50 lines of code (or probably closer to 100).This is my implementation of B: B-solutionvoid solve(int /*test_case_num*/) { ll n,k; read(n,k); vll a(n*k); read(a); ll bottom = (n-1)/2; ll rest = n-bottom; ll total = 0; for(ll i = bottom*k; i
•  » » 9 days ago, # ^ |   +9 I think C was really braindead. In B I needed like 20 minutes to switch n and k. I think this is the first problem where the number of the partial thing is named n, not the number of the whole thing. Same goes with k, it is usually used for a property of a part. Misleading nameing.
 » 9 days ago, # |   +22 Why did div1A have subtasks? In one operation, we always cut off one cell from the bottom/right border until we get 2x2 and there are just 4 distinct operations there. I don't see a simpler solution for the first subtask.
•  » » 9 days ago, # ^ |   +35 Fix each cell individually in 3 steps.
•  » » » 9 days ago, # ^ |   +10 Wasn't the same logic used in the hard subtask also? Each cell can be fixed in 1 step and we are left with just 2 corner cells which require atmost 3 steps.
•  » » » 9 days ago, # ^ |   -17 Fix each cell individually in 1 step.
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 Still the number of submission in div2 for the same problem were 2500(easy)-700(hard). People must have found some logic for 3*n*m
•  » » 9 days ago, # ^ |   +11 For subtask one you can change one cell of each 2 * 2 in 3 operasion such that other cells do not change
•  » » 9 days ago, # ^ |   0 except last row, all cells in 1 operation. total=(n*m-m). for last row, we can chang each cell in atmost 3 operations. total=(n*m-m)+m*3 = n*m+2*m. this can work for both subtasks?? is the total correct?
•  » » » 9 days ago, # ^ |   0 Use the idea for "all but the last row" with columns too. Then you're left with a 2x2 grid.
 » 9 days ago, # | ← Rev. 2 →   0 How to solve Div2.D / Div1,B ?, ty.
 » 9 days ago, # |   -17 ....?? Why NP-Complete problem comes here?
•  » » 9 days ago, # ^ |   +15 From the problem statement it kinda follows that it's not NP-complete if you can instead answer the other question.
•  » » » 9 days ago, # ^ | ← Rev. 2 →   +3 Can you please tell me just the idea. After finding that "a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset" does not exist how to find if clique of size k exist or not?
 » 9 days ago, # |   +118 I'm not gonna forgive you 3 seconds TL in E :<
 » 9 days ago, # |   +10 Make sure you have amazing typing speed with precision before solving Div2. C
 » 9 days ago, # |   +629 Do you hate your participants or what? What the hell is wrong with these limitations? Why in every problem I have to optimize everything? Ideas are maybe fine, but you have killed this round with your limitations.
•  » » 9 days ago, # ^ |   +176 Looking at the standings atm I don't know if I should be afraid of you or of an author...
•  » » 9 days ago, # ^ |   +441 Do you also have to guess the hashset implementation which passes the tests? Fuck you guys, for real.
•  » » » 9 days ago, # ^ |   +139 +1
•  » » » 9 days ago, # ^ |   +97 As a mere blue coder, I know something is wrong when I see Um_nik TLE 2nd problem in div1.
•  » » » 9 days ago, # ^ |   +67 And I thought I was pissed off when carefully implementing clique checking optimised for this problem, lol.
•  » » » 9 days ago, # ^ |   +82 +1
•  » » » 8 days ago, # ^ |   0 The fact that you could not pass test 57 test is not a reason to say every word that you want, I did not answer yesterday because you were angry, but really a pity for those who are LGM and for example can be a good role model for others, do not value himself.
•  » » » » 8 days ago, # ^ |   -75 Fuck you. Today I'm not angry, will you answer?
•  » » » » » 8 days ago, # ^ |   0 Why did I really waste my time writing the previous comment? Keep polite and thank you for proving to me that I was not wrong about you :) ;)
•  » » » » » 8 days ago, # ^ | ← Rev. 4 →   -10 You are clearly an extremely talented programmer um_nik, but that does not give you the right to treat people like this. Your language and rudeness is completely unnecessary.Edit: downvote me all you want — if the guy goes around telling people to f**k themselves because he TLEd on a question, that’s rude, disrespectful of the writers who gave up their time, and just plain unnecessary. No amount of rating points makes that ok behaviour.
•  » » 9 days ago, # ^ |   +165 I support you. Especially for Div1B, I think 1 sec for this problem is terrible even with $O(n \sqrt{n})$ without hashsets or something. I always consider quitting Cf with writers who give us problems with such TL/MLs...
•  » » » 9 days ago, # ^ |   +48 I think my recent submission 98748728 is $O(m sqrt(m))$ without hashset and got TL :(
•  » » » » 9 days ago, # ^ |   +43 It's not. Tests 56 and 57 are against solutions like yours with wrong complexity. Tests 25, 58 and others are made against $O(m\sqrt{m})$ solutions with too high constant and/or log factor.
•  » » » » » 9 days ago, # ^ |   +38 Ah, my submission is wrong with small K (maybe N^2/K). Sorry for confusing
•  » » » » » 9 days ago, # ^ |   +68 By the latter sentence, you mean pretests did not have maximum tests? With such tight TL?
•  » » » » » » 9 days ago, # ^ |   -20 There are tests that look like maximum tests, but the ratio between runtimes of any 2 tests can, due to implementation details, be different for 2 solutions with the same complexity. Pretests probably have tests that caused higher runtimes on most authors' solutions, while on some other solutions tests like 25, 29 and 58 can cause higher runtimes. Or maybe I'm wrong and tests 25 and 29 did cause higher runtimes than tests 6, 7, 9 and 12 on authors' solutions but for some different reason they decided to not put them in pretests.
•  » » » » » 9 days ago, # ^ |   +23 I think that you are just bullshitting me. I used different hashset and got AC now. I was having TL 57. Did different hashset magically fix my complexity?
•  » » » » » » 9 days ago, # ^ |   +56 For some reason test 57 caused an $O(n^2)$ blow up on your hash table. Changing your hash function from (v * A + u + B) % P; to (v * A + u * B) % P; gave AC: 98754739
•  » » » » » » » 9 days ago, # ^ |   +10 For fixed v, if u are near each other hashes are also near each other.