By Vladosiya, history, 2 months ago, translation,

Hello! Codeforces Round 847 (Div. 3) will start at Jan/27/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, DmitriyOwlet and Vladosiya. Also this time, molney suggested one of the tasks.

We would like to thank: alwyn, morasha3, csegura, BledDest, stevenkplus, Darko, Coki628, Crutch, Qwerty1232, Jostic11, liouzhou_101, Jeffin, AW_Flister, glebustim, yorky, mango_lassi, 74TrAkToR, ErrorDeveloper, Be_dos, MODDI, Vercingetorix for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

• +202

 » 2 months ago, # |   +18 Hoping for the first time getting AK (solve all problems) in this contest.
•  » » 2 months ago, # ^ |   +58 Hoping for 6-8 NP-hard and NP-complete problems :D
•  » » » 2 months ago, # ^ |   0 Yes div. 3 round thank everyone
•  » » 2 months ago, # ^ |   0 All the best !!
•  » » 2 months ago, # ^ |   +5 Congo
•  » » 2 months ago, # ^ |   +8 Congrats
•  » » 2 months ago, # ^ |   0 Why has system testing not started yet!!!
 » 2 months ago, # |   0 The date in the blog needs correction i guess.
 » 2 months ago, # |   0 I just hope this round doesn't become unrated and no hearts are broken ;)
•  » » 2 months ago, # ^ |   0 Hoping +ve delta for every participant.
•  » » » 2 months ago, # ^ |   0 -ve delta teaches more than +ve if you want to grow.
•  » » » » 2 months ago, # ^ |   +3 Yes you are also right. But if somebody already have rating < 900, how can he be happy with getting more -ve delta.
•  » » » 2 months ago, # ^ |   0 You know that's impossible right ?
 » 2 months ago, # |   0 Hopefully there will be no error like the yesterday contest
 » 2 months ago, # |   +2 BTW the kitty in the Vladosiya's profile is very cute (◠‿◠)
•  » » 2 months ago, # ^ |   +8 It is Vladosiya
 » 2 months ago, # | ← Rev. 3 →   +5 Iam new here and I didn't get the meaning of "penalty for the wrong submission in this round is 10 minutes", can anyone explain? .. Thanks in advance
•  » » 2 months ago, # ^ | ← Rev. 2 →   -32 Sorry, I am unaware of this.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +8 No. In div3, div4 and education rounds, contestants are ranked by the lexicographic order of (count of problems you've solved, (-1)*sum of the minutes after the contest begins of your accepted solutions), and every wrong submission you submitted (before the correct one) will let the second term -10.
•  » » » 2 months ago, # ^ |   -9 Stupid :}
•  » » 2 months ago, # ^ |   +6 If you make a mistake, then 10 penalties are added to your total penalty.
•  » » 2 months ago, # ^ |   +2 hey guys give me negative vote I want to be the 1st of the worst Contributer
•  » » » 2 months ago, # ^ |   -8 no one can beat me!I am all thw ay down.
 » 2 months ago, # |   0 hoping to be Expert on this contest... Wish me Luck ... xD
•  » » 2 months ago, # ^ |   0 if you try, you will become an expert and without luck
•  » » 2 months ago, # ^ |   0 Some have the privilege of falling to expert, and some don't.
•  » » 2 months ago, # ^ |   0 Good Luck Buddy ..
 » 2 months ago, # |   0 What if I can't solve at least 3 problems?
•  » » 2 months ago, # ^ |   0 There nothing wrong as long as you not give up trying.
•  » » » 2 months ago, # ^ |   0 thanks for the advice
 » 2 months ago, # |   +7 As a tester, tested.
•  » » 2 months ago, # ^ |   0 Hopefully it will be rated round. And all problems are not Np hard .
•  » » 2 months ago, # ^ |   -8 As a participant,participated.
 » 2 months ago, # |   0 is it possible to getting everyone positive ratting?
•  » » 2 months ago, # ^ |   +5 The total delta of every contestants will definitely be negative due to the algorithm of codeforces. However, there are many new accounts (or alt accounts) which participate in contests with 0~1 problem solved, each of them bring +1400 rating to the total rating of CF users (by the first 6 contests they take), which makes the total rating of active CF users being balanced.
•  » » » 2 months ago, # ^ |   0 Hey, bro, seems like you know everything about the rules, where did you get it?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0
 » 2 months ago, # |   0 Hoping to get some positive delta guys!
 » 2 months ago, # |   0 Very nice new rules for Div3 contests
•  » » 2 months ago, # ^ |   +5 what do you mean by new rules ??
 » 2 months ago, # |   0 Hope to solve at least 5-6 problems
 » 2 months ago, # |   +1 omg blue round
 » 2 months ago, # |   0 Hoping to remain specialist:)
•  » » 2 months ago, # ^ |   +3 Hoping for you to be an expert :)
 » 2 months ago, # |   +4 Is it easier to increase rating in div3 than div 2 considering I am a specialist?
•  » » 2 months ago, # ^ |   +9 Yeah, because mostly you will be on the top of the ranking list so codeforces favours those who are top in the scoreboard. But you might fall hard if you can't solve according to your rating as you should do as a specialist.
 » 2 months ago, # |   0 Finally, my time to shine
 » 2 months ago, # |   0 I have a question that usually I only need to take part in at least two rated rounds, but why this time I have to take part in at least five rated rounds? I'm very frustrated because I had only taken part in four:(
•  » » 2 months ago, # ^ |   +5 Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.Since you are green, you don't need to worry about it.
 » 2 months ago, # |   0 Anyone from Bangladesh (class 10 or lower)?
 » 2 months ago, # |   -7 ChatGPT here, participating in this Round ^^ This will be Fun.
•  » » 2 months ago, # ^ |   +1 I bet, you wont get single question right,,, if you are using only CHAT GPT, and no Human logic/intelligence ...
•  » » » 2 months ago, # ^ |   -6 will be using only CHAT GPT here, + very minor fix of the code if needed (missing include, output formatting, etc..) Let's see :) :)
•  » » » 2 months ago, # ^ |   0 First rated Round for ChatGPT, succeeded to solve problem A. Good start?
•  » » » » 2 months ago, # ^ |   0 sure, good one...
 » 2 months ago, # |   0 My Turn ...... :)
 » 2 months ago, # |   0 Can someone suggest me some topics which are most common and helpful under problem ratings from 1200 to 1500?
•  » » 2 months ago, # ^ |   0 number theory, greedy, implementation, constructive algorithms :)
•  » » » 2 months ago, # ^ |   0 Thanks!
•  » » 2 months ago, # ^ |   0 include binary search, two pointers, interactive as well
 » 2 months ago, # |   0 OMG I am very exited, I wish to you positive delta!!
 » 2 months ago, # |   0 Hoping to be specialist :) There are only 4 ratings to go Don't let me down pls :)
 » 2 months ago, # |   0 I have been wait many days for div-3 contest. This is my entering contest on codeforces.
 » 2 months ago, # |   0 I can just solve 2 problems in Div.2, hope in Div.3 I can solve more
 » 2 months ago, # |   +3 Please no NP-hard problems. Please no NP-hard problems. :D
 » 2 months ago, # |   0 I wish there were more Div.3 rounds as they've decreased nowadays.Excited for this one!!
 » 2 months ago, # |   +8 Can't wait to see hmzqaq's performance in this round. (He's duck_pear)
 » 2 months ago, # |   0 first unrated div3 contest for me..........it's unbelivable :)
•  » » 2 months ago, # ^ |   +3 Cheers buddy
•  » » » 2 months ago, # ^ |   0 Thnx :)
 » 2 months ago, # |   +5 Hoping to be a specialist... Wish me good luck.
•  » » 2 months ago, # ^ |   0 Well, it seems that I failed... :(
 » 2 months ago, # |   +5 Hopefully I can reach expert
 » 2 months ago, # | ← Rev. 2 →   0 Either my Code is Wrong or Something Else PROBLEM=B,Verdict: WRONG_ANSWER Input 7, 2 2 1, 2 4 2, 4 9 5, 5 17 11, 3 15 10, 4 4 3, 5 20 15, Participant's output 1 1, 2 2, 1 1 3 4, 2 2 2 5 6, 5 5 5, 1 1 1 1, 3 3 3 6 5, Checker comment wrong answer wrong r: 15 expected, 14 found (test case 7)
•  » » 2 months ago, # ^ |   0 Im getting same if i output the same thing
•  » » 2 months ago, # ^ |   0 I'm getting something similar, on test case 5, my sequence sums up to 15. But it's getting wrong answer r: 10 expected, 9 found
•  » » 2 months ago, # ^ |   0 Not a bug, actually. Just can't tell why it's happening during contest, but it's not a bug. The best I can do is to advice reading the statement carefully.
•  » » » 2 months ago, # ^ |   0 shit,, thanks
•  » » » 2 months ago, # ^ |   0 Got, It Thanks Bro
•  » » » 2 months ago, # ^ |   0 You were right. I reread it, made one slight change on an if statement, got AC.
 » 2 months ago, # | ← Rev. 2 →   +4 A channel is providing solutions in youtube live during contest. This is not fair. The round should be unrated.
•  » » 2 months ago, # ^ |   0 I think this comment should be removed asap so less people will see the link.
•  » » 2 months ago, # ^ |   +2 The same things had happened in some of the div2 contests before directly. However, those contests were rated too. So I thought it would be better to ignore them and just remove cheaters afterwards instead of making the whole contest unrated.
•  » » » 2 months ago, # ^ |   0 How will you determine the cheater if he didn't copy the code but only copy the idea behind the implementation?
•  » » » » 2 months ago, # ^ |   +1 so you saying that more than thousand people that write it fair won get their delta because of one man?
•  » » 2 months ago, # ^ |   0 it's much more unfair to make it unrated, because most of the people solved the problems on their own.
•  » » 2 months ago, # ^ |   0 Was it in your youtube feed?
 » 2 months ago, # | ← Rev. 2 →   +13 This contest is a little hard but quite interesting comparing with other div3 contests. Thanks for the authors' and testers' hard working!
•  » » 2 months ago, # ^ |   0 lmao this was probably the easiest div3 in a long time since most div3 participants only solve till D/E
 » 2 months ago, # |   -25 Wtf this is not Div. 3
•  » » 2 months ago, # ^ |   +7 Sir Please be respectful here. Don't use those hard word. ~~~~~ I am sure you can express yourself even without those slang. ~~~~~
•  » » » 2 months ago, # ^ |   0 and you (both of you) please go back to solving tasks?
•  » » » » 2 months ago, # ^ |   0 Bro F is out of my league. I have already solved till E within 50min. Waiting for editorial for elegant solution of F.
•  » » 2 months ago, # ^ |   0 4000 + submissions of E, and you say its not div3
 » 2 months ago, # | ← Rev. 2 →   +30
•  » » 2 months ago, # ^ |   +5 it's actually F just copy the code centroid on internet and done-.-
•  » » » 2 months ago, # ^ |   0 do you mean centroid decomposition?
•  » » » » 2 months ago, # ^ |   0 It is
•  » » » 2 months ago, # ^ |   0 nah, u could think 2 minutes longer and make it in O(n) easily
 » 2 months ago, # | ← Rev. 3 →   -16 MikeMirzayanovSomeone with codeforces handle demons_paw is providing solutions of Codeforces Round 847 (Div. 3) Codeforces Round #847 (Div. 3) in youtube live during contest. This is not fair. The round should be unrated. I have sent the youtube live video link in your codeforces inbox. Edited**
•  » » 2 months ago, # ^ |   +16 Why do you share this in a public discussion post during a contest ? At least should wait until it’s over
•  » » » 2 months ago, # ^ |   -12 I think, there is a possibility that the youtuber can delete the live video at the end of the contest.
•  » » » » 2 months ago, # ^ |   +4 By the way, now you really should edit the comment and delete the link so that no one else can use it
•  » » 2 months ago, # ^ |   +28 Thank you, we've already seen it and we're really upset about it.Please don't cheat on the rounds! Firstly, it is forbidden. Secondly, it won't help you develop your competitive programming skills at all :(
•  » » 2 months ago, # ^ |   0 Was it in your youtube feed?
 » 2 months ago, # |   +6 Finally I was able to use first 31 digits of pi from my template :D
•  » » 2 months ago, # ^ |   +5 first 30 digits were given in sample cases
•  » » » 2 months ago, # ^ |   0 Didn't notice lol
 » 2 months ago, # |   0 problem f is really one of the best i really like it
 » 2 months ago, # | ← Rev. 2 →   +4 Me after solving A,B,C,D,E
 » 2 months ago, # |   +6 Who else can remember PI without searching the google =)))) BTW, I really love all of the problems
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 you don't have to remember pi, neither do you have to google for solving that problem. That's why I liked the problem (hint: look at the testcases)
•  » » 2 months ago, # ^ |   +1 you could just copy pi digits from the sample input xD
 » 2 months ago, # |   0 "OR" really confused me :(
 » 2 months ago, # |   +44 Problem G was worded very badly in English :notlikeblob: I wasted about 20 minutes just trying to understand the problem (the statement is much better now). Using terms like move / jump / turn interchangeably was just confusing, surprised this wasn't picked up in testing.Even after I solved the problem, I had zero clue what this meant: "The same bonus can be used an unlimited number of times, but not more than once per turn."?????Oh well, still got 8th place :sunglasses: Screencast + editorial at https://www.youtube.com/watch?v=fVaNJ2eTegw&ab_channel=JoshuaChen :)
 » 2 months ago, # |   +3 Problem A: The observant programmer might have noticed that one of the test cases included all 30 digits of pi for a quick copy and pasteProblem B: I spent more time deciding what the best way to implement would be than if I had just picked the slowest way and started writing it immediatelyProblem C: Neat problem, interesting observation that the answer can be deduced from just the first 3 permutations and all of the other ones are irrelevant. Spent 30 minutes debugging poor code though.Problem D: Standard frequency map problemProblem E: A little disappointing that the solution was readily available on Geeks For Geeks, pretty sure most people just pasted the algorithm because it's allowed.Didn't have time to solve F or G but F looked interesting.
•  » » 2 months ago, # ^ |   0 how to solve E
•  » » » 2 months ago, # ^ |   0 I literally don't know. Copy and paste this. https://www.geeksforgeeks.org/find-two-numbers-sum-xor/
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 can you explane why 5 is -1?x = 5a = 5b = 5a OR b = 5(a+b)/2 = 5
•  » » » » » 2 months ago, # ^ |   0 It is XOR not OR
•  » » » » » » 2 months ago, # ^ |   0
•  » » » » » » » 2 months ago, # ^ |   +6 Exclusive OR = XOR, if you click the link it redirects to wikipedia XOR article https://en.wikipedia.org/wiki/Bitwise_operation#XOR
•  » » » » » » » » 2 months ago, # ^ |   +3 oh my badthank you so much :)
•  » » » » » » » 2 months ago, # ^ |   +3 Honestly I would think that means OR too but I am familiar with the XOR operator symbol ⊕
•  » » » 2 months ago, # ^ |   0 a+b is even as per the question so , if x = a xor b then x is bound to be even, since at a time both a and b can either be odd or even. Consider the bit positions where x is set, we are sure that for those bit positions only a is set or b is set. so for those bit positions say i; a[i]+b[i] = x[i]; the sum of those bit positions is x itself. let us call this sum as setSum. We know 2*x = a+b, then the sum of bit positions where a[i]==b[i] or x[i]=0 is 2*x-setSum is equal to x itself. let us call this sum as the otherSum. otherSum is equally distributed b/w a and b, so a and b will get equal share of otherSum/2. let us call this as Add. for any set bit position i of Add, x must not be set (because these are the bit positions where a[i]==b[i]) so if( x&(Add)!=0) solution is not possible. Hence one can give an easy answer to this as a= add, b = x+add or a = x/2, b = x+x/2 (giving all setSum to b only)
•  » » 2 months ago, # ^ |   0 was able to find solution to C in first glance but got stuck at implementation and spent whole time debugging to find out that .resize() doesn't works if called multiple times within another loop, the solution got accepted just after the contest got over :/ My solution for C -https://codeforces.com/contest/1790/submission/190877527
•  » » » 2 months ago, # ^ | ← Rev. 5 →   0 You are almost reach the most elegant answer to Problem C. All you need to do is just figure out the first element of the original permutation and combine it with the new permutation that does not have the first element.
•  » » » » 2 months ago, # ^ |   0 i have shared above the accepted solution i did it using frequency array maintaining the highest count of an element in a column and that will be the number pi for the ith position. did same from the back using 'j'
•  » » » » 2 months ago, # ^ |   0 how do improve in these type of questions/observations?
•  » » » » » 2 months ago, # ^ |   0 practice
 » 2 months ago, # |   0 Do we have to solve problem E using recursion?
•  » » 2 months ago, # ^ | ← Rev. 3 →   -11 No. You just need to check if x is even and if (x + x/2) ^ (x/2) is equal to x. If both conditions are true, print x+x/2 and x/2 else -1.
•  » » » 2 months ago, # ^ |   0 How did you think of this?
•  » » » » 2 months ago, # ^ |   -7 Noticed that in examples a and b are equal to x +- some number. Found such numbers using bruteforce for x in [1, 256] and found out that there is either no solution or at least one solution with x+-x/2.
•  » » » 2 months ago, # ^ |   0 Seems like checking if ( x & 1 || x & x >> 1 ) is false works too.
•  » » » 2 months ago, # ^ |   +1 Wow. People hate this comment so much :/
•  » » » » 2 months ago, # ^ |   0 Did you hack your own solution PURPOSELY? What's the logic behind it?
•  » » » » » 2 months ago, # ^ |   0 To be honest, there is not that much logic behind that. Was wondering, what would happen, and desided to try this dumb idea out...
 » 2 months ago, # |   0 How to prove D?
•  » » 2 months ago, # ^ |   0 Obviously if we have multiple of the same number we must start a new doll. And it also optimal to continue the streak of a previous doll if we have one. So greedy covers both cases.
•  » » » 2 months ago, # ^ |   0 u proved nothing
•  » » 2 months ago, # ^ |   0 A new sack has to be started for number i if there is no number i-1 available before it. We can use a frequency map to tell if i-1 is still available and reduce 1 from f[i-1], or open a new sack if it is not. This would minimize the number of sacks, as only numbers with a value of i+1 can follow behind numbers with a value of i.
•  » » 2 months ago, # ^ |   0 starting the set from smallest doll, we will take elements in set until current+1 is not present in array.{current is initialized with smallest doll value}. Example :- (1,1,2,3,3) starting from 1 we will take 2 and 3 now array/Map contains (1,3) Again starting from 1 we can take 1 only(as 2 is not present) Now we will start from 3 as the smallest element present is 3 Thereby 3 sets will be required intotal
 » 2 months ago, # |   0 how's D done anybody ?
•  » » 2 months ago, # ^ |   0 Sort the array and put each element into a frequency map. If freq[a[i]-1] == 0, increment answer by 1. Else, freq[a[i]-1] -= 1, because it can no longer be used. Then freq[a[i]] += 1 because it can be used for a bigger doll.
 » 2 months ago, # |   +11 F was the same as: https://codeforces.com/problemset/problem/342/E
 » 2 months ago, # |   -25 speedforces
 » 2 months ago, # |   0
 » 2 months ago, # |   +6 This problem 342E. Xenia and Tree is almost similar to today's problem F :)
•  » » 2 months ago, # ^ |   0 :(
 » 2 months ago, # | ← Rev. 3 →   0 Is there any wrong in my B? I output $s-r$, $\lceil r/{(n-1)}\rceil$ n-2 times and $r-(n-1)*\lceil r/{(n-1)}\rceil$. I have no idea why it is wrong.
•  » » 2 months ago, # ^ |   0 I was trying to find an elegant way to have n dice sum into the desired sum, and I settled on initializing an array with all 1's then replacing as many as I could with the max allowed dice number, then replacing the final 1 with the remainder.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 There is a chance that s-r would be smaller than r−(n−1)∗⌈r/(n−1)⌉ (the dice with largest num will be taken) . You have to reduce that last number by distributing to elements other than s-r until it is smaller or equal to s-r.
 » 2 months ago, # |   0 Lol, first tournament I have answered something. :)
•  » » 2 months ago, # ^ |   0 Good job!)
•  » » 2 months ago, # ^ |   0 Me also
•  » » 2 months ago, # ^ |   0 Good job!
 » 2 months ago, # |   +7 How to do Problem F?? I thought of an approach of applying bfs every time I make a node black (bfs from ith node in array c) and whenever I reach a node which is already black I make my mini variable (which stores the min result till now) to be the min of previous mini and level of this bfs which took me to a black node Why I think this should run!! lets say in worst case scenerio I have a linked list type tree then ttou can easily observe that you would take atmax n bfs steps to identify the first black guy then for the second time you would only take atmax n/2 and similarly next time n/4 .... which leads us to a very simple series sum n+n/2+n/4+n/6+....+n/n which I thought would work within the given time limit Also whenever my mini becomes 1 then I am simply breaking out and puuting all my ramaining answers to be 1 only This apporach gave a TLE on test case 18 :(can anyone please tell me what must be wrong in my approach PS:- Sorry for the spelling mistakes if any :)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 The worst case scenario is a snowflake with sqrt(n) tails, every tail has sqrt(n) vertices and first sqrt(n) black guys are ends of a tail. The first sqrt(n) bfs will take n steps, so in worst case this algorithm has time complexity o(n^(3\2)). I think, that in this problem you must use LCA instead of BFS to find distances between the vertices
•  » » » 2 months ago, # ^ |   +3 Ohh Now I understood why it was giving TLE I got frustrated in the contest as I couldn't think of this worst case scenerio Thanks a lot man!
•  » » » » 2 months ago, # ^ |   0 what is wrong with O(n^1.5)? Are we supposed to do better than this? I am running TLE on test 18 also.
•  » » » » » 2 months ago, # ^ |   0 It would pass I guess But in my case I was using set instead of visited array (as array construction would take n time which would definitely give TLE) but since I was using set it would add extra complexity so I guess due to that it's giving TLE. I am just unable to think how to keep track of visited nodes within time limit as I want a new visited set or array for every ci.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Did you AC at the end?My idea is to go through each black node and do a dfs up to answer steps, (answer is the min distant so far) and see if I can find another black node that is closer than answer. If I find one, update answer so that next time we can dfs less depth. However, this will tle at test case 18. I thought the time complexity is O(n^1.5), but clearly this will TLE. Appreciate if anyone can help me understand why.My submission 190916688
 » 2 months ago, # |   0 Any hint for F?
•  » » 2 months ago, # ^ |   0 you can dfs to update the minimum dis of every white nodes to the nearest black node, and we need to set the maximum dfs dep to the curr ans.Or just spam Centroid (it's very similar to this problem 342E
 » 2 months ago, # |   +16 Let us not mention the fact, that tasks E and F are very well-known, what is a purpose of giving task A?Tasks B C D G were great though.
•  » » 2 months ago, # ^ |   +10 Is F well known coz it is repeated? Or the concept well known as well? Hints also pls :D
•  » » » 2 months ago, # ^ |   -8 This task can be solved with centroid decomposition. If you are using it, you can just follow some well-known approach.I wasn't participating the round, but it seems to me that this task is solvable by DSU. If we will suppose that there can't be two adjacent black nodes, then if you will treat black nodes as deleted, the answer is the size of minimal component plus one. However I'm not sure this will work. But the fact that the task can be solved with centroid decomposition using some well-known approach makes this task well-known and thus not suitable for the round.
•  » » 2 months ago, # ^ |   0 I am wondering how you tell your opinion about the problems without participating in the round, I think something is sus here
•  » » » 2 months ago, # ^ |   +10 See, I'm a master, and I can read the tasks, think a little bit and come up with a solution :)
•  » » » » 2 months ago, # ^ |   0 Well not all the master think like you, I hope you're right ...
•  » » 2 months ago, # ^ |   +15 I really liked A because instead of calculating the value of pi upto 30 places or searching it on the internet , i for a moment looked at the samples and found the asnwer's is already there and tbh it made me chuckle a bit and i started rest of the contest with smile. i don't know it's purpose and but yeah that's how it made me feel!
 » 2 months ago, # | ← Rev. 2 →   0 My solutions for the first four problems:Problem A: SpoilerWe can create a string with the first digits of PI, and iterate over it with a counter, stopping the loop if a mismatch happens.Problem B: SpoilerDifference between $s$ and $r$ is obviously one of the dice elements, for the rest we can create a vector of $n-1$ elements and increase each element while decrementing $s$. If $s$ reaches $0$ we can exit, print $s-r$ and the $n-1$ elements.Problem C: SpoilerWe can maintain an array of $n$ elements that holds our guesses. For each of the $n-1$ vectors we check the position of the $nth$ element, if it is higher than our guess we increase it to it's position, since the highest position it will reach will be it's true position, this is easy to see since for each element except the last there will be a vector where all the elements before it are present. In the end we will be left with $2$ elements with the same position of $n-1$, we will take the one with the highest frequency to be the last element, since it is the last, it will always appear in the end except for the case where it isn't present.Problem D: SpoilerWe maintain an ordered frequency map, we will iterate over that map, if the difference between the $ith$ element and the $i+1th$ element is more than 1 then we know there was a disconnect and we add the frequency of $i+1th$ element. else if the frequency of the element increased, then we know that sets were added and we add that increase in frequency,
•  » » 2 months ago, # ^ |   0 E is a bit of a well known problem. We are trying to get two elements with sum of $2n$ and xor of $n$, you will find plenty of code snippets for it or finding two elements with xor $x$ and sum $y$ in general.
•  » » 2 months ago, # ^ |   0 Could D be solved this way but counting decreasing values instead of increasing?
•  » » » 2 months ago, # ^ |   0 Not sure if I am understanding correctly but I assume you are talking about the case that they are continuous sizes and we saw a decrease in the frequency. say {2,2}, {3,2}, {4,1}. In this case we can't really make a guess about the number of sets, since we are trying to minimize a decrease in frequency would be interpreted as one/several of the sets ending. The answer here would be 2 sets, {2,3,4} and {2,3}.
 » 2 months ago, # |   0 Can some one explain me how were the rules of the game for problem G?I didn't understand the problem statement :(
 » 2 months ago, # |   0 hi im new here, is this rated or unrated cuz i wanna get a rating but when i click on my profile it says that this contest is unrated, but in this announcement it says its rated, thanks :)
•  » » 2 months ago, # ^ |   0 All contests will be shown as unrated until the rating update is calculated.
•  » » » 2 months ago, # ^ |   0 oo okay thanks a lot
 » 2 months ago, # |   0 First time solve 4 problem in div 3.Thanks every problem setter.
 » 2 months ago, # |   0 Is there any issue in copying the given sample testcases to clipboard, in Problem G?
 » 2 months ago, # | ← Rev. 2 →   +3 Problem F is similar(same) to 342E - Xenia and Tree! I would like to ask why to give a Centroid Decomposition problem in Div3 round? (it's for < 1600 people) is it expected from them to know Centroid Decomposition??
•  » » 2 months ago, # ^ |   +29 Cause this problem can be solved without centroid decomposition. Don't assume your way is the only way to solve a problem.
•  » » 2 months ago, # ^ |   0 I spend way too much time reading random CF blogs and immediately thought of centroid decomposition because there was a recent action on a blog about it. But I've never even experimented with the algorithm so I didn't even try to solve it with my remaining time.
•  » » 2 months ago, # ^ |   +1 We can solve this problem by DFS with maximum depth set to the current answer. I passed it without centroid decomposition.
•  » » » 2 months ago, # ^ |   0 Is this n log n? Because if the black vertices were adversarially chosen then they have to be at least at the half way distance between two other black vertices?
•  » » » » 2 months ago, # ^ |   +6 Although I can't prove it I think so. IMO the worst situation of my solution is: The graph is a chain with 2^n+1 nodes, and black nodes are added by the order (0, 2^n, 2^(n-1), 2^(n-2), 3*2^(n-2), …) where time complexity is O(n*log(n)).
•  » » » » » 2 months ago, # ^ |   +30 Unless I am misunderstanding your solution, the complexity is at best $O(n \sqrt n)$. Consider a set of paths of lengths $b, b+1, \dots, 2b$ merging at a single vertex, and $O(n)$ leaves connected at that single vertex. The vertices at the ends of the paths turn black one by one, starting from the longest path. For the first $O(\sqrt{n})$ vertices that turn black, every leaf adjacent to the path merging point is visited, thus at least $O(n \sqrt{n})$ vertices are visited in total.
•  » » » » » » 2 months ago, # ^ |   0 Enlightening example, thanks
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 What is the number of edges in this case? I think the complexity is O(min(m, n*sqrt(n)))upd: ...My comments above is wrong, I was thinking, for each node, there should be a value stored indicating the nearest black node, If that information is maintained, not necessarily accurate but should be accurate if the value is smaller than current result, then for this test case, bfs should stop when reach the 'root', the complexity is O(m).
•  » » » » » » 2 months ago, # ^ |   0 I tried solving F using bfs with some optimization, but got TLE on test case 20, can you or anyone please help with what is the time complexity of my solution, and why it's failing. 190874842
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 can you please explain that how is the complexity O(n√n)? I am not able to understand ur previous answer?
•  » » 2 months ago, # ^ |   +17 We solved it without centroids (didn't even think about it), so we decided it would be just a great task.
 » 2 months ago, # |   0 Had solved all problems in a Div 4 earlier, today solved all problems in Div 3.
 » 2 months ago, # |   0 Can someone please look at my profile and suggest what's happening? I really don't know. Thank You.
 » 2 months ago, # | ← Rev. 4 →   +10 All problems solved (if no FST).A: Ctrl+C the last line of the example and Ctrl+V to the code.B: Do division with remainder for r and n-1.C: For numbers with initial position i in range [1,n-1], the position after remove a number will be i or i-1. If i==n, the position after remove will be only i-1. Therefore by count the miminum and maximum position of numbers in each permutations after removal, we can find their initial position.D: Greedy. Always remove a maximal equidistant sequence with common distance 1. But we need implement this solution by an ordered map. We count the time of occurence of each number and store them in a map, and for each adjacent key-value pair [k1,v1] and [k2,v2], if k1+1==k2 we add max(v2-v1,0) to answer (because we can extend some sequences containing k1 to k2), if k1+1=2 such token, we can move them alternately to node 1. If there's exactly 1 token, we need to check if there's other movable token and how many times we can move them. We need to check for every edge (u,v), if u, v are both bonus nodes, mark them as "infinite move". Then for each tokens we check if they have any adjacent bonus node. Therefore, the final condition is: there's some other node adjacent to an "infinite move" bonus node, or the number of movable token (except the one can reach node 1) >= (the distance of the reachable token to node 1)-1.
•  » » 2 months ago, # ^ |   0 You can do F with centroid decomposition.
•  » » 2 months ago, # ^ |   0 Missed the last condition in G
•  » » 2 months ago, # ^ |   0 Do you know exact proof for D? thanks
•  » » 2 months ago, # ^ | ← Rev. 2 →   -8 Here's this bizarre solution for E I found right after the contest ended (I solved it the same method with yours in contest). Just try $(\lfloor n/2 \rfloor, \lceil 3n/2 \rceil)$, if their XOR is $n$, then that is the solution. else, -1. I don't understand why this approach works, but it seems like it does.Also, here's a very elegant solution for C, which I came up with because I didn't want to do make implementation a rigorous job. Basically, just sort by sums of indices. Submission goes to 190790499.
•  » » » 2 months ago, # ^ |   0 That's what tourist has done
•  » » » » 2 months ago, # ^ |   -8 Yep, I just saw. Doesn't change the fact that I found the method by myself, though. Let's just say that we both found it independently.
•  » » » 2 months ago, # ^ |   0 I found this during the contest, but forgot to check if their XOR is $n$.
•  » » » 2 months ago, # ^ |   0 x^y=x+y-2*x&y, this is why that solution works
•  » » 2 months ago, # ^ |   0 Can you explain your dfs solution a little more?
•  » » » 2 months ago, # ^ | ← Rev. 5 →   -16 The answer decreases on every step, and this rate of descent is very quick. For a worst case, lets say, the first two colored nodes are on the diameter of the tree, and the third colored node is on a centroid. You can see that now the answer is halved. So even on the worst case, we will use an average $O(n \log n)$ time complexity in total. If we consider every worst case (such as an "f$%&ed up star", a term I just came up with, which is like a star but there are $O(\sqrt n)$ paths with length $O(\sqrt n)$), the worst case will probably be $O(n \sqrt n)$. Definitely not $O(n^2)$, though.UPD: actually I am pretty sure it's $O(n \sqrt n)$ or better even in the worst case, that "f$%&ed up star" in fact starts to get towards $O(n \log n)$ after $O(\sqrt n)$ steps, $O(n)$ each step.
•  » » 2 months ago, # ^ |   0 I used the same logic for G but it gives wrong answer on testcase 5,i've spent two hours trying o decode but can't find it. here's my solution- https://codeforces.com/contest/1790/submission/190884446 any help is highly appreciated.
•  » » » 2 months ago, # ^ |   +1 Try to add vis[v]=true after q.push[v].My first wrong submission also made this mistake, which caused distance was calculated incorrectly.
•  » » » » 2 months ago, # ^ |   +10 Thanks YocyCraft. My profile pic and face looks same after this silly mistake.
•  » » 2 months ago, # ^ |   0 I use the similar idea for F (i.e. limiting the distance by using current answer for traversal) but using BFS to implement it but got TLE in case 18. Any idea what's the catch?
•  » » 2 months ago, # ^ |   0 (a^b)+2*(a&b)=a+b Where did everyone get this formula from, how does it work out. Explain, thank you.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 (a^b)=(a|b)-(a&b) by the definition of xor(a|b)=(a+b)-(a&b) by the inclusion-exclusion principle
 » 2 months ago, # |   0 This is my solution for F , it keeps getting TLE on test1 and i don't have a damn clue why:( can any one tell ?190880017
•  » » 2 months ago, # ^ |   0 in the init function, the declaration is wrong. you need to specify the type.
 » 2 months ago, # |   0 How to solve E(with proof)?
•  » » 2 months ago, # ^ |   +3 We know that, a+b = a^b + 2*(a&b) here a^b is given let say it is x, and sum is given as 2x so, 2x = x + 2*(a&b) =>  a&b = x/2 , so all bits of x/2 should be there in both a and b, and x should be even, if odd then answer is not possibleso, both a and b are atleast equal to x/2.now bits of x should not be present in both a and b otherwise it will not be present in their xor which is x, so x^(x/2) must be 0, if not then ans is not possible else we can add x to any of them and answer would be 3x/2 and x/2 190824234
•  » » » 2 months ago, # ^ |   0 Where do you learn things like a+b = a^b + 2*(a&b)? I never seen it in my life
•  » » » » 2 months ago, # ^ |   0 You can read about bitwise math properties or you can discover them through problems
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 well. my solution is bit complicated i guess but1) it's not hard to prove that a+b = (a^b)+2(a&b) (consider 4 cases when ith bits are (0,0), (0,1), (1,0) and (1,1) and check that this statement is true)2)by definition a+b = 2*(a^b) => a^b = 2(a&b). 2.1) it's not hard to see that if (a^b)%2==1 then there is no solution because a^b must be even because it's equal to 2(a&b).2.2) but there is some even numbers that can't be answers too. lets consider some cases: if a and b have the same leftmost bit X than XOR on position X must be (1^1)=0, but at the same time AND on position X must (1&1)=1 => this case is not possible, so leftmost bit in a and in b not in the same position. now lets say that a>b so leftmost bit in a is more that in b. if a>b it means that on position X XOR equals (1^0)=1 and AND equals (1&0)=0. but we remember that (a&b)+(a&b)=a^b => X-1 th bit of a&b must be 1 (otherwise a&b + a&b != a^b) => but if X-1 th bit of a&b is 1 that X-1 th bit of a and b is 1 simultaneously => X-1 th bit of a and b is 1. => X-1 th bit of a^b is 0. but we can use the same approach for every 1 in a^b. according to the above, if we see 1 in the position Y in a^b, then in the position Y-1 we MUST have 0 (otherwise we won't have a&b + a&b = a^b) 2.3) now we need to iterate over a^b and check if there is exist two adjacent indices M and M+1 such that M==(M+1)==1. if they exist, then answer is -1. otherwise we can get answer.3) iterate over a^b. if bit X is 1 then a+=(1<b because i want so) and a+=(1<<(X-1)), b+=(1<<(X-1)) (because as i proved it above, X-1 th of a&b must be 1). thats all.
 » 2 months ago, # |   0 anyone can tell me test case which hacked D
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Probably people using unordered map. https://codeforces.com/blog/entry/62393Like this one for example https://codeforces.com/contest/1790/submission/190826838
•  » » » 2 months ago, # ^ |   0 i wanna test case
 » 2 months ago, # | ← Rev. 3 →   0 how to solve e ?a xor b= 2*(a & b) after this observation?
•  » » 2 months ago, # ^ |   0 x = 2 * (a & b)So a and b has similar bits to x / 2, let's say:a = x / 2; b = x / 2But, to maintain equation (a + b) / 2 = x, a should be 3 times bigger:a = 3 * x / 2; b = x / 2If this is not a valid pair, then there is no answer
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 a should be 3 times bigger ? how i'm not getting this point?
•  » » » » 2 months ago, # ^ |   0 if (a + b) / 2 = x, and b = x/2, then:(a + x/2) / 2 = xa + x / 2 = 2 * xa = 2 * x — x / 2a = (3 * x) / 2
•  » » » » » 2 months ago, # ^ |   0 thanks a lot _ /\ _
•  » » » » » » 2 months ago, # ^ |   0 You're welcome!
•  » » » » » 2 months ago, # ^ |   0 i ran a brute force dp on small constraints and found out a = x / 3 and b = a * 3. Lol i can share my dp code if you wanna know about it
•  » » » 2 months ago, # ^ |   0 how can we conclude that is this is not a valid pair then no other pair is possible? I am stuck in this statement.. PLease help.
 » 2 months ago, # |   +1 Nice problems like all other div 3s. orz ITMO University team
 » 2 months ago, # | ← Rev. 4 →   +12 My solution got TLE on test on problem FI've used Heavy-light technique.I thought the solution should fit in the time limit, but I was wrongAny thoughts why ??My solution solution explanationI made a vector to store black nodes, light query is to pass through all of black nodes in that vector, and check the distance with query's nodeheavy query is to run a multi source bfs and clear that vectorand BTW very nice contest today ORZUpdate : thie solution passed, i had to make a small change to make bfs code faster
 » 2 months ago, # | ← Rev. 3 →   0 **edit dont't try it, I made a mistakeIn problem G why does this case's answer is "NO"? 1 4 4 2 2 2 1 2 1 1 2 1 3 1 4 2 3 
 » 2 months ago, # |   0 Hi Guys! If you are upsolving and want help with video tutorials you can refer this: https://youtu.be/YEyg27tm2sQ
 » 2 months ago, # |   0 This contest had a lot of "standard" problems. Seems like both E and F could just be looked up, which is a little unfortunate.
•  » » 2 months ago, # ^ |   0 I think F was a good one, but for E yes it was standard, Actually I just searched for "How to find two numbers a, b where their sum is S and their xor is x"
•  » » 2 months ago, # ^ |   0 Agreed, I feel as though alot of people who did E just googled it, which makes rankings unfair.
•  » » » 2 months ago, # ^ |   0 You could google it too :)
•  » » » » 2 months ago, # ^ |   0 I would not cheat
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 It's not cheating, because it's legal You are not searching for a fresh solution for this problem, you are searching for a similar problem
•  » » » » » » 2 months ago, # ^ |   +9 It is legal according to the rules, but it feels unfair and I don't want to gain rating I don't deserve.
•  » » » » » » » 2 months ago, # ^ |   +1 ok it's up to you :D
•  » » » » » » » 2 months ago, # ^ |   0 oh shut it now, googling is also a skill and searching for hints to crack the problem will help you in the long run
•  » » » » » » » » 2 months ago, # ^ |   -12 sve ću vas pobit majku vam jebem retardiranu
•  » » » » » » » » » 2 months ago, # ^ |   -13 literaly nuke india and dont flinch
 » 2 months ago, # | ← Rev. 3 →   -32 Problem F, why TLE? just java(use java17)?
•  » » 2 months ago, # ^ |   0 My similar C++ solution runs for 800-900 ms, and jaTLEva often cost 4-5x times…
 » 2 months ago, # |   0 C is a harder version of https://codeforces.com/problemset/problem/1512/A
 » 2 months ago, # | ← Rev. 3 →   0 The data of problem C is too weak. There is not even a test case with $T=10000$. I hacked many people by $T=10000$.
•  » » 2 months ago, # ^ |   0 How? It says "the sum $n^2$ over all input sets does not exceed 2⋅10^5."
•  » » » 2 months ago, # ^ |   0 Thanks. I changed the post.
•  » » 2 months ago, # ^ |   0 Can you try hacking mine? I'm trying but it says Testcase can not be longer than 256 KB  ;-;
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 with generator
 » 2 months ago, # |   0 The name of problem B looks pretty familiar :)
 » 2 months ago, # |   +3 nuke cheaters pls
 » 2 months ago, # |   +4 Concerns about problem E.After the contest I visited a few solutions and searched online. There are codes available online to determine two numbers from their sum and XOR.I copied one solution and changed it a bit (i)in order to run for t test cases and (ii) set Sum to x*2,where x was the given XOR of a and b. It got accepted. Is it okay to have this type of problem which has solutions available online?
 » 2 months ago, # |   0 I solved till D :( because i got stuck at C for simple implementation bug which i couldn't figure out and took most of my time and then i solved D in the last minutes after doing C. I wish I could have more time for E! I will try my best to reduce these mistakes in the next round.
 » 2 months ago, # |   +5 For F, how to prove the efficiency of "keep doing BFS from every c[i], but only push a new node in the queue if its distance is getting decreased"
•  » » 2 months ago, # ^ |   0 How about the case when tree is c0->c1->c2......ci->ci+1->....->cn for each i, doesnt it takes O(n)?
 » 2 months ago, # | ← Rev. 3 →   +9 I have solved problem F with sqrt-decomposition over queries in 997 ms. Solution.We can divide all queries in $\dfrac{n}{\sqrt{n}}$ blocks with size of block equal to $\sqrt{n}$. When we reached a border of current block, we can run multi-bfs from all of black vertices in this block and calculate vector dist[u] = distance to nearest black vertex from vertex u. Also we can calculate distance between two vertices in same block with LCA in $O(1)$.So, solution works in $O(n \cdot \sqrt{n})$.
•  » » 2 months ago, # ^ |   +10 This was my solution from the testing phase, and I had one hell of a time squeezing it into TL. Thankfully, the problem authors increased the TL after this.
 » 2 months ago, # |   0 Nice contest. Had enough time to finish the dishes after solving 5 array problems as I do not know graph/trees.
 » 2 months ago, # |   0 problem F more like Xenia and Tree 2
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 190861468 can anyone try to hack my E solution? I do not have proof for this approach
 » 2 months ago, # |   0 I liked C and D, couldn't solve from E and above.
 » 2 months ago, # |   +1
 » 2 months ago, # |   0 F problem, so many Python submissions got TLE, but the same of C++ can just AC, that's not fair! I think the tester at least should test some widely used language, not just C++!
•  » » 2 months ago, # ^ |   0 the TL is 4 seconds, i do not think the authors could've possibly made it more otherwise people would just brute it, tourist's solution was under 200ms.
•  » » » 2 months ago, # ^ |   0 But some red can't pass it using python, so if we have different TL for different language, this problem will be solved. I know it's hard to change, but it's really a good direction
•  » » » » 2 months ago, # ^ |   0 that is true, maybe Mike will make a change to allow custom TL per language in the future
 » 2 months ago, # |   0 it seems that no one can hack the code in $O(n^3)$ in problem C. I think this is a mistake. A better way is to make $1\leq n\leq 100, 1\leq t \leq 1000$.
 » 2 months ago, # |   0 How to solve F using DFS approach?
•  » » 2 months ago, # ^ |   +20 Let's call dis[u] as the minimized distance that all black vertices to u.For each $C_i$ ，we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain.We can demostrate that it's $O(n \sqrt n)$ ，because：1、For the first $\sqrt n$ vertices that will be black, all vertices' dis[u] will be updated for max $O(n)$ times，that's $O(n \sqrt n)$ ；2、After that, each dis[u] will be less than $\sqrt n$. When we DFS the other vertices, each dis[u] will be updated for max $O(\sqrt n)$ times，that's $O(n \sqrt n)$ .
•  » » » 2 months ago, # ^ |   0 How are you calculating dis[u] and couldn't understand this statement " For each Ci,we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain". Could you explain it in detail
•  » » » » 2 months ago, # ^ |   +1 DFS from the vertice that be black just now, and update each dis[u] with dis[u] = min(dis[u],depth). When dis[u] is already no larger than your DFS depth, it's ok to return.Sorry for my poor explanation, it's my first time to comment this at cf:)
•  » » » » » 2 months ago, # ^ |   0 Hey, how do you prove that the for later sqrt(n) queries they'll take at max sqrt(n) time? And what is the worst case tree for your solution?
•  » » » » » » 2 months ago, # ^ |   +4 Actually I also was thinking about this. IMO, it's not necessary that for each dis[u] will be less than $\sqrt{n}$. However, $ans = \min_{u}{dis[u]}$ would be less than $\sqrt{n}$ within $O(\sqrt{n})$. After than, when doing DFS (or BFS), each node will be updated only up to $\min(ans, dis[u])$ number of times. Why ans is less than $\sqrt{n}$ within $O(\sqrt{n})$ is where I am not exactly sure. This can be organized as the size of maximum subset of vertices such that the minimum distance between each pair of vertices is $\ge \sqrt{n}$. Just a heuristic explanation is that most of the vertices will be covering at least $\sqrt{n}$ vertices within $\sqrt{n}$ distance.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 so the worst case would be a linked list with the first sqrt(n) queries on consecutive nodes from one end? Tbh this "all queries after first sqrt(n) queries will give an answer of <= sqrt(n) seems so intutive rn but IDK how to prove it mathematically.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 After handling $k$ nodes the maximum distance must be at most $2n / k$. Consider a ball of radius $r$ around each of the black nodes. If some two of these balls intersect, the corresponding black vertices have distance at most two times the radius of the balls minus one, which is $2r - 1$. Otherwise, we have $k$ disjoint balls containing at least $r + 1$ vertices each, which is a contradiction for $r \geq n/k$.
•  » » » » » » » 2 months ago, # ^ |   0 Oops, i made a mistake:(. Not dis[u] is no larger than sqrt(n). Actually it's the update times of each node is O(sqrt(n)) for later queries. Thank you for making i realize it!
 » 2 months ago, # |   0 When will the rating get updated??
 » 2 months ago, # |   0 Looks like I overcomplicated D. Went for a divide and conquer instead of simple greedy because I couldn't convince myself that greedy works...
 » 2 months ago, # |   0 Can anybody explain problem E?
•  » » 2 months ago, # ^ | ← Rev. 6 →   0 I will try to explain how I solved this question... As, a+b = a^b + 2(a&b) Hence, a+b = x + 2(a&b) => a&b = x/2 let's denote x/2 as y. Now, a^b = x and a&b = y let's take an example say, x = 10 => in binary, x = 1010 and y = 0101Now the positions at which y is 1, both a and b will have 1 (a & b), and the positions at which x is 1 either of a or b will have 1, and other will have 0. Thus our answer will be a: 1111 & b: 0101. Of course, solution will not be possible when x and y both will have 1 at same position, We will handle this case separately. You can refer to my solution: https://codeforces.com/contest/1790/submission/190929183
 » 2 months ago, # | ← Rev. 2 →   0 Could anyone please explain the problem in this code? It is problem B of this contest. I cannot understand the explanation of the wrong test case Taisia and Dice
•  » » 2 months ago, # ^ |   0 The value of the removed dice is 5 in that test case, it is stated that it is the maximum that is removed so you can't have a dice with value 6.
•  » » » 2 months ago, # ^ |   0 Got it. Thanks
•  » » 2 months ago, # ^ |   0 In test 7 you are having a number on dice 6 while s-r = 5. And condition is that s-r is the largest number. "Taisia's pet cat steals exactly one dice with maximum value ai"
•  » » » 2 months ago, # ^ |   0 Ok. Thanks
•  » » 2 months ago, # ^ |   0 You have a die with 6 in test case 7, but the max allowed is s-r=20-15=5.
•  » » » 2 months ago, # ^ |   0 Ok.Thank you
 » 2 months ago, # |   0 So will this round be rated? >_<
•  » » 2 months ago, # ^ |   0 I hope so.
 » 2 months ago, # |   0 Can anyone tell why I don't see my ratings for this round ? Am I not qualified for div 3?
•  » » 2 months ago, # ^ |   0 They are yet to be updated.
 » 2 months ago, # |   +3 When rating will appear?
 » 2 months ago, # | ← Rev. 2 →   0 i didn't understand #D can someone explain me please?
•  » » 2 months ago, # ^ |   0 Consider sets of nesting dolls. They are segments consisting of consecutive numbers. Then there is the following solution: 1) sort the array 2) go through the elements in a row and see how many such elements there are. Let the elements x, the element itself, well, If the elements with a value of x — 1 are less, then we need to add to the answer the difference of these two numbers, because we need to create all sets of nesting dolls, in which the element x — 1 is not included in them. 3) output the answer This can be conveniently done using map (you can see my solution). P.S. I do not know English, so please forgive me typos or some grammatical errors.
•  » » » 2 months ago, # ^ |   0 thanks but i was expecting only question part
 » 2 months ago, # | ← Rev. 2 →   +2 When will wait over ? UPD: wait over.
 »