By khadaev, 3 years ago, translation,

Hello everybody!

Round 443 will start on Thursday, 26 October in 17:35 MSK.

Tasks are prepared by me, Konstantin Khadaev. It's my first round on Codeforces. Thanks to zemen, AlexFetisov, vepifanov, and Belonogov for testing problems, KAN for coordination, and MikeMirzayanov for this site and the Polygon platform.

Both divisions will have five problems to solve in two hours.

Scoring: in Div 1: 500 — 12501250 — 2000 — 2500, in Div 2: 500 — 1000 — 1500 — 22502250

Good luck to all!

UPD1: Congrats to the winners!

Div 1:

1. dotorya — solved all problems!
2. Um_nik
3. moejy0viiiiiv
4. V--o_o--V
5. Errichto

Div 2:

• +311

 » 3 years ago, # |   -103 PS :- IT IS RATED -___-
•  » » 3 years ago, # ^ |   -33 You triggered the curse :/
 » 3 years ago, # |   +47 Wow, Two contests in two days(CS Academy and codeforces) and written by the same author. I enjoyed the problems on CS academy, Hope they are good tomorrow too!
 » 3 years ago, # |   -36 Is it rated means? I am new so i didn't understand what rated means.
•  » » 3 years ago, # ^ |   -14 -first of all , this the most worst question in the universe :D , BUT if you are new here ... well it means that after the contest the codeforces will calculate your new rate ( you can see how to calculate it here ).and you can use the pretty extension Codeforces rate predictor to know your new rate ( because the system take some time to tell you the new rate ) if it's unrated , your rate will not change . this happen in some cases like , Educational rounds , some Mirrors Contests , if a there was a problem in the problem set or the codeforces system. hope a high rate for u .
•  » » 3 years ago, # ^ |   -14 Its the most common "three words" you will find on the CF. Next common three words is "how to solve".
 » 3 years ago, # |   -112 =i'll make a submission...-What is the complexity of your code ? = O(N^3) -
•  » » 3 years ago, # ^ |   -11 A could be quite reasonable depending on the problem. Consider the problem you are solving and the bounds, instead of making a sweeping statement on complexity.
•  » » » 3 years ago, # ^ |   +3 i know , it just a joke :(
 » 3 years ago, # |   -81 Is it rated?
•  » » 3 years ago, # ^ |   -47 you made the same comment last contest... and got the 5th place in the contest !
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 ignore
•  » » » » 3 years ago, # ^ |   -63 Фалунь Дафа хорош
 » 3 years ago, # |   -13 )
 » 3 years ago, # |   +1 will it be available C#?
 » 3 years ago, # |   0 Codeforces Round #https.
 » 3 years ago, # |   +4 I want to describe this not only as a contest, this is an opportunity to explore new thinks for everyone, and this can give a handfull of distribution of our future succes so I wish good luck to everyone and PLUSES ^-^ at the end.!
 » 3 years ago, # |   -18 Great!
 » 3 years ago, # |   -20 One of the shortest announcement I have ever seen!
 » 3 years ago, # |   +26
•  » » 3 years ago, # ^ |   0 try next time
•  » » 3 years ago, # ^ |   +9 Simillar thing happened when I tried to login. I think server is very slow and unstable right now.
 » 3 years ago, # | ← Rev. 2 →   +10 While registering, Error- "HTTP Status 403 -" :(
 » 3 years ago, # |   0 I was registered to the round, but now I see that I'm not registered and I can't register again (HTTP Status 403)
 » 3 years ago, # |   0 Apache Tomcat/8.0.46
 » 3 years ago, # |   +14 Wow the scoring distribution is announced so early! I guess this is a non-"traditional" round...
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 It is traditionally delayed...
 » 3 years ago, # |   +16 Why the delay?
•  » » 3 years ago, # ^ |   +6 Mission 6000 :p
•  » » » 3 years ago, # ^ |   0 Mission accomplished. :P
 » 3 years ago, # |   +1 delayed))
 » 3 years ago, # |   +1 Delayed again...
 » 3 years ago, # |   +3 Delays, delays, delays :P :P
 » 3 years ago, # |   +5 6000 reg only div2? Not bad :)
 » 3 years ago, # |   +8 servidor is very slow today, hope the contest continue rated.
 » 3 years ago, # |   +17 +10 min as usual
 » 3 years ago, # |   -12 for the writer,pls be short!
 » 3 years ago, # |   0 Why test case 3 in div 2 C is 0? Is there no program? Thanks!
•  » » 3 years ago, # ^ |   0 it's empty
•  » » » 3 years ago, # ^ |   0 its special :p !!
•  » » » 3 years ago, # ^ |   0 I don't get it, man! (output => the length of your program) Why ^ 0 is not a program? Why empty program as output? (No program as output)Thanks in advance!
•  » » » » 3 years ago, # ^ |   +3 It's the number of operations that your new function does before returning the value. For example, if k = 2: int modify(int value) { int value1 = value & 100; int value2 = value1 | 3; return value2; } If the k = 0, then you have the following function: int modify(int value) { return value; } 
•  » » » » » 3 years ago, # ^ |   0 Thanks!
•  » » 3 years ago, # ^ |   0 How did you know it was empty?
 » 3 years ago, # |   -7 What is the hack for B?
•  » » 3 years ago, # ^ |   +1 4 2 2 1 3 4
•  » » 3 years ago, # ^ |   +21 When the winner is changed most of the people count the new number of wins to be 0 but it should be 1 :D
•  » » » 3 years ago, # ^ |   +1 Failed on TestCase 33 due to this reason feels so stupid.
•  » » 3 years ago, # ^ |   0 4 2 2 3 1 4
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 4 21 3 2 4
 » 3 years ago, # | ← Rev. 2 →   0 How to solve Div-1 C and D?
•  » » 3 years ago, # ^ |   +45 div1C Consider graph where there are edges from A -> B iff A can beat B , now consider each SCC in this , if a node can beat atleast one from this SCC and if atleast one from this SCC can beat this node , this node also belongs to the SCC , so an SCC can be characterized by mini and maxi which denotes min value of ith game strength of someone from this scc and similarly for max. This breaks the graph into a chain of SCC's , when you add a new node , find where it should belong in this chain , it will either belong complexity between 2 scc's or at the endpoint of the chain in which case just add this , or it will result in merging of a subarray in this chain into this node.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 "when you add a new node , find where it should belong in this chain"But assuming the worst case that at step #k you have k SCCs in the chain, doesn't this mean that the overall complexity becomes O(n^2*k)?There's probably something I don't understand in your explanation. Could you maybe elaborate just a little bit?Thanks in advance :)EDIT: ah, nevermind, you can probably keep the SCCs sorted for each k and use lower_bound() or something similar
 » 3 years ago, # |   +129 Summary of my performance this round.
 » 3 years ago, # | ← Rev. 3 →   +1 Ignore ...
 » 3 years ago, # |   +54 Why i prefer dynamic scoring
 » 3 years ago, # | ← Rev. 2 →   0 what's wrong with this 31762295 for div2 B??
•  » » 3 years ago, # ^ |   0 For 2 Players and 10^12 Wins. your ans will take many iterations. I think after atmost 2000 iterations always the one with maximum power wins. Thats how I did and passed pretests.
•  » » » 3 years ago, # ^ |   0 yeah after atmostst 500*500 iteration the one with max power wins.that's what i m doing...while loop will iterate atmost 500*500 times..then why it's tle
•  » » 3 years ago, # ^ |   0 vector is too slow to solve this problem, why don't you try to use deque?
•  » » » 3 years ago, # ^ |   0 i didn't thought of that.however after many submissions got AC..my approach was:for value at i check how many are less than value at i...if it is greater than k then it will be answer otherwise max value...
•  » » 3 years ago, # ^ |   0 vector.erase is O(n)
 » 3 years ago, # |   +20 The problem C in Div. 2 was nice. Required a good bit thinking (atleast for me). My mind was blown...
 » 3 years ago, # |   0 How to solve div2 C ? Was it like taking Xor , and , or of all values and print in the same order. ?
•  » » 3 years ago, # ^ |   0 no that will not print the correct answer.Try in this input:|3^2|1 Take x as 2.
•  » » » 3 years ago, # ^ |   0 Thanks , Then what was the algorithm behind this you constructed to solve ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Don't know.i thought it for a while.. bt couldn't come up with the right answer.
•  » » » » 3 years ago, # ^ |   0 Suppose you have a 10 digits binary numbers — let 'xxxxxxxxxx' be his digits : what happen to those after the N operations? Can we get the same result with just 1x of each binary operation? :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 a = 1023 b = 0 for each (op, val) in input: a = a op val b = b op val From there, we can see that for each bit in a and b: bit on / off: no operation; bit on / on: or operation; bit off / on: xor operation; bit off / off: or and xor operation. 
•  » » » 3 years ago, # ^ |   0 bit off / off: and 0 operation
•  » » » 3 years ago, # ^ |   -21 You can just do these 2 operations : AND (a ^ b) XOR b
 » 3 years ago, # |   +11 Those rooms in which there are no hacks are going to be destroyed by system tests. n = 10, k = 4, arr = {1 5 4 3 2 10 9 8 7 6} ans: 5
•  » » 3 years ago, # ^ |   +11 oh...
•  » » 3 years ago, # ^ |   0 That's right!
•  » » 3 years ago, # ^ |   0 sad(
•  » » 3 years ago, # ^ |   +6 Oh.The sad moment when you realise there were about 14-15 WA solutions in your room and still you couldnt figure out a hack. In my room there were no hacks at all :p.Dont know why I missed this case :(
 » 3 years ago, # |   +7 Hacked 3 solutions in the last 3 minutes... (my last hack was 3 seconds before the end) So tense!
 » 3 years ago, # |   +7 I think for div 2 C the key is strongly connected components.If you look at the directed graph of the strongly connected components it is always a straight line.For each strongly connected component we need to save only two arrays of size K (the one with the minimum power levels for each skill and the one with the maximum power levels).Thus we can save the strongly connected components inside a map (the key for the map is a structure containing the two arrays and the size of the component).In order to add a new vertex we need to use a lower_bound on the map and then iterate through the map mixing together the new connected components.
•  » » 3 years ago, # ^ |   +8 Div 2 C?? Are you kidding me??
•  » » » 3 years ago, # ^ |   0 He means Div.1 C.
•  » » » » 3 years ago, # ^ |   0 I think so :p, Div 2 C is not a Graph Theory problem at all
•  » » » » » 3 years ago, # ^ |   0 Oh yeah, div1C
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 How did you bring connected components into picture Jefe ??
•  » » » 3 years ago, # ^ |   0 we add an edge from vertex a to vertex b if player a can beat player b in at least one game. Then the players that have a chance to win the game are the ones that can reach every node. Of course these nodes form a strongly connected component.
•  » » » » 3 years ago, # ^ |   0 Okkay Got it !! Thanks
•  » » » » » 3 years ago, # ^ |   0 Answer is number of strongly connected component or what ???
•  » » » » » » 3 years ago, # ^ |   0 Answer is the size of the initial connected component (they form a directed path)
•  » » » » » » » 3 years ago, # ^ |   0 n is 5×10^4 though. Won't it get TLE?
•  » » » » » » » » 3 years ago, # ^ |   0 Jefe Sorry to disturb !!!! How would you solve for this one n = 3 k = 2 1 2 2 1 3 3so In the first case, a single node is present ,then the second node comes and two directed edges are formed 1->2 and 2->1 . How do you get answer here ??
•  » » » » » » » » » 3 years ago, # ^ |   0 First the first node forms a SCC -> answer = 1. After adding the second node, you have a SCC nodes 1 and 2 -> answer = 2.The third node will form a SCC by itself, and this SCC is better than the previous SCC (they form a directed chain SCC{3} > SCC{1, 2}). The answer will be the size of the best SCC -> 1.
•  » » » » » » » » » 3 years ago, # ^ |   0 Thanks I got it . :)
•  » » 3 years ago, # ^ |   0 I like the idea of that key structure.You find a position of the first characteristic and then move up and down looking for min/max on the next ones (expanding the interval), correct?
 » 3 years ago, # | ← Rev. 2 →   +11 And again I will fail C :( When do I will come in div1 :(OMG It passed :p. Finally here I come div1 :D
•  » » 3 years ago, # ^ |   +5 I know that feeling :(
•  » » 3 years ago, # ^ |   +1 I'm dreaming about blue colored handle...
 » 3 years ago, # |   +86 Huh, these were really hard B and C. How to properly solve B? I did something like binary exponentation of reductions (sequences when consecutive groups of same people are merged and when I see interval of length k of same numbers I throw it away). However when done naively these reducted sequences can grow a lot, so I kept only a big suffix and prefix of them, but I am not sure about correctness of the way I did it. On the beginning I tried to reduct initial sequence, then reduct result concatenated two times and consider some cases, but that seemed to be really prone to bugs.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +34 I hope I haven't missed any edge cases, but basically what I did was: Preprocess the single bus to remove as many teams as possible Process all the buses together, removing teams that came from the two consecutive buses At this point, if the "middle" buses (other than first and last) have contestants from more than one city, we're done. Otherwise, we take the prefix from the first bus, the number of participants from the middle buses, suffix from the last bus and do stuff in the naive way.
•  » » » 3 years ago, # ^ |   0 can u please help me in my code for this problem I really tried hard for it and i just don't want that effort to be useless http://codeforces.com/contest/879/submission/32374450everything is explained .
•  » » 3 years ago, # ^ |   -26 Just curious.Is it easy for you to get the idea from source code 31746290?
 » 3 years ago, # |   +49 This is not a Div.1, it is Div.0... I spent a lot of time to solve 1B. Anyway, I need to go to sleep...
 » 3 years ago, # |   -7 Noooo.. I screwed up on div2C! I submitted 30 sec before end of contest and got WA because i thought that x was <= 2047 and not 1023 :(
 » 3 years ago, # | ← Rev. 2 →   0 How to solve Div2 E or Div1 C ???
 » 3 years ago, # |   0 How to solve div 2c ?
•  » » 3 years ago, # ^ |   +4 a = 1023 b = 0 for each (op, val) in input: a = a op val b = b op val From there, we can see that for each bit in a and b: bit on / off: no operation; bit on / on: or operation; bit off / on: xor operation; bit off / off: or and xor operation. 
•  » » » 3 years ago, # ^ |   +11 same method as mine but in the bit off / off case , I used & operation instead of using | and ^ ..Any particular reason why you used | and ^ instead of just using & ?Anyways, here's my solution if you are interested.Short explanation : observe that 0 to 1023 means all numbers having 10 bits.. Also observe that all the & , | and ^ operations actually apply to INDIVIDUAL BITS rather than the full number... So keeping a = 1023 and b = 0 means all bits of 'a' are set to 1 and all bits of 0 are set to 0.so accordingly check what happens to them AFTER applying all the 'n' operations, If no change ==> means the AND bit was '1' , or bit was '0' and xor bit was '0' and so on..,my submission --> 31767545
•  » » » » 3 years ago, # ^ |   +1 i don't understand. please explain more. why 1023 and 0, what i can get from them after the n operations.
•  » » » » » 3 years ago, # ^ |   0 see, 1023 == (1 1 1 1..... 1) (10 times) and 0 == (0 0 0 ...........0) (10 times)so basically we can treat 1023 and 0 as rather a SET of 10 bits..now apply all the mentioned operations,after applying if the a particular bit of 1023 remains 1 and that bit of 0 remains 0, this means that all those operations do NOT CHANGE THAT PARTICULAR BIT IN ANY NUMBER! Why? --> well that's because in every number that particular bit can be either 0 or 1 and no matter what that bit is , it wont change because we have tested it for both 1 and 0Similarly there are 3 more cases , all the cases have the same reasoning , i.e. if 1 1023 bit changes but 0's bits do not change it means that whatever be the number that Bit has to be equal to zero,apply same reasoning to get to the final answer!.. Hope this helps!
•  » » » » » » 3 years ago, # ^ |   +1 Thankyou.W hen i read your previous comment my mind was not registering the fact that BITS OPERATION apply to single bit, so i didnt understood the solution. so one day when i was working on something, suddenly my mind clicked and i was able to solve it. This was good problem.
 » 3 years ago, # |   0 How to solve Div2 D?
 » 3 years ago, # |   0 CF Predictor DIV 2 DIV 1
 » 3 years ago, # |   +17 Is the Div.1 contest really of the difficulty of Div.1? I spent more than 1h 40min working on B and only resulted in 5 Wrong Answers on pretest.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 It was hard, but i remember harder contests, for example http://codeforces.com/contest/704.
 » 3 years ago, # |   0 Ugly code, without any beautiful optimizations, but ... AC =)
•  » » 3 years ago, # ^ |   0 solution for C: click
 » 3 years ago, # |   +68 Thank you for 5 great problems!btw, I got AC on E after contest by adding one character on my TLE code (I knew that could cause TLE, but my unconciousness omitted one character). and I got only A passed :(I really liked this problemset although I'll get -170 :)
 » 3 years ago, # |   +56 Tests for div1B are weak. Noam527 found a test, that breaks my AC solution:4 3 31 1 2 1http://codeforces.com/contest/878/submission/31762139My solution outputs 6, while it should be 0.
•  » » 3 years ago, # ^ |   +7 It is very bad to provide a hard task with weak tests: Not many people will solve it and they would be upset that other guys have accepted incorrect solutions. Those, who solved it correctly, would be upset that some other folks have accepted incorrect solutions, lowering their achievement. Those who have accepted incorrect solutions would also be upset, as this gives them no satisfaction and unjustified points. (Not 100% sure about that though.)
 » 3 years ago, # |   +38 Challenge: div1D with k ≤ 1000.
•  » » 3 years ago, # ^ |   +5 Do you have a solution on mind or is it just your wishful thinking? Looks really hard
•  » » » 3 years ago, # ^ |   0 I think that my solution will work (except for input and sorting (the latter can be done in linear time))
•  » » » » 3 years ago, # ^ |   0 Can you please explain your solution? I could not understand the code.
•  » » » » » 3 years ago, # ^ |   +28 Let's suppose we have only one query of third type. Then we can maintain only the characteristic which we are asked for. Now let's do binary search on answer (there are only k possible answers), then we can maintain only one binary characteristic: is the real characteristic bigger than our bound (from binary search). Max/min on binary characteristic is equivalent to or/and.Now we can do parallel binary search for all queries of the third type and do our operations using bitsets.Complexity will be
 » 3 years ago, # |   +7 Well,good problems today.
 » 3 years ago, # |   +1 can anyone please explain Div 2 problem C logic ? thanks in advance :)
 » 3 years ago, # | ← Rev. 2 →   0 I failed test case #7 on problem C div 2.Can somebody tell me what is wrong with my result? 3 ^ 125 ^ 377 & 1019 Participant's output 2 & 1019 ^ 260 Jury's answer 2 | 4 ^ 260 Checker comment wrong answer The participant's program isn't equivalent to the inputI passed this one with the same idea, grouping by operators: 3 & 242 ^ 506 ^ 522 Output 2 & 242 ^ 1008 Answer 2 | 781 ^ 253 Checker Log ok OkThanks in advance!
•  » » 3 years ago, # ^ |   +1 Just try any input, e.g. 0. With the input program: ((0 ^ 125) ^ 377) & 1019 = (125 ^ 377) & 1019 = 260 & 1019 = 256. With your program: (0 & 1019) ^ 260 = 0 ^ 260 = 260.
•  » » » 3 years ago, # ^ |   +1 So you should see, the order of the operations matters.
•  » » » » 3 years ago, # ^ |   0 Thanks!
 » 3 years ago, # | ← Rev. 2 →   +25 Cheater Report:- ImNaman and kingside have cheated as you can see even variable names are same for problem A and B and slight change in variables of C.
•  » » 3 years ago, # ^ |   0 how did you find out ?
•  » » » 3 years ago, # ^ |   0 I was just looking at the standing and saw kingside solved A and B within 2 minutes ,then I went to his submissions page and saw that ImNaman is his teammate and then rest of the work was fairly simple.
 » 3 years ago, # |   +12 When will be editorial published?
•  » » 3 years ago, # ^ |   0 still waiting :p
 » 3 years ago, # |   +3 Editorial!!?
 » 3 years ago, # |   -6 Will there be any editorial? Thx :)
 » 3 years ago, # |   -18 Why are the editorials so late?
 » 3 years ago, # |   0 what was the logic of "C #div-2".????I couldn't understand till now. please someone explane clearly ......
 » 3 years ago, # |   0 Can Anyone Explain Div 2 Problem A?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Iterate through the array of s[i] and d[i] and keep updating the present day of meeting the current doctor.To update the present day, if (presentDay < s[i]) presentDay = s[i]Otherwise, find the smallest value of k (>=0) such that: presentDay < s[i] + k*d[i] and put presentDay = s[i] + k*d[i] for that value of kThe answer will be the presentDay for the last doctor in the array
•  » » » 3 years ago, # ^ |   0 Thanks.
 » 3 years ago, # |   +4 Where is the editorial??
•  » » 3 years ago, # ^ |   +22
•  » » » 3 years ago, # ^ |   0 thank you
 » 3 years ago, # |   -23 Hello, can someone tell me where can I find the editorial of this contest? Thanks.
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   +1 In proB, why test 5 2 1 4 2 5 3. The output is 4? I think the output is 5? Can someone explain for me?
•  » » 3 years ago, # ^ | ← Rev. 6 →   +6 5 2 1 4 2 5 3 first win: 4 because (1 < 4). 4 2 5 3 1 the second win: 4 because (4 > 2). Answer 4 (because 4 won two wins in a row).
•  » » » 3 years ago, # ^ |   0 5 2 2 1 3 4 5 this test why the power's winner is 5 ? I think answer is 3 ?
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +6 5 2 2 1 3 4 5 2 1 3 4 5 winner is 2 2 3 4 5 1 winner is 3 3 4 5 1 2 winner is 4 4 5 1 2 3 winner is 5 5 1 2 3 4 winner is 5 5 have two wins. It means answer is 5.
 » 3 years ago, # |   -19 Where is Editorial?
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   -18 Editorial ??
 » 3 years ago, # |   +5 I get WA in Div2 C because of additional space at the end of first line. I thought that Codeforces typically ignores additional spaces at the end of line.