By BledDest, 12 months ago,

Hello Codeforces!

On Oct/10/2021 12:05 (Moscow time) Educational Codeforces Round 115 (Rated for Div. 2) will start. Note that the start time is unusual.

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 Alex fcspartakm Frolov, Mikhail awoo Piklyaev, Max Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

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

Hello once again, Codeforces!

We are thrilled to congratulate our faculty member Nikolay KAN Kalinin on his first place at the ICPC World Finals, celebrated in Moscow, Russia. Years of training by Nikolai and his team from Nizhny Novgorod State University lead them to the top of the scoreboard, defeating teams from 116 other universities and becoming world champions.

We would also like to congratulate our future student Egor mhq Dubovik, who won the silver medal with the Belarusian State University. Egor will join our Masters in Computer Science in the coming weeks.

We are looking forward to seeing Nikolay again next January when he teaches his course on Advanced Algorithms and Data Structures alongside Mike Mirzayanov. In this course, students focus on key and in-depth algorithms and data structures that form a modern computer specialist’s toolkit.

We are always excited to see Codeforces participants as our students here at Harbour.Space, so once again we’ve given a special discount (up to 70%) for the single course participation in Barcelona, Spain (travel cost and accommodation are not included).

Good luck on your round, and see you next time!

Harbour.Space University

• +310

 » 12 months ago, # |   +40 Note that the start time is unusual is becoming quite usual now.
•  » » 12 months ago, # ^ |   -19 It is very friendly to East Asian players, I hope it will be more than a few times . We don't need to stay up till 2 a.m. to sleep.QWQ
•  » » » 12 months ago, # ^ |   0 Don't you have Chinese version of codeforces?
•  » » » » 12 months ago, # ^ |   +11 It seems not
•  » » » » 12 months ago, # ^ |   -26 cf is wonderful
•  » » » » » 12 months ago, # ^ |   +29 Google, Youtube, Twitter, Amazon... are also great
•  » » » » » » 12 months ago, # ^ |   -40 china have its wonderful Google，YouTube，Twitter，Amazon
•  » » » » 12 months ago, # ^ |   0 we have a mirror site This but the contests are all sync-ed with This Codeforces
•  » » » 12 months ago, # ^ |   +3 Yes,I'm very happy.
 » 12 months ago, # |   +26 Great time for Chinese players!
•  » » 12 months ago, # ^ |   -87 Why ?
•  » » » 12 months ago, # ^ |   +21 It's 17:05 pm.
•  » » » » 12 months ago, # ^ |   -98 bad and don't tell it again
•  » » 12 months ago, # ^ |   +6 Yes ! very good !!!
 » 12 months ago, # |   -14 Thank you for the contest. I hope that my rating will be increase after doing this contest
•  » » 12 months ago, # ^ |   +10 Hmm...I think it's not as easy as you think
•  » » » 12 months ago, # ^ |   +12 not as bad as you think too
•  » » 12 months ago, # ^ |   -9 And your contribution will decrease.
 » 12 months ago, # | ← Rev. 4 →   -92 I hope codeforces stop changing its contest times.
 » 12 months ago, # |   -8 good luck to everyone for the competition!
 » 12 months ago, # |   -17 Why is it so early dudeee, some people have school
•  » » 12 months ago, # ^ |   +29 Yes of course "School in Sunday"
•  » » » 12 months ago, # ^ |   +12 what's wrong with school on sunday? some schools have weekends on Friday and Saturday instead of Saturday and sunday
•  » » » » 12 months ago, # ^ |   -15 for example what school?
•  » » » » » 12 months ago, # ^ |   +14 These unusually timed contests are not for unusual schools!
•  » » » » » 12 months ago, # ^ |   0 Allame helli
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   -22 In many Muslim countries and in Israel weekend is not on Sunday.
•  » » » » » » 12 months ago, # ^ |   -31 There's a reason muslim countries keep schools on Sunday, else this pissfull community will start planning for their next attack, xDD
•  » » » » » » » 12 months ago, # ^ | ← Rev. 3 →   -30 AFAIK in your country it is mostly Hindu mobs violently attack Muslims. Is it because they don't go to school on Sunday? Anyway, what are you doing in this comment section if you did not participate in the round?
•  » » » » » » » » 12 months ago, # ^ |   -24 Ok I don't know why you are looking at one side, hindu mobs violently attack jihadis, whenever they provoked, and such attacks will continue, until you pissfulls will not stop nonsense. By the way, whole world is fed up of you all, ISIS, LeT, JeM, AlQuaeda, AL-Shabab, Ahrar-al-Asham, Taliban........., the list is endless.Not only different religion, you people fight within your own, Taliban is the latest example, you are killing your own brothers. Hope they all get 72 virgins xDDD
•  » » » » » » » » » 12 months ago, # ^ |   -14 Yeah, I know. I've seen those "jihadists" in "Slumdog Millionaire".
•  » » » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 There is no reason for your disrespectful comment for a whole community, I think that codeforces should delete comments that are disrespectful or full of hate to others, I think you need to understand that some people have understood our religion wrongly and people like you just don't want to even bother searching before judging the whole community, I hope no one in this community (cp community) use bad words to describe others without any reason and remember every bad word you said will return to u.
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   -9 Very well said. India has a long history of religion-based sectarian violence, but there is absolutely no place for hate speach in an international community like codeforces. And I believe this thread will be deleted. It just has not been brought to their attention yet.
•  » » » » » » » » 12 months ago, # ^ |   -11 I won't argue much but Why do all terrorists turn out to be muslims? & Why all terror groups around the world are having muslims as their members & heads?As far as knowing your religion is considered, whoever doesn't follow islam is considered as "infidel" & islam shall dominate the world, are the teachings of Quran.Reference
•  » » » » » » » » » 12 months ago, # ^ |   0 I have another Wikipedia link for you.
•  » » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 The last part of your comment applies to Christianity. The word "infidel" is of Latin origin. Christians have been using it to designate those who did not accept the divinity of Jesus, against whom they were perpetrating violent crusades.
•  » » » » » » » » » 12 months ago, # ^ |   0 Ok Agreed about saffron terrorism. Now another link for you to take a look & compare the length of these articles, you may understand my point. Reference
•  » » » » » » » » » 12 months ago, # ^ |   0 But at least you agree that your claim that all terrorists turn out to be muslims is false, don't you?
•  » » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 No, I don't agree. Reference Above is a list of all riots in India, just see the cause of communal riots, you will realise my point. And as I have already stated earlier that such violences had occurred due to jihadis provocations, & will continue to happen further. Hindus are never the 1st ones to attack, although they should be. Also note that saffron terrorism is actually not terrorism like suicide bombing & all, it is just violence, that too never started by Hindus.
•  » » » » » » » » » 12 months ago, # ^ | ← Rev. 8 →   0 Stop that BS. Your references show nothing. You just can't forget that some centuries ago you were ruled by Muslims.Here are your "provoked" Hindus.And while we are at it here are Christians turning the other cheek in a different part of the world.And be careful — Mike's last name has a Muslim (Persian) root (Mirza), the same as Punjabi village Mirzajan. :)))
•  » » » » » » » 12 months ago, # ^ |   -9 MikeMirzayanov don't you think that the comments section needs to be cleaned of all this crap?
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 I can understand when a statement of an opinion is getting downvoted, but when people downvote a statement of an indisputable fact — I don't get it.
•  » » » » 12 months ago, # ^ |   0 yes dear!!!!
•  » » 12 months ago, # ^ |   0 Some people also have school during the usual contest time.
•  » » 12 months ago, # ^ |   0 I wish rather than wasting my time on cracking JEE in school I utilized it here.
•  » » » 12 months ago, # ^ |   0 Yeah,I feel the same!
•  » » 12 months ago, # ^ |   +5 For Chinese and Japanese，this tmie is better than usual time, as the usual time is 10：35~01:05 in Peking, China.
 » 12 months ago, # |   +9 Too sad we are not seeing vovuh's handle in writers part of an educational round...
 » 12 months ago, # | ← Rev. 2 →   -16 [deleted]
•  » » 12 months ago, # ^ | ← Rev. 4 →   -57 [deleted]
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 [deleted]
•  » » » 12 months ago, # ^ |   0 and so do I.
•  » » » » 12 months ago, # ^ |   0 How I wish vinchurkar had written "You know the rules ", it would be a nice rickroll. You know the rules, and so do I...
•  » » 12 months ago, # ^ |   0 I think so too. I hope I turn green too
•  » » 12 months ago, # ^ |   0 Same too, good luck.
•  » » 12 months ago, # ^ |   0 in Egypt,we take this sentence as a joke, and I do not mean any offensive mean by it.
 » 12 months ago, # |   +3 All the best guys!
 » 12 months ago, # |   +3 Why the participation has reduced a little bit from previous 2-3 contests?
•  » » 12 months ago, # ^ |   0 Note that the start time is unusual.
•  » » » 12 months ago, # ^ |   0 It was just 30 mins plus-minus in the last contest still participation was low!
•  » » 12 months ago, # ^ |   0 I think it is because time, 4h05PM or 5h05PM hard for us to join the contest.
•  » » 12 months ago, # ^ |   +8 Due to universities mid exams I guess !!
 » 12 months ago, # |   0 Thanks for all your efforts. Is it not possible to make contest on 14:45 with GMT?
 » 12 months ago, # |   +10 RIP sleep schedule. Gotta get up at 5am for this contest.
•  » » 12 months ago, # ^ |   +8 In China we have to stay up until 2am to participate in contests with usual times :(
 » 12 months ago, # |   -41 I think the writer also wants to see CSK vs DC (IPL 2021) Qualifier so this may be reason for this unusual time.
•  » » 12 months ago, # ^ |   0 may be
 » 12 months ago, # |   -11 " Note that the start time is unusual " this mean no contest for me
 » 12 months ago, # |   0 Another friendly time for Chinese users! Looking forward to great problems and having fun! I hope I will not be hacked in open hacking.
 » 12 months ago, # |   0 Hoping for a great contest OvO
 » 12 months ago, # |   0 The start time of this contest is very friendly to Chinese contestants! Hope I'll perform well in this contest.
 » 12 months ago, # |   -27 It's just dinner time. I'm going to spend it with bread
 » 12 months ago, # |   -32 In China, you can take a nap, wake up and start playing games
•  » » 12 months ago, # ^ |   +4 The game I said refers to playing codeforces. Please don't get me wrong
 » 12 months ago, # |   -8 I hope I will be specialist after this round.
 » 12 months ago, # | ← Rev. 3 →   -11 I think i will be depressed after this round :')
•  » » 12 months ago, # ^ |   0 I enjoyed problem D too much :DThank you!
 » 12 months ago, # |   +11 I enjoyed this round There is really very interesting problems
 » 12 months ago, # |   0 How to solve D?
•  » » 12 months ago, # ^ |   +10 I tried to use inclusion-exclusion principle. The answer is (different a) + (different b) — (different a and b). I have figure out how to calculate "different a" and "different b", but didn't figure out how to calculate "different a and b".
•  » » » 12 months ago, # ^ |   0 Lol, I did the same. Couldn't pass it during the contest. Later debugged and got accepted. Definitely it was an overkill..
•  » » 12 months ago, # ^ | ← Rev. 2 →   +33 I calculated the total possible solutions which will be nC3 and then subtracted the number of bad combinations(observe that in a bad combination 2 problems will be having the same topic type and 2 problems will be having the same difficulty).
•  » » » 12 months ago, # ^ |   +17 Damn idk why i got stuck in a much harder solution .. thanks
•  » » » » 12 months ago, # ^ |   0 you are not alone!
•  » » » 12 months ago, # ^ |   0 I understand. Thanks!
•  » » » 12 months ago, # ^ |   0 But I think there are some cases which you will remove twice how you solved that? For Example In the first Test Case 2 4 3 4 2 1 1 3You will remove index 1 3 4 because of repetition of same topic 2 and again you will remove indexes 1 3 4 because of the same difficulty 4 how you solved this case?
•  » » » » 12 months ago, # ^ |   0 Your approach is different from @aniket_lakhotia.You are calculating topicwise and diff wise separately while he is calculating per problem.
•  » » 12 months ago, # ^ |   0 Try to calculate the number of bad combinations and then it's trivial.
 » 12 months ago, # |   +1 How to solve E?
•  » » 12 months ago, # ^ |   +3 with dp. the main point is for each flip you just have to update O(n) dp values which makes it O(nq) that fits in time limit
•  » » » 12 months ago, # ^ |   +6 I was wondering the whole time why's $q \leq 10^{4}$ and not $10^{5}$, I knew that solution was somewhat related to it. Unfortunalely, I wasn't able to figure it out in time.
•  » » » 12 months ago, # ^ |   0 Can you please explain further, my brain is fried up right now and I am unable to see the dp states..:P
•  » » » » 12 months ago, # ^ |   +9 yes sure let dp[x][y] be the number of stair cases that start from point x,y also dp1[x][y] : number of stair cases from x,y that second move is right and dp2[x][y] : number of stair cases from x , y that second move is down . now we can easily update all these dp values (you can see my submission) sorry for bad english
•  » » » » » 12 months ago, # ^ |   0 No no the english is quite clear, and thanks. I think I will see ur submission now.
•  » » » » 12 months ago, # ^ |   +3 and also for each query update you just have to update these points : (x,y) (x-1,y) (x,y-1)(x-1,y-1) (x-2,y-1) (x-1,y-2)...which is in total at most 3*min(n,m)
•  » » » » » 12 months ago, # ^ |   0 Ahh yes I see.. BTW do u think this was solvable by Segment Tree or some similar data structure? I would think so considering the type of problem.
•  » » » » » » 12 months ago, # ^ |   0 maybe but it is not trivial
•  » » » » » » » 12 months ago, # ^ |   0 Yeahh
•  » » » » » 12 months ago, # ^ |   0 Hey, can you please explain why only those points have to be updated? I think points like (x, y-2) also need to be updated
•  » » » » » » 12 months ago, # ^ |   0 No staircase from x,y-2 will cross x,y
•  » » » » » » » 12 months ago, # ^ |   0 Thanks!! Really nice solution
•  » » 12 months ago, # ^ |   +3 There is a technique know in Brazil as Color Update, it consists in store in a set intervals that we assign a given color, each position can have at most one color. You can use this idea to color an interval, ask the maximal interval of the same color that contains a given point, etc. Using this idea just build maximal staircases, for each position store in which maximal staircases it is, and in which position. Then using Color Update technique the solution is straightforward.
•  » » » 12 months ago, # ^ |   0 You can see this idea in my code 131497457.
 » 12 months ago, # |   0 How to solve D ? I found it much harder than E or am i missing something ?
•  » » 12 months ago, # ^ |   0 just find cases where the given condition fails and remove it from total cases
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 Inclusion and Exclusion Principle, the total number we can get without any constrains is (N choose 3), then we subtract the invalid ones.the invalid ones must have 2 similar elements in both sides so we just count that.https://codeforces.com/contest/1598/submission/131438774
•  » » » 12 months ago, # ^ |   +1 could you elaborate how you calculated invalid ones
•  » » » » 12 months ago, # ^ |   +4 Invalid ones should have at least two similar elements in both arrays let's say we picked the current element.A is the topic B is the difficulty so A should appear at least one more time. B also should appear at least one more time. so we count the number of other A's multiply by the number of other B's and keep subtracting this from the answer, and this will work nicely with the constrains we have as (A,B) can't repeat again together. sorry it's hard to explain, but you can go through my code for better understanding.
•  » » » » » 12 months ago, # ^ |   +1 kind of got it. Thanks for the effort
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Use Multiplication Principle.Preprocess each element's number of occurrences , and mark them as cnta[] and cntb[].Enumerate i from 1 to n , and the invalid ones are sigema((cnta[a[i]] — 1) * (cntb[b[i]] — 1)).Hope you can understand it.(My English isn't good).
•  » » » » » 12 months ago, # ^ |   +3 thanks man.understood.
•  » » » » » » 12 months ago, # ^ |   0 What's more.Because of "It is guaranteed that there are no two problems that have the same topic and difficulty at the same time".Invalid ones are a group with two identical "elements A" and two identical "elements B". So we just need to select the first pair first, and then select the other two pairs which have one "element A" and one "element B" which are the same as the first pair. The formula is just written in my last comment.I think this comment is more clear than the last one.By the way , wish you good luck. :)
•  » » » » » » » 12 months ago, # ^ |   0 yup , just got the code accepted.this comment really summed it up for me ^_^
•  » » 12 months ago, # ^ |   +5 Definitely missing something. $D$ was a nice exercise of complement counting. I solved it by adding edges $a[i], b[i]$ to empty bipartite graph with $2$ partite sets of size $n$ and then the problem becomes equivalent to counting the number of paths with $3$ edges in this graph.(at this point the problem is quite easy by storing frequency array of both $a$ and $b$) Of course this is only for better visualization. In reality you never actually do a graph algorithm to solve the problem. But I personally found this as a nice way to see the problem.
•  » » » 12 months ago, # ^ |   0 Can you please elaborate your visualization?
•  » » » » 12 months ago, # ^ |   0 Uhh just add vertices in the graph and do simple case work for counting the complement. You will find every valid element in the complement corresponds to a path of length $3$ in the graph u made...
•  » » 12 months ago, # ^ |   0 You are not alone.
 » 12 months ago, # |   -8 Can E be solved with link cut tree ?
 » 12 months ago, # |   -70 Definitely moving up from Pupil today!! How was the contest for yall guys?
•  » » 12 months ago, # ^ |   +10 There are so many comments in your code :-\
•  » » » 12 months ago, # ^ |   +37 Removing the comments in your submission of problem d, its remarkably similar to the solution in this image SpoilerI don't know if you will be caught by plag check but, What's more shocking is the audacity of your comment " Definitely moving up from Pupil today!! How was the contest for yall guys? "
•  » » » » 12 months ago, # ^ |   +16 its remarkably similar it's equal.
•  » » 12 months ago, # ^ |   +34
•  » » » 12 months ago, # ^ |   +8 lmao adding random comments to avoid plag
•  » » 12 months ago, # ^ |   +21 You seem to be a Cheater
•  » » » 12 months ago, # ^ |   +15 Ironical to spam comments just to avoid plag check. Where is your dignity lol
•  » » 12 months ago, # ^ |   +9 you are not going to see any rating change.
•  » » 12 months ago, # ^ |   +11 You piece of shit. Look into the mirror and ask yourself what have you gained from cheating. You are a disgrace. Your parents will be ashamed of you.
•  » » 12 months ago, # ^ |   0 I have seen many comments in your code.
•  » » 12 months ago, # ^ |   +2 Someone, Please hack this cheater's solution The same copied codes by others are hacked by many people
•  » » 12 months ago, # ^ |   0 i don't mean to spread hate but his solutions from past contest also have spamming comments, just trying to draw similarity that something might have happened then too.
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 Because, of you dumbass looser many who deserve are not able to reach. You hadn't even solved A by yourself. Many deserving who practiced daily really hard and solve 600 problems and are not able to reach above pupil because of you people. This things really disappoint them. You should be ashamed of yourself.Writing this things after doing cheating what you wanna to prove? Why are you humiliating others.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 You have never practiced on codeforces (Just 24 problem that you had done using cheating in contests). You just come here to increase your rating using wrong means. This place is not for garbage. You better accomodate yourself in codechef. And try to become 6 star(As I am sure you must be atleast 5star cheater).
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 I will watch your submissions of the next contest. And if I found, I would write a blog. Take it as warning. Better to not do this type of activities in future. I always talk point to point. I don't care if you feel bad or insulted. Take it as a chance to improve your character.
•  » » 11 months ago, # ^ |   0 he is still cheating
 » 12 months ago, # |   0 solved D but tough Java constraints :( https://codeforces.com/contest/1598/submission/131447806
•  » » 12 months ago, # ^ |   0 https://codeforces.com/contest/1598/submission/131456342 it worked with c++
•  » » 12 months ago, # ^ |   0 I used the exact same approach as you did, and got AC in java. 131438128 I am pretty sure that your issue is at the line where you create a new ArrayList (computeIfAbsent). Try to change that to putIfAbsent and it should work fine.
•  » » » 12 months ago, # ^ |   0 thanks, it worked! do you know that makes computeIfAbsent so slow?
•  » » » » 12 months ago, # ^ |   0 No idea, but my guess is that for some reason it generates a new Arraylist, even if some element is not absent resulting in a new copy every time.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 sorry for necroposting but I found out what was the problem with computeIfAbsent. https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function-the reason of MLE here is that computeIfAbsent passes key as argument for ArrayList constructor so ArrayList is instantiated with given capacity which can lead to MLE 166786739 AC with computeIfAbsent
 » 12 months ago, # | ← Rev. 5 →   +5 A round a day keeps my rating away.It seems that I will get about -50 rating after this round. I hope I can remain an Expert.By the way , Problem D is such an excellent problem although I didn't solve it in this round. It really gives me a lesson.
 » 12 months ago, # |   0 Talk about the shortcomings of this game (this does not mean that I do not support the author, I support every author of CF), the data range of the C question is very intriguing (why is there a data range that cannot be covered by int64?), I am useless Over int128, so I spent nearly 20 minutes on compilation errors. Of course, the other topics are very good, thank you very much to the authors!
•  » » 12 months ago, # ^ |   +21 I guess you checked for $sum \cdot (n-2)=(sum-a_1-a_2)\cdot n$?Notice, that you can shorten this check to $2 \cdot sum = a_1 n + a_2 n$ for which both sides do fit in a long long.
•  » » » 12 months ago, # ^ |   0 The first solution I came up with was to use long double and count but it's timed out. So I replaced the count through the function with map :3
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 can you explain more how to solve C problem in more details please?, and can be solved by a formula , thanks in advance.
•  » » » 12 months ago, # ^ |   0 Sorry, I'm not familiar with CF pages.In fact,I think your idea is great.
•  » » 12 months ago, # ^ |   0 a data range that cannot be covered by int64? Problem C?
•  » » » 12 months ago, # ^ |   0 I use Double to accept https://codeforces.com/contest/1598/submission/131504681
•  » » 12 months ago, # ^ |   0 int64 works fine for C. You just need to reduce the equation with algebra. Spoiler$\frac{\sum v_{i}}{n} = \frac{\sum v_{i}}{n-2} -y$$(n-2) \sum v_{i} = n \sum v_{i} - ny$$ny = 2 \sum v_{i}$$y = \frac{2 \sum v_{i}}{n}$
•  » » 12 months ago, # ^ |   0 I think "GNU C++17" does not support int128.
•  » » 12 months ago, # ^ |   0 Without int128: 131432277
•  » » » 12 months ago, # ^ |   0 Can you look at my submission : https://codeforces.com/contest/1598/submission/131469087I have used unsigned long long int but still it's failing...!!! I don't think it should overflow since (n * amx) will be (20^5 * 10^9)= (20^13) which should be well under long long.Please let me know where is the error.
•  » » 12 months ago, # ^ |   0 I used a different approach131417048
 » 12 months ago, # |   +3 How To solve D ?
•  » » 12 months ago, # ^ |   0 Let be ai = task, notice, that for a we can take (n * (n — 1) / 2) other tasks and lets just remove pairs of tasks that we can not use with a. This is the amount of the same difficulty * the amount of the same topic
•  » » 12 months ago, # ^ |   +15 If we consider pairs as coordinates on 2D plane and since all points are distinct, only way three points selected at random dis-satisfy the given conditions is when they form the right angle triangle. Hence subtract number of right angle triangles from NC3.
•  » » » 12 months ago, # ^ |   +4 What an excellent and unique understanding!
 » 12 months ago, # |   0 what is the meaning of open hacking phase is running, can i get points if i solve problems or what it is ?
•  » » 12 months ago, # ^ |   0 You can hack other's submissions. Hacking doesn't earn or loss points in this contest. Feel free to hack if you find any bugs in other's code.
 » 12 months ago, # |   +20 I misunderstood D and thought that both the given conditions should be satisfied. Later obtain the actual answer easily from the answer I calculated. Anyone did the same?
•  » » 12 months ago, # ^ |   0 D was combinations problem though looks like graph
•  » » » 12 months ago, # ^ |   0 break into smaller subproblems simplify using pnc and generalize the formula to compute in O(nlogn)
•  » » 12 months ago, # ^ |   0 why u didnt check examples?
•  » » » 12 months ago, # ^ |   0 I'm lazy and I wanted to solve the problem faster.
 » 12 months ago, # |   0 Great time, but problems hard for me to think of solutions for solved it. Thank you for your problem. But next contest u can change the time :(. (4h05 PM, I studing in my university.)
 » 12 months ago, # |   0 In C why (sum*(n-2))==(sum-a1-s2))*n is wrong?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 overflow.sum can be at max 2e5 * 1e9 == 2e14And then sum*n==2e14*2e5 == 4e19 which is more than the limit of the long data type
•  » » » 12 months ago, # ^ |   0 I thought long long will handle this :(
•  » » » 12 months ago, # ^ |   0 Can anybody tell me what I am missing so that following 2 codes gives different results.Problem CCode 1 : Accepted Code 2 : Wrong Answer Thanks in advance
•  » » 12 months ago, # ^ |   0 I don't think this is wrong, maybe its an overflow issue
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 sum/n = (sum — a1 — a2)/(n-2)=> (sum*(n-2))==(sum-a1-s2))*nbut k = sum/n, k maybe = 1e9, n maybe = 2*1e5 => k * n * n = 4 * 1e19 > max long long
•  » » 12 months ago, # ^ |   0 bro power will reach to something 10^20 and long long has range 10^18
•  » » » 12 months ago, # ^ |   0 Can't we find mean using this method ? double k = 0; //k is the mean int t = 1; for (double x : arr) { k += (x - k) / t; ++t; }
•  » » » » 12 months ago, # ^ |   0 avoid doing such operations bro.it won't give you the correct ans.there are always chances of floating pint error,performing such operation is not advisable
 » 12 months ago, # | ← Rev. 5 →   -67 I love Russian Contests.
•  » » 12 months ago, # ^ |   +36 The fact is that there are many Chinese top coders like Miracle03 and QAQAutoMaton are busy in teaching some new coders.So they don't have time to write more contests.The rounds you see are written by some students who love coding , and I think they're good enough for these younger coders.I think they need more encouragement but not prejudice.I do hope you could post comments with less discrimination and prejudice.And I think Chinese writers can get progress very soon.Best wish.
 » 12 months ago, # |   0 In problem C, what i did was to find all the pairs whose sum is equal to twice the original mean, but it gave wrong answer. Can anyone explain why?
•  » » 12 months ago, # ^ |   0 dont use decimals.the numbers are intergers so sum_of_numbers%n must be 0 else the ans will be 0.
•  » » » 12 months ago, # ^ |   0 Can anybody tell me what I am missing so that following 2 codes gives different results.Problem CCode 1 : Accepted Code 2 : Wrong Answer Thanks in advance
 » 12 months ago, # |   +4 Too good questions (:)
•  » » 12 months ago, # ^ |   0 hh
 » 12 months ago, # |   0 Where is the solution of this contest ？ I think I need it！
•  » » 12 months ago, # ^ |   0 If you find it,could you please share with me?I need it too.
 » 12 months ago, # |   0 there is a solution for problem Enotice that each staircase's length at most 2000and each point have 4 staircases at mostso U can use brute force to solve itthe complexity will be $O(Q(N+M))$
•  » » 12 months ago, # ^ |   0 Oh, i mean that you can start only 4 staircases at each free cell
 » 12 months ago, # | ← Rev. 6 →   0 when will publish editorial?
•  » » 12 months ago, # ^ |   0 May be after hacking phase is finished
 » 12 months ago, # |   0 Awesome round. Love problem F
•  » » 12 months ago, # ^ |   -29 really? its the worst round for me
•  » » 12 months ago, # ^ |   0 F has too many details :( Is it only for me?
 » 12 months ago, # |   0 solved E just several seconds after the round ends, what a pity! :(
 » 12 months ago, # | ← Rev. 3 →   +10 Awesome round with much less extra hackings (comparing with other Edu rounds) ,excepting problem D.
 » 12 months ago, # |   0 Can anyone help me with the approach to solve B?
•  » » 12 months ago, # ^ | ← Rev. 7 →   0 its a kind of first finding the days that have more than or equal n/2 1's then checking if any two days combinely having all the 1's. import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t =sc.nextInt(); while(t--!=0) { String result = "NO"; int n=sc.nextInt(); int[][]tr = new int[n][5]; int[] c = new int[5]; for(int i=0;i=n/2) { i1=i; for(int j=i+1;j<5;j++) { if(c[j]>=n/2) { i2=j; //System.out.println(i1 + " : " + i2); int cnr=0; for(int pr =0;pr
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Day 1: (Group 1)Day 2: (Group 2)u can make the array a[5][n] // u can make by vector Day I — (Day I in Day J)Day J — (Day I in Day J)// n/2 is member of singe group if (Day I have member == n/2 and Day 2 have member == n/2)
•  » » » 12 months ago, # ^ |   0 for the third one i did brute force for sets grouping and mean find , i think we need to invert the equation and use an extra data structure, correct me if i am wrong #anhung2k3
•  » » » » 12 months ago, # ^ |   0 u need to read the problem again. Member in group 1 and group 2, not the same a day.if(tr[pr][i1]==1||tr[pr][i2]==1) { cnr++; }
•  » » » » » 12 months ago, # ^ |   0 please check my solution its accepted i am checking n/2 greater values in the different days and taking all the days which are greater than n/2 and then i am comparing the days
•  » » » » » » 12 months ago, # ^ |   0 Sorry, I don't read check n/2 of you. Tks for a solution to solving problems.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 There are only 5 days. We can enumerate all pairs of days and find if it is possible to seperate students into two groups. Let's say we choose day A and day B. If there are some students (possibly one) who can't attend day A and day B, then {A, B} isn't the answer. We count the students who can only attend at day A, students who can only attend at day B, and students who can attend at both day A and B. Codevoid solve() { int n; cin >> n; vector> can(n, vector(5)); vector cnt(5); for(int i = 0; i < n; ++i) { for(int j = 0; j < 5; ++j) { cin >> can[i][j]; cnt[j] += can[i][j]; } } if(n & 1) { cout << "NO\n"; return; } const int need = n >> 1; for(int a = 0; a < 5; ++a) { for(int b = a + 1; b < 5; ++b) { if(cnt[a] >= need && cnt[b] >= need) { bool ok = true; int f = 0, g = 0, h = 0; for(int row = 0; row < n; ++row) { if(can[row][a] && !can[row][b]) ++f; else if(!can[row][a] && can[row][b]) ++g; else if(can[row][a] && can[row][b]) ++h; else { ok = false; break; } } if(!ok) continue; int f_need = max(0, need - f); int g_need = max(0, need - g); h -= f_need; h -= g_need; if(h >= 0) { cout << "YES\n"; return; } } } } cout << "NO\n"; } 
•  » » » 12 months ago, # ^ |   0 Thank u so much, got it entirely
 » 12 months ago, # |   +6 Nice round. Totally enjoyed it!!
 » 12 months ago, # |   0 Please explain how to solve D. >_<
•  » » 12 months ago, # ^ |   0 I think we need to use bfs or dfs
•  » » 12 months ago, # ^ |   +15 Substract the illegal ways from all the ways.There are in total $\dbinom n 3$ ways to choose $3$ elements among $n$ of them. Now considering how many of them are illegal, that is, none of the two conditions in the statement is satisfied.To calculate it, we first define cnta[x] as how many times topic x has occured and cntb[x] as how many times difficulties y has occured.Then assume that we choose the $i$ th problem, since no two problems share the same $a_i$ and $b_i$, we can assume the second problem we choose shares the same $a$ with $a_i$ and the third problem shares the same $b$ with $b_i$. So we just need to calculate 1ll * (cnta[a[i]] - 1) * (cntb[b[i] - 1]).You can view my code 131440598 for more details.Sorry for my poor English(
•  » » » 12 months ago, # ^ |   0 Can you provide a more rigorous proof?It seems that a lot of the solutions for D are getting hacked (mine included) and they all count the answer the same way you are describing. I don't know why though.
•  » » » » 12 months ago, # ^ |   +8 They are hack just because they didn't use long long
•  » » » » 12 months ago, # ^ |   +8 In your code, when it comes to nA += (ca[a[i]]-1) * (cb[b[i]]-1);, I suppose that it overflows the int limitation
•  » » » 12 months ago, # ^ |   0 thank you
 » 12 months ago, # |   0 The penalty for each incorrect submission until the submission with a full solution is 10 minutes What is the meaning of this?
•  » » 12 months ago, # ^ |   0 Penalties are for the leader board. More time used means lower ranking.
•  » » » 12 months ago, # ^ |   0 Oh okay. I am a little confused, will I get penalities for multiple wrong answer submissions for a problem even If i don't solve it?
•  » » » » 12 months ago, # ^ |   +3 No, penalty will be added only for those problems which are accepted.
 » 12 months ago, # |   +5 Any hack tc for D ?
•  » » 12 months ago, # ^ |   0 I think the hacks exploit this.I believe you can have all numbers from 1 to 100000 and create the pairs (1, 100000) (2, 100000) ... (100000, 100000), (1, 1), (1, 2), ... (1, 99999).In that way there are $2\cdot 10^5 - 1$ pairs (possible because $n\leq2\cdot 10^5$) but the product of counts will overflow if they are initialized as int. (for example considering the first pair the counts will both be 99999)
•  » » » 12 months ago, # ^ |   0 I used size_t( vector.size() ) in my code, but it still be hacked.Do you know why?
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   0 You've been overflown. Thought your ans is 'long long', you are not yet familiar how expression is evaluated. It's in this line: ans += (cntb[d].size() - 1) * (x.se.size() - 1);Try to output: long long ans = 100'000 * 100'000;
•  » » » » » 12 months ago, # ^ |   +3 Thanks for your reply!Could give me one testcase? I test my code with input:n = 200000a = [1, ..., 1, 100001, 100002, ..., 200000]b = [1, 2, ..., 100000, 1, ..., 1 ]When x.fi = 1, d = 1, that line is:ans += (100000 — 1) * (100001 — 1). It seems that my code is correct on this testcase with the ouput of 1333303333500000.
•  » » » » » » 12 months ago, # ^ |   0 Try for this one. But with very large sequence, (1, 1), (1, 2), (1, 3), ... , (2, 1), (3, 1), .....
•  » » » » » » » 12 months ago, # ^ |   0 Thanks!I have figured it out! It is due to the compiler issue. size_t is a typedef for some unsigned integer. It is associated with the platform (see more).So on my computer, it may be 64 unsigned integer. While on codeforces, it may not, which would cause the issue. I resubmitted the same code with c++ 17 (64), and got ac. Addional thanks to nikhil1_raghav
 » 12 months ago, # | ← Rev. 4 →   -10 Nice problems :)))
 » 12 months ago, # |   0 when will the contest ratings be given?
•  » » 12 months ago, # ^ |   0 after the open hacking phase.
•  » » » 12 months ago, # ^ |   0 What is hacking phase , I don't know much about it
•  » » » » 12 months ago, # ^ |   0 It is a 12 hour phase after the contest where you can look at other participants submissions and hack(find a test case where their code might fail). check this for more info
•  » » » 12 months ago, # ^ |   0 sorry for being impatient, but when will the ratings and editorials be updated?
 » 12 months ago, # |   +13 Nothing to say!XD
 » 12 months ago, # | ← Rev. 3 →   0 Why O(Q*(N+M) + N*M) is failing for problem E (TLE on testcase 41 (not included in pretests))? My Code : https://codeforces.com/contest/1598/submission/131480763 Edit : Finally my code was accepted. Replaced vector with pair which brought a major change in execution time (approx 7 times faster). Always try not to use small vectors (if possible). AC Code : https://codeforces.com/contest/1598/submission/131498204
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 Assuming that you are doing a bfs for each query : giving the fact the number of situations is at most (nb of x * nb of y * nb dir = N*M*2), the total complexity of your algorithm is O(N*M*2*Q + N*M) = O(N*M*Q), which is too slow. Sorry for my bad English.
•  » » » 12 months ago, # ^ |   0 No, the time complexity is fine actually because for changing a particular cell you just need to update max O(n+m) cells, not the whole dp table. I had run test case 41 on codeforces and it's taking 3.3 seconds to give the output. The runtime is slow. Can anyone please optimize this code?
•  » » » » 12 months ago, # ^ |   0 Sorry, my bad
•  » » 12 months ago, # ^ |   0 To make your code cleaner, you can use array instead of those pairs, here is the AC code with that modification 131514905
 » 12 months ago, # |   +5 I just came to know that Um_nik was in the 1st place.. I thought that he finished University and I was watching the closing ceremony and thought that this guy behind the mask has a familiar hairstyle and then after googling I got to know that he was our Um_nik. I tagged you because I wanted to congratulate you publicly but without a blog.. Congratulations and wow you are a hardcore person from specialist to red and then ICPC Champion... way to go man I couldn't be a great coder winning contests like you do till now but it's ok coz everyone's life is different.. but it feels good to see an inspiration of hardwork and straight forward man(this i am saying by your blogs and comments) like you at the top.
 » 12 months ago, # |   0 Can somebody give a testcase where this is going wrong
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 try this 1 6 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 
 » 12 months ago, # |   0 For problem C I used double still I think it is overflowing somewhere How can double overflow here.Please help My submission
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 just use (long long) instead of (int) here: cout<
•  » » » 12 months ago, # ^ |   0 Thanks man!!!!
 » 12 months ago, # |   0 the timing is nice but i missed it y 30 mins and shit went wrong
 » 12 months ago, # |   0 when are ratings and editorials updated?
•  » » 12 months ago, # ^ |   0 Patience, my friend. :)
•  » » » 12 months ago, # ^ |   0 lol I thought sys test was done
 » 12 months ago, # |   0 When will the solution be available
 » 12 months ago, # |   0 Please release the editorials and ratings
 » 12 months ago, # | ← Rev. 4 →   0 Does anyone know why the unordered_map solutions to C are resulting in TLE? Is it because of some crafty input which is causing everything in the hash table to be put into single bucket?
•  » » 12 months ago, # ^ |   0 yeah its because of anti hash test case which is causing the unordered map to have a bad hashing
•  » » » 12 months ago, # ^ |   0 That's really interesting. Do you know where I could read more on this or how I could generate such cases?
•  » » » » 12 months ago, # ^ |   +6 yeah you can read about it here, I have also used these techniques to hack 20+ submissions of C
•  » » » » » 12 months ago, # ^ |   0 You learn something new everyday :)
•  » » » » » 12 months ago, # ^ |   0 Thank you!!
•  » » » » » 12 months ago, # ^ |   0 When the editorials and the ratings will be released , do anyone know ?
•  » » » 12 months ago, # ^ |   -12 my question is that is it valid to hack solution on the basis of short coming of unordered hash , should this be concern of the problem . I think its a useless ground to discard out solution specially in problem C
•  » » » 12 months ago, # ^ | ← Rev. 4 →   +8 What about hash map implementations in other languages (say Python dict)? Can they be hacked like this?
 » 12 months ago, # |   -8 Can someone please let me know the problem with my Problem-C solution. It is giving TLE on Test-17. I have used a standard unordered_map based solution, with O(n) complexity as per my understanding.Any help will be appreciated. Thank you !
•  » » 12 months ago, # ^ |   0 Unordered map does not work as efficient as hashing. Technique
•  » » » 12 months ago, # ^ |   0 Is not unordered map == Hashing ?
•  » » » » 12 months ago, # ^ |   -6 Unordered map takes logn for retrieval when the input is not mostly in good manner
•  » » » » » 12 months ago, # ^ |   0 I think you are talking about ordered_map, it has O(log n) retrieval even in worst cases. While unordered (hash map) given a O(1) on average.
•  » » » » » » 12 months ago, # ^ |   0 I have met the same issue before. unordered map may cause hash collision when meets big range number.Then you will get tle.
•  » » » » 12 months ago, # ^ |   +6 unordered map worst time complexity is O(n) , so anti hash test cases has been used to hack unordered map without custom hashing
•  » » » » » 12 months ago, # ^ |   0 Ohh thanks! I thought that it is O(1) so I was preferring an unordered one to get better complexity.
•  » » 12 months ago, # ^ |   0 Notice that unordered_map is a hash table and the complexity is average O(n). I believe that is some input that is causing it to get the worst case complexity which is O(n^2)..
•  » » » 12 months ago, # ^ |   0 So should I prefer ordered_map in future ?
•  » » » » 12 months ago, # ^ |   0 I don't know to be honest. I myself used unordered_map in the contest.. I think that if the log n operations are acceptable we should prefer map since.. Though I think someone more experienced would be able to answer better.
•  » » » » 12 months ago, # ^ |   +12 you can still use an unordered map but with custom hashing ,you can copy paste the template from this blog,because in edu round people have enough time to make anti hash test cases.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +11 Thanks KingRayuga, will keep in mind. I think we can also go with ordered_map as it seems that the time limits are flexible enough to accommodate O(n*logn) solution even when best one is O(n). Please, correct me if I am wrong.
•  » » » » » » 12 months ago, # ^ |   +3 yeah you are right
•  » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 I think instead of using unordered_map we should stick to ordered map because if someone can see your custom hash function then they can make anti-hash cases. Also time difference in case of unordered and ordered is mostly not significant to change verdict of your submission so it is better to just use ordered map.
•  » » » » » » » » 12 months ago, # ^ |   0 Another approach for this problem is to sort and use two pointers.
•  » » 12 months ago, # ^ |   +3 Just read someone else's comment here and tried with ordered map. Solution Accepted !So what should I learn/conclude from here regarding the use of ordered/unordered_map. Like when to prefer ordered_map over unordered (because here I thought using unordered should work, but id didn't eventually).
•  » » » 12 months ago, # ^ |   0 usually ordered_map will be better than unordered_map in codeforces or other problems because there will be testcases that make unordered_map using solutions TLE.
•  » » » 12 months ago, # ^ |   0 Read this blog by neal https://codeforces.com/blog/entry/62393
 » 12 months ago, # |   +1 The test cases used for successful hacks will be included in the main tests?
•  » » 12 months ago, # ^ |   +1 Yeah they are
 » 12 months ago, # |   +3 Probably not relevant to the blog but I have a solution which I think would work for non-distinct pairs for D. Would anyone like to test it out or perhaps reply with a solution of their own which also works for non-distinct pairs.Here's my submissionhttps://codeforces.com/contest/1598/submission/131482336
 » 12 months ago, # |   0 same solution using unoreded_map is tle (after hack) but using map is accepted.I used unordered_map in contest
•  » » 12 months ago, # ^ |   0 Unordered map implementation- 131448620Ordered Map implementation- 131510925
•  » » 12 months ago, # ^ |   +5 I think it can help you to solve your problems: https://codeforces.com/blog/entry/62393
•  » » » 12 months ago, # ^ |   0 Had I known this earlier...
 » 12 months ago, # |   +17 When will the ratings change?
 » 12 months ago, # |   0 How to solve problem F? I have been thinking for a long time but still have no ideas. Can anyone tell me the idea of this problem? Thx.
•  » » 12 months ago, # ^ |   +1 HintIt's a standard bitmask dp. The most difficult part is speeding up the transitions.
•  » » » 12 months ago, # ^ |   0 Thx.
 » 12 months ago, # |   0 Help NeededMy solution for the 3rd question 'Delete Two Elements' got hacked recently. I wrote an O(N) solution which should ideally run within the time constraints but it gave TLE on the hacked test case. Some other solutions which also run on O(N) are accepted. Can anyone tell me the reason for TLE despite the solution being O(N)?Solution Link: https://codeforces.com/contest/1598/submission/131422916
•  » » 12 months ago, # ^ |   0 Use map instead of unordered_map or you can use custom hash for unordered_map. You can go through this blog. I hope it helps.
•  » » » 12 months ago, # ^ |   0 Thanks a lot! Never knew about this concept :-(
 » 12 months ago, # |   +12 Why ratings change taking so long?
•  » » 12 months ago, # ^ |   +8 I guess because the time of the contest, when the hacking phase finished the timing was too late for Mike (Just a guess) :D
•  » » 12 months ago, # ^ |   +8 yes editorial was also late
•  » » » 12 months ago, # ^ |   0 Where is the editorial? I could not find it. Please share it here. Thanks.
 » 12 months ago, # |   +3 Rating change is taking longer than I thought!!!
•  » » 12 months ago, # ^ |   -8 I think it's because the unusual time of this round, but also, I have to say that the rating change of this round is the longest I have waited...
 » 12 months ago, # |   0 when does system testing starts?
•  » » 12 months ago, # ^ |   0 I remember it has been finished already in the past few hours.
•  » » » 12 months ago, # ^ |   0 No, System testing is not finished yet.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 You are right.It is still running now.But it is the second time for system testing.I wonder why it takes.
•  » » » » 12 months ago, # ^ |   +8 Why does the system testing run twice?
•  » » 12 months ago, # ^ |   0 But the rating didn't change yet.Maybe the technicians met some problems.
 » 12 months ago, # |   +13 MikeMirzayanov please remove the cheaters and update the ratings thanks !
•  » » 12 months ago, # ^ |   +10 why the systetm testing is caried out multiple times. is this for rejudging with additional testcases.?
 » 12 months ago, # | ← Rev. 2 →   0
 » 12 months ago, # |   0 why system testing is done so many times ?
•  » » 12 months ago, #