Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, history, 2 months ago, translation, ,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Special thanks to Mikhail darnley Dvorkin for helping in round preparation!

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

You really went for it in the last Educational Round! We had an all-time high participation of 21750 people :) We are happy to support such an awesome community, and look forward to growing these numbers in the future!

We are searching for diamonds in the rough — driven, talented humans, passionate about technology and design, undefined by nationality, gender and cultural background. We know that no diamond is born polished, so our mission is to identify and support as many talented young individuals as we can, so that they can fulfill their potential and secure the future they deserve.

If you are graduating or have already completed a bachelor's degree, we are waiting for your applications for fully-funded Master's degree scholarships by the link below.

APPLY NOW→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 DreamLolita 6 211
2 KrK 6 235
3 Heltion 6 259
4 krijgertje 6 268
5 Temotoloraia 6 272

Congratulations to the best hackers:

Rank Competitor Hack Count
1 liouzhou_101 81:-35
2 j_peters 29:-16
3 eR6 18:-19
4 tonyli00000 14:-15
5 lollihunter 8:-7
281 successful hacks and 925 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Sevlll 0:00
B This0is0the0AmShZ 0:02
C DreamLolita 0:03
D xb0nS 0:14
F chemthan 1:07

UPD: Editorial is out

• +336

 » 2 months ago, # |   +3 Kudos. " You really went for it in the last Educational Round! We had an all-time high participation of 21750 people "
 » 2 months ago, # |   0 Lets cross 25000 this time!
•  » » 2 months ago, # ^ |   +28 Oh no. Think about CF servers.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 On last div3 server works fine with 28k registration. So 25k is going to be regular participation.
•  » » » » 2 months ago, # ^ |   +1 I hope so.
•  » » » » 2 months ago, # ^ |   -7 But this is ‘rated for div.2’ so there will be less participants. Educational Codeforces Round 85 (Rated for Div. 2) has only 21750 people.
•  » » » » 2 months ago, # ^ |   0 Div 3 isn't rated for many people. The no. of people who actually stay throughout the contest is very less. That might be the reason why 28k wasn't a problem.
•  » » » » » 2 months ago, # ^ |   +2 Div3 has more official participants than educational round. On last div3 round rating changes for 16k people where rating changes for 11k people on last educational round.
 » 2 months ago, # |   +17 Can someone please explain what's a difference between codeforces educational and normal rounds? Thank you.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +125 You can find following difference Normal codeforces round has a variable points for each problem(500,750,1000 and so on). Each problem has equal points on educational rounds. In normal coforces rounds you can hack during the contest, in educational round there is 12 hours hacking phase after contest is finished. Normal codeforces round has 20 penalty for wrong submission where educational round has 10 minutes penalty. During contest successful submission gives verdict pretest passed where educational rounds gives accepted. Normal codeforces round judges your last pretest passed solution for each problems and skip other solution for that problem. In educational rounds all your solution will be judged and 1st one will be counted which passes the system test. In normal round final standing is given based on points earn from all solved problem. In educational round standing is given based on no of solved problem. If no of solved problem is equal then time penalty is used to break a tie. NB: Div3 rounds follow the rules of educational rounds.
•  » » » 2 months ago, # ^ |   0 Thank you, sounds like these rounds are not too harsh and beginner friendly. One other thing, How do you hack during a contest or after its over? After some research I found out it gives you points after successful hacks. What I don't found out how you do it?
•  » » » » 2 months ago, # ^ |   +33 In normal codeforces round you have to lock you problem first. When you lock your problem you can't resubmit that problem during contest time. After you lock your problem go to room tab and here you can see solutions of other participants who are in that room. You can hack or see solutions for those problem which you have locked.Successful hacking gives +100 and unsuccessful attempts give -50.In educational and div3 rounds you can see any solution you want. Then you can hack one from status page if you think that solution is not fine enough. This hack has no points.
•  » » » » » 2 months ago, # ^ |   0 Thank you very much for explaining!!
•  » » » 2 months ago, # ^ |   0 Are there points for hacks in educational rounds?
•  » » » » 2 months ago, # ^ |   +3 No
•  » » » 2 months ago, # ^ |   +2 In normal round you got -50 penalty if you passed the problem from pretests
•  » » » 2 months ago, # ^ |   +9 As far as I remember educational rounds also have system tests after them, after hacking phase. So #4 is only about name of verdict, isn't it?
•  » » » » 2 months ago, # ^ |   +8 Yes it is only name of verdict.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Really? Or the main system tests are just the added hacked test-cases?
•  » » » » » » 2 months ago, # ^ |   0 As far i know this also happen in codeforces rounds too.
•  » » » » » » » 2 months ago, # ^ |   0 Are all the successful hacks included in the system tests?
•  » » » 2 months ago, # ^ |   +8 Why does the educational round give accepted instead of pretest passed?
•  » » » 2 months ago, # ^ |   0 Normal codeforces round has 50 penalty for wrong submission afaik.
•  » » » 2 months ago, # ^ |   0 In normal codeforces round,1st solution passed pretests time — 3 minutes into the contest — score 496/500same problem2nd solution — passed pretests — time — 10 minutes into the contest — score ?
•  » » » 2 months ago, # ^ |   0 I have a doubt. If the round is rated for only people less than 2100 rating, why is the rank calculated considering all ratings. And also, is there the case with rating change as well ??Just a doubt ...
•  » » » » 2 months ago, # ^ |   0 Contestants with rating >=2100 are one final standing but rating doesn't change for them. Rating only change for them who have rating less than 2100.
•  » » » » » 2 months ago, # ^ |   0 yes, but if they are in the ranklist that means the ones who are below them will suffer rating loss and high ranks..is it the way educational round rating system works ?Its a doubt !!
•  » » » » » » 2 months ago, # ^ |   0 They will be not considered while calculating rating. Only rank of official participants will be considered.
•  » » » 7 weeks ago, # ^ |   0 thank..so many doubt are now clear..one last question ...is there time for hacking phase after the normal contest like div 1,2??
•  » » » » 7 weeks ago, # ^ |   0 i think yes
•  » » » » » 7 weeks ago, # ^ |   0 ok..thanks
•  » » » » 7 weeks ago, # ^ |   0 No. there is no hacking phase in div1,2 rounds. But you can hack during contest.
•  » » » » » 7 weeks ago, # ^ |   0 great to know..thanks
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 You can read about educational rounds here
 » 2 months ago, # |   0 Good Luck everyone
•  » » 2 months ago, # ^ |   -100 Good luck.Your photo is so cute.
•  » » » 2 months ago, # ^ |   +38 SIMP!
•  » » » » 2 months ago, # ^ |   0 thank you
•  » » » 2 months ago, # ^ |   +4 I guess it's a fake profile photo. The photo is of an actress..
•  » » » » 2 months ago, # ^ |   0 Which actress? I want to explore.
•  » » » » » 2 months ago, # ^ |   0 serial_killer Here u go
•  » » » » » » 2 months ago, # ^ |   0 Cool. I wish you high ratings.
•  » » » » » » 2 months ago, # ^ |   0 My picture & Pori Moni's face are not same.
•  » » » » » » » 2 months ago, # ^ |   0 I don't think so. Can you prove yourself? Change your profile picture.
•  » » 2 months ago, # ^ |   +4 No wonder why my contest didn't go well.
 » 2 months ago, # |   +187
•  » » 2 months ago, # ^ |   -22 But we should hope for short and simple problem statements. What else we needStronger pretests:)
•  » » » 2 months ago, # ^ |   +4 we do but let's hope that in our hearts I don't think writing hope comments will actually affect the problem statements or how strong pretests are ... just an opinion maybe someone else has a different point of view
•  » » » » 2 months ago, # ^ |   +1 Lets add a new word to our dictionarySARCASM
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +14 and one more "Simultaneously" -_-
•  » » 2 months ago, # ^ |   +213
 » 2 months ago, # |   +341
•  » » 2 months ago, # ^ |   +29 I had a +242 in the previous edu round :)
•  » » » 2 months ago, # ^ |   +4 Congrats buddy
•  » » » 2 months ago, # ^ |   0 I had +88 in previous ^^ I cant imagine how myself was when I solved C accepetedly ^^
•  » » 2 months ago, # ^ |   0 So much rating!? (^w^)
 » 2 months ago, # |   -17 just a legendary noobmaster passing by...
 » 2 months ago, # |   +3 Pretests have been extremely shit recently. Like seriously does it hurt to make good pretests and spare us from misery?
•  » » 2 months ago, # ^ |   0 Your photo...orz
 » 2 months ago, # |   -16 Why the educational round harder than normal div 2 round is it a lie or not
•  » » 2 months ago, # ^ | ← Rev. 10 →   +131 _ (Reference — Evro)_
•  » » » 2 months ago, # ^ |   +90 Damn ,Stealing memes even in codeforces..
•  » » » » 2 months ago, # ^ |   +16 My intention was not to steal your content(Evro), I simply found it funny and quite relevant to Codeforces while surfing google. So, I simply posted it to make people relate and smile a little. Now, That I know you made it, I tagged you.Peace
•  » » » » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +37
 » 2 months ago, # | ← Rev. 3 →   +18 Educational rounds have never let me down.I hope everyone can enjoy this.Good luck and high rating!See you in the top list!
•  » » 2 months ago, # ^ |   +26 You had to edit your comment thrice to say this?
•  » » » 2 months ago, # ^ |   -20 thrice !! English Language experts prefer to say 'once' and 'twice' instead of 'one time' and 'two times;' but the –ice suffix ends there, –'three times' is standard expression in today's world and not 'thrice. ... To answer the question (title) of this post, 'Yes, 'thrice' is a correct English word; and yes, it is dated! i copy this from google :)
•  » » » » 2 months ago, # ^ |   +6 not sure what you mean by "english language experts", but I definitely remember hearing thrice being used so it can't be that archaic
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   -11 Bro i just search thrice on the google becuase ive never hear that before
•  » » » » » » 2 months ago, # ^ |   +33 Well, you must not be an expert then :p
•  » » » » » » » 2 months ago, # ^ |   0 :/
•  » » » » » » 2 months ago, # ^ |   0 You searched "thrice" thrice?
 » 2 months ago, # | ← Rev. 2 →   -67 [removed]
•  » » 2 months ago, # ^ |   +96 Did you mean: "Codechef"?
•  » » 2 months ago, # ^ |   0 Codeforces is one of the best!
•  » » » 2 months ago, # ^ |   +21 It is the "BEST".
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +18 I completely agree but your username :p
•  » » » » 2 months ago, # ^ |   0 Yeah!
•  » » » 2 months ago, # ^ |   0 I completely agree!
•  » » » 2 months ago, # ^ |   0 Yeah, Codeforces has many good problems and a strong community!
 » 2 months ago, # |   +80 What people think simultaneously means??
 » 2 months ago, # |   +29 I'm sorry but this round is one of some rounds that mostly made me be confused by its statements :|
 » 2 months ago, # |   +105 simultaneously really ? :( @pikmike MikeMirzayanov
•  » » 2 months ago, # ^ |   +8 Till the last 10 minutes, I thought both of them have to end up at 0 together in a single step and then I see in the contest announcement that x=1 and y=0 become x=0 and y=0." simultaneously" didn't let me solve any further questions.
•  » » » 2 months ago, # ^ |   0 Even after seeing the announcement, I thought it could have gone from 1, 0 -> 1, 1 -> 0, 0 since x & y have to reach 0 simultaneously!!
•  » » 2 months ago, # ^ |   +5 I feel for you, this took my 40 mins ... RIP Rating
•  » » » 2 months ago, # ^ |   +6 Same here :( I didn't feel like solving any more questions after I wasted time on 'simultaneuosly'
•  » » 2 months ago, # ^ |   +5 This round should be unrated IMO because of the ambiguity of questions
•  » » 2 months ago, # ^ |   0 And 01 has period of 2 :| Omg :(
 » 2 months ago, # |   +13 that C killed me
 » 2 months ago, # |   +25 I'm really confused that when I choose not to see unoffical participants I see load of yellow and red names in the first 100.How are the D2 participants' rank calculated?Does Codeforces calculate our ranks removing them?
•  » » 2 months ago, # ^ |   +1 Yes, they appear on the official scoreboard but don't count when calculating the rating distribution.
 » 2 months ago, # |   +7 Sorry to say,but problem statement of A was not clear enough,which caused unnecessary penalty for many contestants.Also there were too many Announcement during the first hour.Hope,next time problem statement will be clear enough! :(
 » 2 months ago, # | ← Rev. 3 →   +48 contest is still running(only 6 mins remaining) and i haven't been able to solve a goddamn single problem. wanna die.
•  » » 2 months ago, # ^ |   +13 that simutaneously word though!! I am irritated!
•  » » 2 months ago, # ^ |   +14 just realised my mistake, in first question i thought in second operation we're doing x+1,y-1 or x-1,y+1. I SHOULD HAVE READ THE PROBLEM CAREFULLY.
•  » » » 2 months ago, # ^ |   +2 Same for me, I noticed after like 30 minutes.
 » 2 months ago, # | ← Rev. 2 →   +6 [removed]
•  » » 2 months ago, # ^ |   0 Bait or Naive?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +166 like this
•  » » » 2 months ago, # ^ |   0 more interesting
•  » » 2 months ago, # ^ |   0 And being a newbie , you solved first five problems of the contest , don't try to fool everyone , you are definitely Orange/Red on your real id .
•  » » 2 months ago, # ^ |   0 XD!!
 » 2 months ago, # |   +42 Your goal is to make both given integers equal zero simultaneously : this statement cost me 5 WA + 63 min to submit
•  » » 2 months ago, # ^ |   +27 Yeah , the term "simultaneously" is diverging from the actual question.
•  » » » 2 months ago, # ^ |   0 Besides, according to Einstein, simultaneity is relative.
 » 2 months ago, # |   0 What is test 3 of C?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +1 I can guess its something like this click
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I guess those were like this: 1 17 110 2 100 200 50 300 
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 Try this t=1 a=7 b=10 q=1 l=85 r=150
 » 2 months ago, # |   +43 Am I the only one who dislikes problems like D where you need to print one of the solutions rather than just saying what the minimum value of best solution would be? Seems annoying to code.
•  » » 2 months ago, # ^ |   +9 I don't think it requires much additional coding: Just put the elements in a cyclic order into the output arrays:https://codeforces.com/contest/1342/submission/78163277
•  » » » 2 months ago, # ^ |   +9 It doesn't require much coding, but it feels like it was put there just to trip up contestants who didn't read carefully. (I'm also biased because I got tripped up as well)
•  » » » 2 months ago, # ^ |   0 Can we print the cyclic order starting from the smallest element? Thank you
•  » » » » 2 months ago, # ^ |   0 yes
•  » » 2 months ago, # ^ |   0 Sometimes I like that style; often (like today) it's a big hint to contestants that the solution to the problem is greedy and not dp.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +46 I don't see how it's a "big hint" that it's greedy. Many dp solutions can be reconstructed and printed out in a batch like this too, like Thursday's Div1B/Div2D.
 » 2 months ago, # |   +5 Problem C — test case 3. Can I have some example?
•  » » 2 months ago, # ^ |   0 I guess those were like this: 1 17 110 2 100 200 50 300 
 » 2 months ago, # |   +58 In problem A, the word 'simultaneously' has been used in a very wrong way. Because of this, I thought if we have states (0,1) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and complete waste of 1 hr.How about using 'both' instead of 'simultaneously'?
•  » » 2 months ago, # ^ | ← Rev. 2 →   -46 We used this word to cover the fact that you cannot make, for example, $x = 0$, then make $x \ne 0$, and then make $y = 0$ without making $x = 0$. And the notes for the first example showed that $(0, 1)$ to $(0, 0)$ is possible.I don't think that there is a perfect wording for such problems (''both'' implies some questions like ''can we make $x = 0$, then make it non-zero, and then make $y = 0$''). Perhaps a lot of inline-examples would help, but make the statement much more cumbersome.
•  » » » 2 months ago, # ^ |   -118 Contest should be unrated as problem statement was really confusing
•  » » » » 2 months ago, # ^ |   -11 I too got 2 wrong submissions and it caused confusion to a lot of people, but simply because of that you cannot make whole round unrated!
•  » » » » 2 months ago, # ^ |   +21 I don't think so , i was able to understand problem statement very easily ,Although ,i am not a native english speaker.
•  » » » » » 2 months ago, # ^ |   0 I politely disagree with you. If you will see some other questions here, simultaneously implies that both reach together. The distinction is that of "simultaneously reaching zero" and "simultaneously being zero" I think, and in this question they meant "simultaneously being zero".Though in contest one can always ask question and clarify, I did that. But rating suffers if one is not able to solve other questions.
•  » » » » 2 months ago, # ^ |   0 Did you mean to write "because my rating nosedived"?
•  » » » 2 months ago, # ^ |   +26 Your example added more confusion.
•  » » » » 2 months ago, # ^ |   +3 exactly! instead of saying that the word simultaneously is not to be considered!The explanation was more confusing!
•  » » » 2 months ago, # ^ |   0 How though would it make a difference if you didnt cover up that fact?The word "simultaneously" used in this context literally (in all sense) means that going from state 0,1/1,0 to state 0,0 is not correct
•  » » » » 2 months ago, # ^ |   -16 Why does it mean so? If we go from $(0, 1)$ to $(0, 0)$ then both numbers are $0$ simultaneosly.
•  » » » » » 2 months ago, # ^ |   +16 Because "simultaneously" means "at the same time" or "at the same instant" (try googling it)and making x and y to 0 simultaneously means making them 0 at the same time/instant
•  » » » » » 2 months ago, # ^ |   +5 This is from the problem statement "Your goal is to make both given integers equal zero simultaneously". Here, you didn't make both given integers equal zero simultaneously because one has been already zero the other non-zero.
•  » » » » » » 2 months ago, # ^ |   +17 The last operation makes them both $0$ at the same time, so the condition is met.Okay, there might be more than one way to understand it, but the example notes and the clarification system are working for exactly this reason — if you think that you don't understand something, ask a clarification.
•  » » » » » » » 2 months ago, # ^ |   +6 Well, I thought I understood the problem as the way I explained, and sadly that interpretation of the problem statement works on the sample cases.
•  » » » » » » » » 2 months ago, # ^ |   +7 But it does not work on notes (which are part of the statement).
•  » » » » » » » » » 2 months ago, # ^ |   0 I don't think an explanation to a test case justifies an incorrect statement. Everybody is more likely to read the statement and the testcases rather than the explanation to the testcases, especially for problem A
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 It wasn't one of they way one could understand it. It was the right way to understand. Yes, one could have got the intended meaning by looking at the notes, so to demand that contest be unrated is not sensible at all.But please refrain from using words you don't know the exact meaning of.
•  » » » » » » 2 months ago, # ^ |   -23 No, problem statement is correct. They are zero at the same time instant (simultaneously) at the end of the operations. That's it. The fact that one of them was zero beforehand does not matter.
•  » » » » » » » 2 months ago, # ^ |   +9 in a way that is simultaneous (= happening or being done at exactly the same time):this is from the dictionary, which clearly states being done at the same time. x and y would be 0 after the operation does not mean x and y became 0 simultaneously.
•  » » » » » » » » 2 months ago, # ^ |   -16 I am not disagreeing that it could have been worded better to avoid any confusion at all. But the author's usage of simultaneously is not wrong. Regardless, the round should remain rated.
•  » » » » » » » » » 2 months ago, # ^ |   +14 The author's usage of simultaneously is incorrectThe statement specifically mentions"Your goal is to make both given integers equal zero simultaneously"If it did not have the word "make" I would have accepted the problemsetter's interpretation of things, but adding the word "make" in the same sentence suggests that both x and y have to BE MADE equal to 0 at the same time and not that they have to both BE 0 at some time.
•  » » » » » » » » » 2 months ago, # ^ |   0 Regardless, the round should remain ratedI never said anything about the round being rated or unrated. Just wanted the authors to know that statement was misleading for some people which could have been avoided.
•  » » » » » » » » 2 months ago, # ^ |   0 You're trying to make them both be 0 simultaneously, not change them to 0 simultaneously, and the problem statement obviously said the former way.
•  » » » » » » » » » 2 months ago, # ^ |   0 Exactly, making them zero at exactly the same time , that's what simulataneously means. And honestly if you are differentiating between make and change then by doing so even you are agreeing that it was ambigous.
•  » » » » » » » » » 2 months ago, # ^ |   0 the statement said "make both", not "make both be"make both suggests changing them to 0 simultaneously
•  » » » » » » » » » 2 months ago, # ^ |   0 If you change one to 0 after the other, you're still making both given integers equal zero at the same time, not implying you have to change them at the same time. I don't get the confusion.
•  » » » » » » » » » 2 months ago, # ^ |   +1 The debates reached maximal permitted depth Let us stop, we both are viewing it from different angles and thus it seems different to both of us.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Your goal is to make both given integers equal zero simultaneously, i.e. $x=y=0$"Make ... simultaneously" might be taken to mean that both numbers become equal to 0 at the same instant, not just that they are both 0 at some moment in time. Given the clarification $x=y=0$, the word "simultaneously" could have been safely omitted.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   +11 yes both numbers are zero simultaneously, but the statement says "your goal is to make both numbers equal to zero simultaneously". This is a dangling modifier as it is unclear whether "simultaneously" refers to the numbers being equal to zero, or to making the numbers equal to zero.I think removing the "simultaneously" actually makes the statement clearer. If you want to emphasize that both numbers need to be zero at the end, I would prefer phrasing it as "your goal is to make both numbers zero after all the operations"(just sharing what I think people are complaining about, I understood the statement in one try because of the example)
•  » » » 2 months ago, # ^ |   +10 You could perhaps say, at the end of all operations, $x$ and $y$ must both be $0$. The current statement wasn't optimal (the announcement could have been part of the problem statement), but I agree that the question itself wasn't ambiguous.
 » 2 months ago, # |   0 test 2 for problem A is just making me nuts..
•  » » 2 months ago, # ^ |   0 me too. T_T
•  » » 2 months ago, # ^ |   +3 I guess you missed "long long". The answer is overflowing integer limits.
•  » » » 2 months ago, # ^ |   0 Not really. Used JavaScript for fun, turned out to be not so fun :D And most annoying thing — the solution was correct.. Congrats to me — I've played myself.
•  » » 2 months ago, # ^ |   0 me too :c
 » 2 months ago, # | ← Rev. 3 →   +16 I reduced the problem E to the following:Distribute n distinct objects into n-k distinct bags such that each bag gets at least one object. This is solvable through Inclusion-Exclusion but how to do it efficiently? Is there any other way to solve the problem?
•  » » 2 months ago, # ^ |   +8 yes, i also reduced to exact same, but cant move ahead after that.
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 .
•  » » 2 months ago, # ^ |   0 Another solution described here
•  » » 2 months ago, # ^ |   +57 The number of ways to put $n$ objects into $n-k$ bags is $(n-k)^n$. This also counts all the configurations with one empty bag, so we should subtract $(n-k-1)^n\cdot\binom{n-k}{1}$ (number of ways to choose the 1 empty bag, and put $n$ objects into $n-k-1$ bags). Now, this subtracts off too many configurations with two empty bags, so we should add $(n-k-2)^n\cdot\binom{n-k}{2}$. Continuing this gives the answer as $\sum_{j=0}^{n-k} (-1)^{j} \cdot (n-k-j)^n \cdot \binom{n-k}{j} .$
•  » » » 2 months ago, # ^ |   +8 Thanks emma, I just saw your submission. Damn it! It didn't occur to me to use binary exponentiation to solve it. I just gave up after reaching the expression :(
•  » » 2 months ago, # ^ |   +29 After you've decided a distribution with positive integers $a_1,...,a_{n-k}$ and $\sum a_i = n$, you can arrange them in $\frac{n!}{\prod a_i!}$ ways. So the answer is coefficient of $x^n$ in $\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^{n-k}=\left(e^x - 1\right)^{n-k}$. Now you can expand it with binomial theorem and extract answer in $\mathcal O(n)$.
•  » » 2 months ago, # ^ |   0 Can you tell how you reduced the problem to this?
•  » » » 2 months ago, # ^ |   +9 To attack every empty cells, either every row or every column contains a rook (both only if $k = 0$). Now notice that , if, say, you have decided to fill every column, you will have to group pairs of attacking rooks within the different rows. A row will consist of possibly $0$, or more rooks. $n$ rooks means $n-1$ pairs, for $n \geq 1$. Now we are almost there for the reduction. There will always be $n-k$ groups of row (or "used" row if you prefer). If less, it can be shown that there are too much pairs. If more, there are not enough. The $n-k$ rows are the "bags". The position of the rooks in the columns is important. That is why you have the forumla $(n-k)^n$ at the beggining. At the end you also need to multiply by two if $k=0$ (because of what I said at the beggining) and... you have to take into account that you also have to ditribute the "bags" ($n-k$ of them) to the different rows ($n$ of them). This is yet another binomial coefficient. I hope this was somewhat helpful, the editorial should be better at explaining the solution anyway :)
•  » » » » 2 months ago, # ^ |   0 Thanks a lot for the great explanation
•  » » » » 2 months ago, # ^ |   0 I would like to add an explanation for "why exactly n-k groups of row?" Let q denote the number of chosen rows. Assume our chosen rows are r(1), r(2) ... r(q). Let Cr(i) denote the number of rooks in each row. As the number of attacking rooks for each row is Cr(i)-1 , so we have this equation: Cr(1)-1+Cr(2)-1+ .. +Cr(q)-1 = kFrom this we can get Cr(1)+Cr(2)+...+Cr(q) = k+qSo q = Cr(1)+Cr(2)+...+Cr(q)-k = n-k
 » 2 months ago, # |   +52 for future reference
 » 2 months ago, # |   +5 Video tutorials here for some of the tasks, you can also join my discord server for more insightsCD
 » 2 months ago, # |   0 https://codeforces.com/contest/1342/submission/78208967 what's wrong in this solution for C
 » 2 months ago, # | ← Rev. 4 →   -23 Wierd Runtime, please help! I am getting Runtime Error on submitting div2D on Codeforces on 1st sample, but same code & input runs & produces perfectly correct output on online IDE at Codechef.com/ide !https://codeforces.com/contest/1342/submission/78209696How is that possible? I have correct code but can't get accepted because of this. MikeMirzayanov pikmike
•  » » 2 months ago, # ^ |   0 When weird stuff like this happens, this usually means that your code has undefined behavior (like indexing an array with an invalid index or using the value of an uninitialized variable).
•  » » » 2 months ago, # ^ |   +3 I cross verified, there seems no variable uninitilaized. set I am using, made sure to only erase if a value exists. That makes me believe, there is no undefined behaviour. Please point out if I am missing something. Thanks Be_dos
•  » » » » 2 months ago, # ^ |   +21 RTE is because you are looping through set and erasing from it both in the same loop. for (auto cq: mem) and mem.erase(cq);. Mike might not be able to offer any help here.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Shit! I am happy yet sad. Too much thanks for the catch! i_love_arya_stark
•  » » 2 months ago, # ^ |   0 same thing happens to me also.https://codeforces.com/contest/1342/submission/78207115My code also gives a runtime error. I tried on CodeChef ide also, it works perfectly. But I can't find the reason.
 » 2 months ago, # | ← Rev. 3 →   +65 "Your goal is to make both given integers equal zero simultaneously"Why on earth did you have to use the word "simultaneously"? I thought it means we have to use operation 2 to go from 1 1 to 0 0 (to make it simultaneous) I wasted more than 20 mins on this until i read the description of the test case and asked the question to the setters
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 lmao same, just added to consider the case 'a' on both x and y and it got acceptedEDIT: sad thing is, i just noticed that problem statement says 'move from 0:1 to 0:0 is valid'
 » 2 months ago, # |   +56 I missed placing exactly n rooks part in E and tried solving this problem for almost entire duration of the contest: placing some x rooks on the board such that either all rows are occupied or all columns are occupied (or both). :/
•  » » 2 months ago, # ^ |   +8 Is there a way to place less than $N$ rooks and cover each square? I don't think so.
•  » » » 2 months ago, # ^ |   +8 Can place more though
 » 2 months ago, # |   +5 how to solve F?
 » 2 months ago, # |   +51 The word simultaneously in the text of Problem A was seriously misleading. It made it seem like the last operation must have been of type 2 so that both values would arrive at 0 simultaneously.
•  » » 2 months ago, # ^ |   0 wait that wasn't what they meant?
•  » » » 2 months ago, # ^ |   0 Apparently the values could arrive to 0 at different steps, as well. They made an announcement stating that during the contest.
•  » » » » 2 months ago, # ^ |   0 oh wow. I was just looking at the questions thank god I didn't give the contest. I mean what its not like I could go any lower lol
•  » » 2 months ago, # ^ |   -26 correct! atleast make the round unrated
 » 2 months ago, # |   +15 I misunderstood the term "simultaneously" and wasted 15 mins.
•  » » 2 months ago, # ^ |   0 and i wasted whole contest!
 » 2 months ago, # |   +23 Problem A made me zoned out for 25 mins.
 » 2 months ago, # |   +8 Upsolving C and D live on YouTube: https://youtu.be/XeK6lYKd8W4
 » 2 months ago, # |   +20 So my code for problem 'C' decided to run correctly 10 seconds after the contest cool cool cool cool cool cool cool cool cool cool cool cool cool cool
 » 2 months ago, # |   +1 https://codeforces.com/contest/1342/submission/78208967what's wrong in this solution for C?
•  » » 2 months ago, # ^ |   +1 Try this .13 4 112 12Ans should be zero but your code gives 1 .
• »
»
»
2 months ago, # ^ |
-76

# define ll long long int

using namespace std; int main() { int t; cin>>t; while(t--) { ll a,b,q; cin>>a>>b>>q; if(a==b) { for(int i=0;i<q;i++) { ll l,r; cin>>l>>r; cout<<"0"<<" "; } cout<<endl; } else if(a<b) { ll k=0;

for(int i=0;i<q;i++)
{
ll l,r;
cin>>l>>r;
ll cnt=0;

cnt=r-max(l,b)+1;
if(b%a!=0)
cnt-=b*((r/a)/b-(max(l-1,b-1)/a)/b);
else
{
ll g=__gcd(a, b);
cnt-=b*((r/g)-(max(l-1,b-1)/g));
}

cout<<max(cnt,k)<<" ";
}
cout<<endl;
}
else
{
ll k=0;
for(int i=0;i<q;i++)
{
ll l,r;
cin>>l>>r;
ll cnt=0;

cnt=r-max(l,a)+1;
if(a%b!=0)
cnt-=a*((r/a)/b-(max(l-1,b-1)/a)/b);
else
{
ll g=__gcd(a, b);
cnt-=a*((r/g)-(max(l-1,b-1)/g));
}
cout<<max(cnt,k)<<" ";
}
cout<<endl;
}

} return 0; }

•  » » » » 2 months ago, # ^ |   +6 At least put your code in spoiler ....19 12 11 192Ans is 121 and your code gives 169 .
 » 2 months ago, # |   +34 In problem A, the word 'simultaneously' confused me. Because of that, I thought if we have states (1,0) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and waste of 25 minutes.
•  » » 2 months ago, # ^ |   +6 just simple English, simultaneously means at same time. so A and B have to be zero at same time. you're not even supposed to have 1 0 in first place
•  » » » 2 months ago, # ^ |   0 What i meant to say is if we have (2,1) and a=1,b=10 then with use of Simultanouesly i calculated 10+1=11 as cost whereas actually it meant 2*(1)+1=3
 » 2 months ago, # |   +3 Hi, I tried a greedy solution for D. I sorted an array and added tests from the smallest, for each of them checking how many more I could add to one testcase. It got WA on test 11.What do you think is the counterexample?
•  » » 2 months ago, # ^ |   0 Try this: 5 3 1 2 3 2 1 2 1 1 You can construct an answer with 3 multitests instead of 4 as given by your code.
•  » » » 2 months ago, # ^ |   0 I cannot understand why this test case would give WA for greedy, I think it works!
•  » » » 2 months ago, # ^ |   0 Thanks! This is what I missed. The greedy solution doesn't work for repeated elements.
•  » » » » 2 months ago, # ^ |   0 Can you please explain why it wouldn't work?
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 You can make such testcases: {1 2} {1 2} {3} Whereas my solution would give: {1 1} {2} {2} {3}
 » 2 months ago, # |   0 Hey MikeMirzayanov, I got unnecessary 2 WA in problem A because I considered the condition to make both x and y simultaneously zero. Though I can't ask back the overall time lost due to this but if possible can those two penalties be removed! Thanks in Advance.
•  » » 2 months ago, # ^ |   +5 in correction too! it was not mentioned correctly that simutaneously is not to be considered! worst educational round!!
 » 2 months ago, # |   0 A and B again supersimple problems hidden in complecated text. In A I needed half an hour to get it that we cannot use opposite signs in operation b. Of course the statements states so, but that was mostly invisible to me.And D, sorry, simply to much words, I am not able to understand the sentences.Usually posting like this get downvotes. I know. Thanks.
•  » » 2 months ago, # ^ |   0 And your C is hacked now !
•  » » » 2 months ago, # ^ |   0 Yes, I was expecting that, the solution wasn't that great.
•  » » » » 2 months ago, # ^ |   -17 Check Mine it is accepted now!
•  » » » » » 2 months ago, # ^ |   0 Such Salty
•  » » » 2 weeks ago, # ^ |   0 Hope there isn't any number theory problem (Like this C problem)in today's contest.
 » 2 months ago, # | ← Rev. 3 →   0 What's wrong with my solution of F?What's the meaning of "wrong answer 'to' position should be in [1, 14] (test case 4)"？my submission
•  » » 2 months ago, # ^ |   +3 It looks like you print an auxiliary action somewhere in test case 2, so the numeration changes.
•  » » » 2 months ago, # ^ |   0 Well,I thought that I had printed the same answer as the example ouput,in test case 2.
•  » » » » 2 months ago, # ^ |   0 Sorry,I made a mistake.
 » 2 months ago, # | ← Rev. 2 →   +5
 » 2 months ago, # |   +4 Can someone tell me where my greedy approach for D fails. Here is what I did I sort the tests with respect to their sizes. I pick the array with largest size and put it in first testcase. Now I pick the next largest array , say of size X and the testcase with minimum tests till now and check if No. of tests in this testcase + 1 <= c[X]. If the condition holds, I put this test in the chosen testcase, otherwise make a new testcase. I got a wrong answer on TC 11
•  » » 2 months ago, # ^ |   0 try this test case : Spoiler8 4 1 1 2 2 3 4 3 4 2 2 1 1 Expected Output : 4 2 4 1 2 4 1 2 3 2 2 3 2
•  » » » 2 months ago, # ^ |   0 I couldn't understand how the greedy solution with your test case would give a different answer. Can you provide any other test case?
•  » » » 2 months ago, # ^ |   0 Kill me !! Kill me. My Greedy approach is correct . There was a single line I missed in the implementation. I used a min heap and I forgot to insert the previous topmost element(which I had popped) whenever I am creating a new testcase. It got accepted now and I am confused why could not I find this in more than an hour.
•  » » » » 2 months ago, # ^ |   0 It happens...
•  » » » » 2 months ago, # ^ |   0 can u pls explain your appraoch in brief I'm not able to get the min heap part .
 » 2 months ago, # |   0 In Problem C, O(test * 3 * gcd(a, b)) times remainder calculation cost TLE on test 4. Does the remainder calculation cost this much?:(
•  » » 2 months ago, # ^ |   0 Your time complexity for solution 78195345 is O(test * q * a * b). For every test, for every query you iterate x at most len times (which can equal to a * b) so you have around 100 * 500 * 200 * 200 = 2e9 operations times constant. You also have remainder calculation so I guess it is a rather predictable verdict.
•  » » » 2 months ago, # ^ |   0 Ohh! Thanks. My Bad...
•  » » » 2 months ago, # ^ |   0 But how this solution passed 78177360? I think it is also O(T*q*a*b). The time limit was 3.5 sec though.
•  » » » » 2 months ago, # ^ |   0 Then I was wrong and this solution passes because it has precalculated remainders and the previous one did not.
 » 2 months ago, # |   +2 How is 78182933 doesn't get TLE?It has linear complexity for every query or did I miss something?
•  » » 2 months ago, # ^ |   +11 As far i understand he calculates curr in the loop which is never used after that. As it is never used so compiler removes that loop as a part of optimization. As a result the loop doesn't get a chance to run so there is no tle.
•  » » » 2 months ago, # ^ |   +8 Thanks, you were right. I don't know that compiler can skip unnecessary operation.
 » 2 months ago, # | ← Rev. 3 →   0 Question C: Which number $x$ in the range $[100,200]$ other than $141-149$ gives $(x \mod 7)\mod 10 = (x \mod 10)\mod 7?$ The answer is $91$, so there should be $10$ such numbers.
•  » » 2 months ago, # ^ |   +1 140
•  » » » 2 months ago, # ^ |   +1 omg...........*cries in a corner*
 » 2 months ago, # | ← Rev. 2 →   +3 Fail on 1605th number. Oh cmon? How can I debug? 78209018
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 Here's your case:121 14 1291 823
•  » » » 2 months ago, # ^ |   0 Could you please tell 48011th number of test case 2? please.
•  » » » » 2 months ago, # ^ |   +5 148 32 116 99
•  » » » » » 2 months ago, # ^ |   +17 How do you find the test cases?
 » 2 months ago, # | ← Rev. 2 →   0 Got no idea what's wrong with my C submission.Could anyone take a look at it? https://codeforces.com/contest/1342/submission/78197703
•  » » 2 months ago, # ^ |   0 Why do you post the link of this blog here?
•  » » 2 months ago, # ^ |   0 You should've at least posted your submission (78197703) here and not the link of the blog entry.
•  » » 2 months ago, # ^ |   0 Update the link to submission
•  » » 2 months ago, # ^ |   0 Try below test 1 4 6 1 1 10 
•  » » 2 months ago, # ^ |   0 one major thing is the for loop from l to r.the range can be way orders of magnitudes over 10^9 .. so you'd get TLE even if your solution passed test 3.
 » 2 months ago, # | ← Rev. 3 →   0 is it possible to solve C without prefix sum / dp ?
•  » » 2 months ago, # ^ |   +2 There's a dp/prefix sum solution for C?I just excluded the numbers from i*LCM(a,b) to i*LCM(a,b)+max(a,b) for i=0,1,2,3.. from the range l to r
•  » » 2 months ago, # ^ |   +8 Yes it can be solved. You can check my submission https://codeforces.com/contest/1342/submission/78176991You can use the fact that x%a%b == x%b%a occurs at every multiple of lcm(a, b) for exactly max (a, b) times. You just get that and you have your answer in O(1) for each query, or log(n) if you consider GCD.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I've tried things similar to this but it's not working for me https://codeforces.com/contest/1342/submission/78229431can you tell any counter case on which this will be failing ?UPD: Just figured I was unnecessarily assuming that if a and b are divisible then the o/p will always be 0. thanks for the help tho
•  » » » » 2 months ago, # ^ |   0 i also assumed the same and was getting WA on test 2 can you pls explain why that assumption is wrong my submission on c
•  » » » » » 2 months ago, # ^ |   0 I also put the same condition though, and mine is accepted, so it must be something else, I will try looking into test cases after system testing.
•  » » » » 2 months ago, # ^ |   0 The problem was not the a and b divisible condition, but you did not take inputs when they were divisible. You just printed 0 q times. you should also take left and right inputs.
 » 2 months ago, # |   0 that fucking simultaneously word in problem A .......
•  » » 2 months ago, # ^ |   0 I don't even understand what are you talking about.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 they have mentioned that we have to convert x and y into zero simultaneously and later they made an announcement that it is not req.
•  » » » » 2 months ago, # ^ |   0 I agree that it might be misleading but I didn't have any problem with understanding that word. I take it as the meaning of a simultaneous equation and didn't notice that word until I see this comment.
•  » » » » » 2 months ago, # ^ |   0 Pls don't take it as the meaning of a simultaneous equation...
 » 2 months ago, # |   0 simultaneously means at the same time, doesn't it?
•  » » 2 months ago, # ^ |   0 exactly bro but then they later said that it is not req.
•  » » » 2 months ago, # ^ |   0 This is evident. It didn't help me at all.If they made it more explicit than in input 1 0, the answer would be a, I would understand."In particular, it is possible to move from x = 1, y = 0 to x = y = 0."In my mind: 1 0 1 1 0 0 ans = a movement with A and one with B.When you are participating in a contest, you just need to know code. When you create an EDUCATIONAL, you at least need to make understandable statements.
 » 2 months ago, # | ← Rev. 2 →   0 Exactly same solutions[user:MikeMirzayanov][user:pikmike] Disqualify both of them from contest
 » 2 months ago, # | ← Rev. 7 →   0 Hm, my idea for E was wrong, but I don't know how:Something like, when $0 < k < n$, we know either all rooks will be on distinct cols or all rooks will be on distinct rows, (and not both since $k \neq 0$), since two rooks sharing a col and two rooks sharing a row would leave some row and some column untouched (and thus the square at their intersection untouched). Then, we can WLOG assume all rooks are on distinct rows.Consider all the columns that contain a rook. If we consider all the rooks on that column a path graph, we see that it contributes exactly the number of edges it has to the number of pairs that attack each other. However, we also know that there will be $k$ edges in total, and since the whole graph is a forest, there should be $n-k$ components, i.e. $n-k$ columns containing rooks. So, the question then becomes how to partition $n$ objects into $n-k$ nonempty components (stirling # of second kind), and then multiply that by the $n-k$ columns that the rooks can occupy, and then multiply that by 2 to account for distinct columns cases.Anyone know where the error in this logic is? I plugged the formula into wolfram (mod[2*stirlings2[1337, 1295]*(1337 choose 1295), 998244353]) for test 4 and it was incorrect.EDIT: As BledDest pointed out, one just needs to multiply this final formula by $(n-k)!$ to index the columns for specific subsets, then it should be fine.
•  » » 2 months ago, # ^ |   +14 When you multiply the stirling # of second kind with a coefficient to choose $n - k$ columns, you should consider the fact that the subsets in definition of stirling numbers are not indexed.
•  » » » 2 months ago, # ^ |   0 Ah, good catch! Simple change to the formula. Thank you!
•  » » 2 months ago, # ^ |   0 shouldn't answer be simply stirling(n,n-k)*chose(n,n-k)*2 ?
•  » » » 2 months ago, # ^ |   0 Stirling number would count all required possible arrangements. Let one such possible arrangement be set1. Set1 would contain n-k elements, each element would correspond to a valid arrangement for a column. Then you have to select n-k columns from the board to place those valid arrangements (combinations), let the set of selected columns be set2. Then each different function from set1 to set2 would correspond to a different way you can arrange the rooks. (The function needs to be one-one and onto i.e invertible). Number of different functions from set1 to set2 is (|set1|)! or (n-k)!. You can also think of it as you have n-k diffrent objects and you need to put them in n-k different slots, how many ways are there to do it (permutations).Hope it helps!
•  » » » » 2 months ago, # ^ |   0 thanks bro!!!
 » 2 months ago, # |   0 https://codeforces.com/contest/1342/submission/78214455 what's wrong in this for C
•  » » 2 months ago, # ^ |   +3 a counter test case in case it helps : 1 248 12 2 491 1289 839 1234o/p for this should be 551 243 .Hope this helps !
 » 2 months ago, # | ← Rev. 3 →   0 Thanks.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 The only contest u joined is an April Fools’ Contest. Why would u even expect it to be a rated round.
•  » » 2 months ago, # ^ |   0 The first contest you took part in was April's Fools so it was unrated There is a 12 hour hacking phase after the contest so wait and you will get your rating tommorow.
 » 2 months ago, # |   +43 My rating and confidence level is going down simultaneously....Thanks for problem A.
•  » » 2 months ago, # ^ |   +3 xD same happened with me too!
•  » » 2 months ago, # ^ |   0 similar situation i was in last contest where i took around 90 minutes to solve A. Then past 2 days i solved around 20+ Div.2A from contest page 1; it really helped today
•  » » 2 months ago, # ^ |   0 you can't have a bad day as bad as mine ! I made a small typo in A initially, after making changes I forgot resubmitting it... :(Thanks to standings table that i finally submitted it after more than a hour .
 » 2 months ago, # |   +35 Time Limit of problem C was misguiding.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Why? You can answer each query in O(1)
 » 2 months ago, # |   +3 For problem B, I approached the question the same way as others. Printing "01" up to s.length() times. But in the clarification panel, the value of k for string "0011" is 4 but it is 2 if we print "01" up to n times(n == s.length()). Can anyone explain what am I missing here?
•  » » 2 months ago, # ^ |   0 I think you are right. The statement of B make me confused!
•  » » 2 months ago, # ^ |   0 it just states the definition of a period. Explanation in clarification panel is not much related to original problem.
•  » » » 2 months ago, # ^ |   0 Got it! It was s not t.
 » 2 months ago, # |   +115 task A
 » 2 months ago, # |   +4 Wait darn solved ABD and didn't get C...played around with gcds/mods and found some progress but whatever. Why doesn't O(ab(t+q)) pass? It's the naive solution but it seems to be well within the time limit of 3.5 seconds (2.4*10^7 operations -- i've had solutions with more operations and less time pass)
•  » » 2 months ago, # ^ | ← Rev. 5 →   0 You can do it in O(t*(ab+q)) if you precalcutate a prefix array. Such solution of mine took 498ms.This is one thing and the second is maybe Java is slower than C++.
•  » » » 2 months ago, # ^ |   0 Ah ok, I should have done prefix array, maybe the complexity would have been reduced by a constant factor and pass but yeah C++ is definitely faster than java too :(
•  » » 2 months ago, # ^ |   0 can you please tell me how many max operation can be done in 1 sec
•  » » » 2 months ago, # ^ |   +1 Not entirely sure but somewhere between 10^7 and 10^8 (since for some problems O(N^3) for N=500 passes and some other variants which have >=10^8 operations)
•  » » 2 months ago, # ^ |   0 and also how mush time should i spend on C and then jump to D.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Yeah, I also didn't get why the TL. No idea why my solution failed. But in the end I managed to do O(1) per query. The main thing to notice was that every number from b to lcm-1 is good. So you don't even need to precalc anything first and can answer each query in constant time.
•  » » » 2 months ago, # ^ |   0 can you please explain
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +5 First you need to check how many numbers are there between 1 and lcm-1 that satisfies the property. Let's say a is smaller. Then any number X greater than or equal to b will satisfy. We can prove this as follows.Let's say X = bq+r, Then (X%b)%a = r%a. Now we need to write (X%a)%b in similar form. Here notice that bq is less than X, and since X is less than the LCM, bq is also less than LCM. Therefore it can't have a as a factor. So bq = aq'+r'. Therefore X = aq'+r'+r. Taking modules, we will get (r+r')%a. Since r' is neither 0 nor a, therefore it is different than r%a. Thus any number greater than equal to b satisfies.(Upto LCM that is)
•  » » » » » 2 months ago, # ^ |   0 how are you comparing (r+r')%b and r%a???
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 (X%a)%b is reduced to ((r+r')%a)%b. If you notice, the second modulo by b is unnecessary as (r+r')%a is always less than b. So it reduces down to comparing r%a and (r+r')%a