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

### Egor.Lifar's blog

By Egor.Lifar, 13 months ago, translation, ,

Hi!

On Jun/01/2019 17:35 (Moscow time) we will host Codeforces Global Round 3.

It is the third round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.

• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

• In each round top-100 participants get points according to the table.

• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.

• The best 20 participants over all series get sweatshirts and place certificates.

The problems of the round were developed by me, egor.lifar and UnstoppableSolveMachine. We are glad to say that we have prepared 8 tricky tasks for you. We hope you will enjoy them!

Thanks to KAN and _kun_ for the help with coordinating the round, and cookiedoth, lewin, voidmax, 300iq, Aleks5d, Learner99, Jeel_Vaishnav, arsijo, KAN, Ashishgup, AlexFetisov, V--gLaSsH0ldEr593--V for testing!

Good luck!

UPD. 1:

Here are a few words from the sponsor of Global Rounds, XTX Markets.

Hello, I’m Yuri Bedny from XTX Markets! While studying at university I actively took part in programming contests and later got to apply these skills at XTX Markets. Our office in London (UK) is looking for candidates for two open positions. We hope it will be interesting for some of you to apply your skills and knowledge in problems we are solving. I wish good luck to all the participants and hope you’ll enjoy the problems.

Open positions at XTX:

• XTX Markets is looking to expand its Java team. You’d be expected to be able to design low-level data structures and algorithms to fit particular performance characteristics. We have a direct impact on profits and very little bureaucracy and are open to candidates with no financial experience. Read the details via the link.
• XTX Markets is hiring into its Core Development team in London. This team is responsible for the design and implementation of the platform that provides a broad range of post-trade functionality essential to the firm’s business. This complex, distributed system has been developed in-house using a distributed microservices architecture to provide high throughput (thousands of trades per second) and high availability (24x7 operation) while also allowing very agile but well-controlled development practices (multiple production releases per day). The system is implemented primarily in Go, but prior Go experience is not required for those willing and able to learn quickly. The only necessary skills are exceptional programming ability, a passion for solving real-world problems, and a dedication to rigorous software engineering. Read the details via the link.

If you are interested in these positions, then fill out the application form via the link or during registration for the competition.

UPD. 2:

The scoring distribution will be 500 — 1250 — 1500 — 1750 — 2250 — 3000 — 4000 — 4000. The round will last 2 hours and 15 minutes.

UPD. 3:

Current results of all Global Rounds.

Congratulations to the winners!

UPD. 4:

Announcement of Codeforces Global Round 3

• +121

 » 13 months ago, # |   +76 Another rated round after a long break! Yeah!
 » 13 months ago, # |   0 Hope it will be a balanced contest. Not like the previous one :)
•  » » 13 months ago, # ^ |   +25 Fortunately the wish came true. Good problemset!
•  » » » 13 months ago, # ^ |   -19 IMHO bad problemset
 » 13 months ago, # |   -49
 » 13 months ago, # |   -29 Why the Announcement link is given two times?
 » 13 months ago, # | ← Rev. 4 →   -35 deleted :(
 » 13 months ago, # |   +14 Where is the number of problems and score distribution?
•  » » 13 months ago, # ^ | ← Rev. 3 →   +12 It will be posted not long before the contest starts, maybe.(It is posted just two minutes before starts.)
 » 13 months ago, # |   +8 Hope everyone can have a good performance! (and hope I can get red again)
 » 13 months ago, # |   +5 Hi, new member of the CodeForces community here. Looking forward to participating in the contest and getting a good rating and learning cool stuff. Wishing everyone the same too!
 » 13 months ago, # |   +29 I'm interested in XTX Markets job but are they interested in me XD ? (I know the answer don't tell me)
 » 13 months ago, # | ← Rev. 3 →   -52 I like global rounds (I didn't entered any of them)
•  » » 13 months ago, # ^ | ← Rev. 2 →   +60 Ok, ok I deserved it (-52)
 » 13 months ago, # | ← Rev. 2 →   -15 Do global rounds support hacking? if yes then, during or after the contest?
•  » » 13 months ago, # ^ |   +46 During the contest of course, just like in regular rounds.
•  » » » 13 months ago, # ^ |   -6 Thank you for the clarification.
 » 13 months ago, # |   -33 Are there remote jobs at XTX Markets?
 » 13 months ago, # |   -34 Here we go!!
 » 13 months ago, # |   -41 How many problems will be shown
•  » » 13 months ago, # ^ |   -25 eights
 » 13 months ago, # |   0 1.. 3.. 5.. 7.. 9.. Finally!! the contest season is back!
 » 13 months ago, # |   -10 hopes this contest will bring happiness in our life
•  » » 13 months ago, # ^ |   +38 happiness is a state of mind.
 » 13 months ago, # | ← Rev. 3 →   -40 round will be rated for those who have not solve anything?
•  » » 13 months ago, # ^ |   +52 If you do not make a single attempt, it won't be rated for you. Otherwise it will be.
 » 13 months ago, # |   -24 Why you don't thanks MikeMirzayanov for amazing systems Codeforces and Polygon! ?
•  » » 13 months ago, # ^ |   0 they have bro
•  » » 13 months ago, # ^ |   -31 LOL what an attempt to get free upvotes
 » 13 months ago, # |   0 Why I was told that too many request and couldn't submit my code?
 » 13 months ago, # |   +43 JOJO's Bizarre Adventure? That's pretty cool!
•  » » 13 months ago, # ^ | ← Rev. 5 →   +24 This comment has been edited and I sincerely apologize for my lack of knowledge about this great anime
•  » » 13 months ago, # ^ |   +10 Still cannot believe I lost this round...
 » 13 months ago, # |   -7 Is this a JoJo reference ?
•  » » 13 months ago, # ^ |   +16 Aha! I believe that there are only two sorts of people in the world, those who like JOJO, and those who don't know JOJO!
 » 13 months ago, # |   +58 Problem D was easier than Problem C. Am I the only one who felt that way?
•  » » 13 months ago, # ^ |   +4 C feels somewhat hit-or-miss, if you're familiar with the trick behind it, it's a cakewalk, otherwise it'd take some brainstorm.
•  » » » 13 months ago, # ^ |   +27 I found the way to solve the problem only took a short time, but it took me more than an hour just to correct the error in the code. :( But it took only 14 minutes to solve D, while it took 91 minutes to solve C.
•  » » » 13 months ago, # ^ |   -16 What is the trick?I can't think anything as a trick. Is it "if $|i-j|*2>=n$ then $|i-j|>=n/2$"?
•  » » » » 13 months ago, # ^ |   0 I think trick is temporary swap, in an 8 long array if you need to change index 6 and 7, first swap(1,6), then swap(6,7), then swap(1,7). Part "you should use no more than 5⋅n operation" was a good hint but I wasn't able to think that during contest.
•  » » » » 13 months ago, # ^ |   0 I meant the one of sorting the array using minimum swaps (if not counting the condition of $|i - j| \ge n/2$) by DFS idea.Once grasping that, the derived solution would be trivial.
•  » » » » » 13 months ago, # ^ |   0 I don't know how you used that in this problem but I don't see any similarity.
•  » » 13 months ago, # ^ |   0 Oppositely I thought E was easier than D.
•  » » 13 months ago, # ^ |   +28 Weird flex, but D was extremely hard for me, lol
•  » » 13 months ago, # ^ | ← Rev. 2 →   -10 Did we have to use the fact that every integer from 1 to 2⋅n is mentioned exactly once anywhere in the solution? I think I have not used it anywhere in my soln. But its complexity is nlog(n) using segment tree. UPD: Got it.
•  » » » 13 months ago, # ^ |   0 No, see my solution 54947377 Hopefully it would be correct, coded it in the last few minutes
•  » » » 13 months ago, # ^ |   0 Yes we can use the fact that every integer is mentioned exactly once.It makes the comparisons easier.We divide the pairs(a,b) in two parts:- Part 1:(a>b) Part 2:(ab1b2) bcoz(a2>a1 and a1>b1 so a2>a1)If part 2 has more elements then the answer will be the pairs sorted in decreasing order of second element.
•  » » 13 months ago, # ^ |   0 i felt is was easier than B also.
•  » » » 13 months ago, # ^ |   0 That, might be also right to some extent. Actually it took 18 minutes for me to solve B, which is longer than the time took for me to solve D.
 » 13 months ago, # | ← Rev. 3 →   +24 Regarding problem F, is it true that there will always exist at least one $s$ with not more than $2$ bits being set? :OMy solution only checked for those (and their compensation, just in case) and got Pretest passed :OUPD: It did fail at test 49. GG. :DUPD2: My source code was actually screwed up a bit. Still AC after fixing some bugs and optimizing a bit. ;) (54974178)
•  » » 13 months ago, # ^ |   +13 One case I can think of is an array with all elements equal(of size 60 or so) and maski has the ith bit set.
•  » » 13 months ago, # ^ |   0 No. Suppose that we have one object for each mask with exactly two bits set, and that each object has value 1. If we use an s with at most 2 bits set then only a small fraction of the objects will have their values negated, so the sum will still have the same sign. And the same thing happens for all s with 60 (or more) bits set (this was what you meant by compensation, right?).But if you're lucky such a case won't be in the system tests. :)
 » 13 months ago, # |   +8 How to solve F?
•  » » 13 months ago, # ^ |   0 Maintain sum and try to randomly switch bits?
•  » » » 13 months ago, # ^ |   +8 I did this, and my rationale about this solution was that the expected value of the sum is 0 because every number will flip the sign with probability 1/2. But since expected value is only average there might be the case that there a lot of small positive numbers reachable and few large negatives. In this case, random search can fail. I'm not sure if random search is a expected solution for this problem, and I will be happy to hear if it is a valid solution, why it is expected to work on time (with high probability).
•  » » 13 months ago, # ^ | ← Rev. 4 →   -8 I passed the pretests with following algorithms: Repeat this operations until you find an answer. 1. Choose value s randomly between $1$ and $2^{62}−1$. 2. Check the total prices. To calculate, it usually takes $O(NlogN)$, but if you use __builtin_popcountll (if C++), it takes $O(N∗C)$ and $C$ is around $5$. 3. If the sign of total prices has changed, you successfully found the answer. On average, you should do $~2$ operations. Is there any doubt that there is some cases that the sign of total price changes in very less percentage of $s$? I think it's not. I checked $100,000$ random cases which the value of mask is between $1$ and $63$. The worst case was the sign of total prices changes in $8/63$ of s assume s is also between $1$ and $63$. P.S. The testcase which the sign changes with only $8$ out of $63$ $s$ is as follows: Testcase10 0 45 -1 11 -1 21 -1 45 0 6 -1 51 0 19 0 40 0 60 0 51
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +61 Try this test case:2621441 1310721 1310731 131074...1 393215The only answer is $393216+524288*k$.
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   +15 Wow, incredible. :)
•  » » » » 13 months ago, # ^ |   0 amazing. how did you get this?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Given the fact that only the bits being set on for at least one mask are counted, I guess your testcase can still be intercepted: 54974178.Changing $n$ into $262145$ and adding a line: 1 2^62-1 will counter such solutions.The systest of F still looks surprisingly weak as of now, which is strange.
 » 13 months ago, # |   0 How to solve E?
•  » » 13 months ago, # ^ |   +9 Sort points via $s_i$. Then maintain stack of points having $s_i < t_i$. When you check another point, push it to stack if $s_i < t_i$ and try to match it with points on stack until stack becomes empty or you get $s_i = t_i$ if $s_i > t_i$.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 How about changing stack to queue?I think I have implemented algo like that, but I got WA.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +3 I thought so during the contest, but probably no...ok, then it still yes, I guess :)
•  » » » » » 13 months ago, # ^ |   0 But, I think my submission 54936636 did something like yours.
•  » » » » » » 13 months ago, # ^ |   0 Oh! I found a stupid mistake.
•  » » 13 months ago, # ^ |   +10 Unfortunately, I have drunk too much prostate juice today, so I solved the problem incorrectly (greedly from both ends) and can't give you a hint what the correct solution is like.
 » 13 months ago, # |   +31 what the hell is pretest 14 on E ?
•  » » 13 months ago, # ^ |   +62 Something like this maybe? I got WA on 14 until I fixed this case 4 1 4 5 8 2 3 6 7 
•  » » » 13 months ago, # ^ |   0 yeah. That works. Thanks. Forgot to pair j with the max i, instead put min i, which lead to wrong solution.
 » 13 months ago, # |   +22 Too greedy contest
 » 13 months ago, # | ← Rev. 2 →   +21 Problem H proved once again that Za Warudo's true power is, indeed, the power to reign over this world
 » 13 months ago, # |   0 Can someone please give hints for question: C. Crazy Diamond.
•  » » 13 months ago, # ^ |   +11 Consider how to use no more than $5$ swaps to move number $i$ to position $i$.
•  » » » 13 months ago, # ^ |   0 Hi! Im sorry I still did not understand it, can you or anyone please explain it. tia!
•  » » » » 13 months ago, # ^ |   +5 You can find the positions of the numbers in the middle first. For example, if n=6, the order of numbers to find a position will be 3->4->2->5->1->6. When treats 3, if the original position>3, swap p1 and 3. And swap p1 and pn, and swap p3 and pn. If you do this way for each number, you can move each number to the correct position within three times. So the maximum number of the operation is 3n.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +26 Maybe there are simpler solutions, I will explain mine. $p_i=i$, we don't need to do anything. $0$ swaps. $abs(at_i-i)\ge\frac{n}{2}$, just swap directly. $1$ swaps. (Edited, should be $\ge$ but not $>$) $i\le\frac{n}{2}$ and $at_i\le\frac{n}{2}$, use $p_n$ as temporary variable. $3$ swaps. $i>\frac{n}{2}$ and $at_i>\frac{n}{2}$, use $p_1$. $3$ swaps. otherwise, let $x$ be the lefter one in $i$ and $at_i$, $y$ be the righter one. Swap $p_x$ and $p_n$, $p_y$ and $p_1$. Then swap $p_1$ and $p_n$. Finally swap $p_x$ and $p_n$, $p_y$ and $p_1$. $5$ swaps.
•  » » » » » 13 months ago, # ^ |   0 That is also fine. (Although I didn't think of that way during the competition.)
•  » » » » » 13 months ago, # ^ |   +15 2 should >=
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 I was not able to deal with the 5th case . :(
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Enumaration sort can be used and you will need at most n operations to sort.
 » 13 months ago, # |   0 Too Greedy Contest, the setters want to steal our rating :(
 » 13 months ago, # | ← Rev. 2 →   -10 what is pretest 14 in problem E? why this code gets WA? 54943503
•  » » 13 months ago, # ^ |   0 I also had this problem. I think we need to add d=min(d, (s[j] — s[i])/2)
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Your code will fail on tests like 4 1 6 7 10 3 5 8 8 Your code gives the output "NO" but the correct output will be "YES" YES 3 1 2 1 1 4 1 3 4 1 here^ is one of the suitable output for the above test case
 » 13 months ago, # | ← Rev. 2 →   +34 Please tell me problem F is not about trying different $s(hit)$ randomly...
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 (retracted my previous claim; turns out there are counter tests)
•  » » » 13 months ago, # ^ |   0 Why tf it's div. 1 F then...
•  » » » » 13 months ago, # ^ |   0 Don't forget about Div.2 people :)) It's combined!
•  » » 13 months ago, # ^ | ← Rev. 2 →   +90 System test haven't started yet. I think they're trying to make that test :)
•  » » 13 months ago, # ^ | ← Rev. 3 →   +74 Deterministic solution for F:WLOG assume sum positive, otherwise change all signs. Iterate $k$ from $61$ to $0$. For each $k$ and each $i$, sum $val_i$ over all masks such that the lowest on bit of $mask_i$ is the $k$-th. If this sum is positive, then turn on the $k$-th bit in $s$, otherwise do nothing.Proof this works: Consider a certain $0-1$ mask, and consider the expected value of the sum over all masks that have this mask as a prefix. (choosing a mask uniformly at random). All $i$ that have an on bit below the $k$-th contribute $0$ to this expected value, while the ones that are all $0$ below the $k$-th bit contribute $2^k$ times their sum. So our algorithm just forces the contribution for these to be always negative.
•  » » » 13 months ago, # ^ |   +2 I'm thinking for an hour also reading this but still don't know why this solution works. The fact that you're using the expected value in proof makes it not very convenient. So I'm assuming it's not something have to do with "random"s but couldn't figure out.
•  » » » » 13 months ago, # ^ |   0 Yeah, the expected value is just for convenience, the solution isn't random. In a bit more detail:For a mask $m$ with length at most $62$ let $f(m)$ be the expected value of the sum described in the problem if we choose a mask uniformly at random from among the masks of length $62$ that have $m$ as a prefix. (Using sum or average instead of expected value would give the same argument, I just found expected value clearer). By the linearity of expectation we can expand $f(m) = \displaystyle\sum_{i = 1}^n \displaystyle\sum_{s}\mathbb{E}\left[val_i \cdot (-1)^{popcount(s, mask_i)}\right]$Where the right sum goes over all masks of length 62 that have $m$ as a prefix. In particular for masks of length $62$ this is just the sum in the problem statement, which we want to make negative. So basically we build each digit of the mask while decreasing or keeping the expected value the same at each step. Initially the expected value is $0$, so this way we do get an answer at the end. The main claim is that the expected value for a certain $i$ and $m$ is $0$ if $i$ contains some $1$ after $m$, and $2^k \cdot val_i$ otherwise. This is because half of the masks with prefix $m$ have $popcount(s, mask_i)$ odd and half even as long as there's at least one on bit after $m$ (basically just restating that a set has the same number of odd size subsets as even size).
•  » » » » » 13 months ago, # ^ |   0 Okay, thanks for answering again. But still, I'm not sure about some parts. Do you prove that it'll be negative in the end? Or do you show it just decreases or stays the same in each iteration?
•  » » » » » » 13 months ago, # ^ |   0 I show that it decreases or stays the same. At the start it's $0$ because all masks have at least one on bit, so the end result is negative unless it never decreases. But if it never decreases then the sum of everything must be zero, which is false.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +29 The way I think of it is like this:Go through the $(value_i,mask_i)$ and group them depending on which bit is the last 1 bit in the mask.What juckter's soution does is making it so that the sum of values for each of those groups is $\leq 0$. He does this by doing the operations in a smart order, starting with mask 10000000 and then doing X1000000, then XX100000, ..., ending with XXXXXXX1. Note how modifying bit k doesn't change the contributions from groups 1 to k-1. This way he can make the contribution from each group be $\leq 0$.Also because the sum of everything in the beginning is $> 0$ at least one of those groups must after running the algorithm have sum of values $< 0$. One way to see this is proof by contradiction, assume that after doing the algorithm all groups have contribution $= 0$, that implies that they also initially all had contribution $= 0$ which is a contradiction.
•  » » » » » 13 months ago, # ^ |   0 Thanks, this is easier for me to understand.I was having a hard time to understand that groups don't block other's processes. Now it's clearer.
•  » » » » 13 months ago, # ^ |   +5 After reading mnbvmar's solution, here is the intuitive approach I got:Asume the sum of all the elements to be positive, otherwise change all signs.Iterate current_bit from 0->61Let the sum of all the values with current_bit as the highest set bit be current_sumNow, the values with higher set bits in their mask can be manipulated later on, but the ones contributing to current_sum cannot, because they are not effected by toggling higher bits in answer.So, if current_sum is positive, we must greedily toggle the current_bit in our answer, and then negate the values of all the masks having current_bit set as 1.This way, we will make sure that at each iteration, all the numbers with highest set bit as cuurent_bit sum up to non-positive number.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 I have a algorithm (not random) for problem F. Haven't tested it yet, but I think It's correct.Let's split A (the origin set of objects) into two subsets: A1 and A2. All masks in A1 have the bit 0 turn off, and A2 = A\A1.Suppose we have someway to assign bit 1, bit 2, ... such that sum of all val in A1 is non-negative. After assign bit 1, bit 2, ..., we have two option: turn off bit 0 or turn on bit 0, one of them will make the sum of A2 is non-negative. So, we found a way to assign bit 0, bit 1, ... such that sum of A is positive.
•  » » » 13 months ago, # ^ |   0 This argument is so elegant.
•  » » 13 months ago, # ^ |   0 I think that tourist's solution is not that kind of solution.
 » 13 months ago, # |   +15 10 seconds too slow to submit correct F :(Too slow :(
 » 13 months ago, # |   +121 Did somebody find a counter-test that makes random solution fail on problem F?
•  » » 13 months ago, # ^ |   +40 There's no such thing!!
•  » » » 13 months ago, # ^ |   +172 WTF!!
•  » » 13 months ago, # ^ |   +58 I was in same room as Um_nik and I made random solution to problem F. he didn't hack my solution, so there is no counter-test.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +8 He didn't lock problem F, so...
•  » » » » 13 months ago, # ^ |   +6 I know that my F is in big danger. I was just joking. Deep inside I am afraid of losing it.
•  » » 13 months ago, # ^ |   +195 Yep, _kun_ found some about a week ago :)
•  » » » 13 months ago, # ^ |   +29 Cool! I hoped there were. How would one construct such a test case?
•  » » » » 13 months ago, # ^ |   +34 https://codeforces.com/blog/entry/67316?#comment-515034I constructed it by looking at only test cases with val=1 and looking at various possible n and mask size and i found that this makes only 1/16 masks work: 8 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 I tried extending it to higher n and succeeded.
•  » » » 13 months ago, # ^ |   +18 It's very brave not to put that test in pretests, given the fact that people complain about weak pretests each time.
•  » » » » 13 months ago, # ^ |   +20 What should they be scared of?
•  » » » » » 13 months ago, # ^ |   +8 of people disliking the round
•  » » » » 13 months ago, # ^ |   +18 Huh, but it's not the case when you don't pass systests due to some silly error. This one here is pretty essential...
•  » » » » » 13 months ago, # ^ |   +1 I understand a difference but is it obvious to you that pretests shouldn't catch solutions with a wrong idea?I don't have a strong opinion about it FYI.
•  » » » » » » 13 months ago, # ^ | ← Rev. 2 →   -8 What's the point of pretests if they do catch solutions with a wrong idea?As far as I know, main purpose of pretests is to check if you understood statement correctly and that your solution barely does what it should do in general. Everything else is pretty optional.
•  » » » » » » » 13 months ago, # ^ |   +56 xdOne of points is exactly to catch solutions with a wrong idea. Don't forget about hacks. Sombody could submit a wrong submission from one account, lock it and then reading codes of other people to get a correct solution.
•  » » » » » » » » 13 months ago, # ^ |   -7 There's surely no point in catching all such solutions, otherwise there would be nothing to hack.
•  » » » » » » » » » 13 months ago, # ^ |   0 People don't hack hard problems, especially in combined-division contests. There are usually only 1-2 users with such problem solved in the same room.
•  » » » » » » » » » 13 months ago, # ^ |   0 That's true. But here's another point: People usually don't cheat on hard problems this way.And I think that participants who submit shit on hard problems thinking "no one hacks them so pretests should be strong" should be punished.
•  » » » » » » » » » 13 months ago, # ^ |   +33 I tried to hack F, but I lacked the intelligence to come up with a test case. I think it’s fair for someone who manages to find such testcases to get extra points. If not, then what is the purpose of hacks, indeed?
•  » » » » » » » » » 13 months ago, # ^ |   0 As I said, the issue is that it's a hard problem that almost nobody in the same room will solve.
•  » » » » 13 months ago, # ^ |   +16 If tests are weak, people complain about weak pretests. If tests are strong, more people solve F, so people complain about difficulty distribution. :)
•  » » » 13 months ago, # ^ |   +21 Could you also add that test case by dorijanlendvaj to upsolving testcases? It seems to break even more solutions. 262144 1 131072 1 131073 1 131074 ... 1 393215 
•  » » » » 13 months ago, # ^ |   +13 Done
•  » » » 13 months ago, # ^ |   +38 In case somebody wonders, the test structure is as follows:Take some number of bits $k$ (must be odd)Then for every bitmask except the zero ($2^k - 1$ in total), add the item with this mask and the weight: if bitmask == $2^k - 1$, the weight is some constant $-B$ (e.g. $B = 10000000$). if bitmask has even number of bits, the weight is $+A$ (e.g. $A = 20000000$). otherwise the weight is $-A$. One can see that the only way to change the sign of the sum is to use the mask $2^k - 1$. Which is $2^{-k}$ probability if you select the mask randomly. I also fill tests with some amount of random noise so you shouldn't be able just to use largest mask in the test data. Since $2^k$ must be at most $n$, the probability is about $\frac{1}{n}$, which is $n^2$ expected running time.It was also me who suggested not to put this thing in pretests, I thought it would be a good idea to allow hackers to came up with this test as well and probably the bad impact is not too large, you wouldn't have expected that some random trash solution will get AC on the problem F, don't you? :)
•  » » » » 13 months ago, # ^ |   +20 you wouldn't have expected that some random trash solution will get AC on the problem F, don't you? Yeah yeah, it'd be ridiculous if some random trash passed F. G is another story, of course, in G there can be everything, but in F only good proven solution must pass, obviously.
 » 13 months ago, # |   +8 So many constructive and greedy problem!
 » 13 months ago, # |   +8 any hints to b plzz??
 » 13 months ago, # |   +4 How to solve B?
•  » » 13 months ago, # ^ |   +10 Greedy. Fix the number of canceled flights from the first set (A to B) and then check what the earliest time we can go from B to C with binary-search/lower_bound is.
•  » » 13 months ago, # ^ |   +3 Suppose you cancel the first x flights from A to B. That means Arkady will take flight x+1 from A to BDoing a binary search on b you can get the first available flight from B to C. But since you have only canceled x flights, you can cancel the next k-x flights, forcing Arkady to take later flights. Then you can now whats the earliest that Arkady can get to C.You can do that for every x<=k
•  » » 13 months ago, # ^ |   +3 Can solve using two pointers too instead of binary search! Here's my code
 » 13 months ago, # |   +9 I would like to ask in problem C, how low can the amount of swaps allowed be, so there would still be a solution for every possible permutation?
 » 13 months ago, # |   +3 Problem C:You can solve this task in less than 3*n moves is this true?Problem D: You partition the pairs into two sets: Set A: (pair.left < pair.right) Set B: (pair.left > pair.right)You cannot use elements from both sets because of the following Suppose you use an element from set A then you have ....pair.left(A) < pair.right(A)now if you want to append an element from set B you get.....pair.left(A) < pair.right(A) > pair.left(B) > pair.right(B) --> not possible or.... pair.left(A) < pair.right(A) < pair.left(B) > pair.right(B) --> not possible
•  » » 13 months ago, # ^ |   -15 Problem C: You can solve this task in less than 3*n moves is this true? No.
•  » » » 13 months ago, # ^ |   +8 Could you please tell me what the minimum number of moves required is then?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   -23 Near 5*n in worst case.
•  » » » » 13 months ago, # ^ |   +3 54945437 solution with at most 4*n (no idea how it works)
•  » » » 13 months ago, # ^ | ← Rev. 2 →   -21 Yes Enumeration sort can be used and you will need at most n operations to sort.
•  » » » » 13 months ago, # ^ |   0 No, because we have condition: take two indices i and j such that 2⋅|i−j|≥n and swap pi and pj
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   +5 Okey thanks!
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +5
•  » » 13 months ago, # ^ | ← Rev. 2 →   +4 I solved C taking less than 3*n moves. code
•  » » » 13 months ago, # ^ |   +4 At first your code looked like maggi (Noodles) :D .
•  » » » » 13 months ago, # ^ |   +1 busy to solving problems, I forgot using function XD
•  » » 13 months ago, # ^ |   0 So, the answer to the first question is, YES. In my code the operation works within 3n times.
 » 13 months ago, # |   +55 The worst feeling in life: Waiting main tests with unproven random solution for F.
 » 13 months ago, # | ← Rev. 2 →   +7 How could this solution get TLE 12? Just because of slow output? Thanks in advance.
•  » » 13 months ago, # ^ |   +16 too many flushes. try without endl perhaps
•  » » 13 months ago, # ^ |   +3 Alex's right: 54950010
 » 13 months ago, # | ← Rev. 33 →   -34 it's my cake day so can i get 7 upvotes please
 » 13 months ago, # |   +38 Problem C was great, very enjoyable to solve.
•  » » 13 months ago, # ^ |   +3 What was your approach to solve C ? Please help! as I couldn't get it.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +1 Here is how to perform a swap between two indeces a and b in at most 5 moves:-1. Just a and b if they're far enough-2. Swap a with it's opposite side (1 or n)-3. Swap a with b now if possible, and undo step 2-4. Swap a with other side (1 or n, the one which hasn't been used yet)-5. Now you can definitely swap a and b, so swap those, and undo steps 4 and 2
 » 13 months ago, # | ← Rev. 3 →   +10 The difficulty gap between problem F and G. It was good for the other colors, but it was bad for reds.
•  » » 13 months ago, # ^ |   +129 And the new one:Good enough, I think.
 » 13 months ago, # | ← Rev. 2 →   +16 I felt q(D) easier than q(C). Is there anyone who felt same ?
•  » » 13 months ago, # ^ |   +2 I felt the same, and there's my comment like yours in the middle of comments.
•  » » 13 months ago, # ^ |   +3 I did
 » 13 months ago, # |   +18 If mnbvmar did not get a hack in the last five minutes tourist was likely to have a new personal best rating.
•  » » 13 months ago, # ^ |   +7 Yes, Really interesting in the last minutes.
•  » » » 13 months ago, # ^ |   +13 Codeforces' best rating *
 » 13 months ago, # |   0 Problem G would be pretty cool if the graph was given. That shit with bitsets ruined it.
•  » » 13 months ago, # ^ |   +37 Author's solution doesn't use bitset.
•  » » 13 months ago, # ^ |   +10 We think that it is easier to write incorrect solution in this case, because an efficient test requires $O(N^2)$ edges, therefore, number of vertices must be $\leq 1000$. So, we have decided to make this version with $10^5$ vertices.
 » 13 months ago, # |   +26 Why so many people use random algorithms to pass F?Are they really correct?
•  » » 13 months ago, # ^ |   0
•  » » » 13 months ago, # ^ |   +14 But later it turned out that it caused so many FSTs
 » 13 months ago, # |   +27 System Testing hasn't started; when will it start?
•  » » 13 months ago, # ^ |   0 started
•  » » » 13 months ago, # ^ |   +3 Oh, I see.
 » 13 months ago, # |   0 What's the upper-bound on number of operations in prbE.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I think n — 1, when the last one have to move to left n — 1 steps, and each of the rest have to move right 1 step.
 » 13 months ago, # |   +2 What if in C we had to minimize the number of operations?
 » 13 months ago, # | ← Rev. 2 →   0 Any specific reason why submission 54926688 for B fails on pretest 8 ?Is the general solution using two pointers wrong or have I missed an edge case?Thanks in advance.
 » 13 months ago, # |   +115 Codeforces Global Failed System Test Round .
•  » » 13 months ago, # ^ |   +14 Never have seen so many FSTs in my life.
•  » » » 13 months ago, # ^ |   0 Me either
•  » » » » 13 months ago, # ^ |   -33 Because you are newfags.When Codeforces just started, every round was with weak pretests, and it was funny, and everyone was happy.There is nothing better than laughing at a friend who failed systests.It is so boring when there is no hacks and no solution fails systests.
•  » » » » » 13 months ago, # ^ |   +30 We are definitely playing different games
 » 13 months ago, # |   +43 There are literally 5 times more failed on main tests submission for F than Accepted.
 » 13 months ago, # |   +8 Could somebody take a look at C 54937652? I have an O(n) solution that is getting TLed. Is this intended?
•  » » 13 months ago, # ^ |   +5 Don't use endl. It flushes the output stream, and this problem has a large amount of output.
•  » » » 13 months ago, # ^ |   -8 Even if you're right, I saw codes worse than this one (using endl and not the optimization sync_with_stdio) who passed system tests... Looks unlucky to me, maybe you're very very close to the time limit...
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   -6 Hope there would be a system retest.. Like take a look at test 12 -- it's also n = 300000 and has <3000ms running time. Great disappointment.
 » 13 months ago, # |   +9 This contest be like: Pretests: Calculate 2+2 Main tests: The train goes 80 km/hours and you are writing programs. Calculate the mass of sun.
•  » » 13 months ago, # ^ |   +47 Is this a test that _kun_ came up with?
 » 13 months ago, # |   +181 The most accurate description of pretests:
•  » » 13 months ago, # ^ |   0 Sad for Vn_nV
•  » » » 13 months ago, # ^ |   0 first time see -300+ sad for him
•  » » » » 13 months ago, # ^ |   0 -389 if to be accuracy
•  » » 13 months ago, # ^ |   0 I remember him, he got +400 on predictor when I checked leaderboard
•  » » » 13 months ago, # ^ |   0 What is predictor?
•  » » » » 13 months ago, # ^ |   +3
 » 13 months ago, # |   +8 Problem C. Same code, replacing endl with \n. TLE with endl 54949525, Accepted, 452 ms with \n 54949838. This is awful :(
•  » » 13 months ago, # ^ |   0 Same thing, absolutely.
•  » » 13 months ago, # ^ |   +7 Endl flushes the output in addition to outputting new line, so it's slower. At least you won't make the same mistake again :)
 » 13 months ago, # |   -8 https://codeforces.com/contest/1148/submission/54936686. how it can be ml 38?! help me please
•  » » 13 months ago, # ^ |   +5 2 3 3 2 4 Try this
•  » » » 13 months ago, # ^ |   0 thank you very much)
 » 13 months ago, # |   +12 Actually problem F can be solved in various ways . Including good-look random and check all 2^n and 2^n-1 then random. here
•  » » 13 months ago, # ^ |   +10 good-look random (×)randomize random (√)
•  » » 13 months ago, # ^ |   0 How does the first one pass?
•  » » » 13 months ago, # ^ |   0 now it cannot pass...
•  » » » 13 months ago, # ^ |   0 +1 to this questionWhy did it pass test 15?
»
13 months ago, # |
+41

As usual, we used the following two files to determine tshirt winners:

get_tshirts.py
randgen.cpp

And the tshirt winners are:

List place Contest Rank Name
1 1148 1 mnbvmar
2 1148 2 tourist
3 1148 3 Petr
4 1148 4 yutaka1999
5 1148 5 LHiC
6 1148 6 Egor
7 1148 7 ksun48
8 1148 8 sunset
9 1148 9 krijgertje
10 1148 10 kczno1
11 1148 11 RNS_CUS
12 1148 12 betaveros
13 1148 13 ATS
14 1148 14 Reyna
15 1148 15 zeliboba
16 1148 16 khsoo01
17 1148 17 stO
18 1148 18 ainta
19 1148 19 Shanru
20 1148 20 Hazyknight
21 1148 21 zzq_IOI2019_AK
23 1148 23 gisp_zjz
24 1148 24 renjingyi
25 1148 25 Alex_2oo8
26 1148 26 whzzt
27 1148 27 lumibons
28 1148 28 komendart
29 1148 29 scanhex
30 1148 30 receed
53 1148 53 Noam527
55 1148 55 KrK
97 1148 97 lintoto
107 1148 107 RobeZH
110 1148 110 Motarack
140 1148 140 darkkcyan
146 1148 146 GoGooLi
151 1148 151 Gassa
152 1148 152 Pigbrain
162 1148 162 J.J.T.L.
231 1148 231 socketnaut
272 1148 272 RCG
305 1148 305 Cinro_9baka
324 1148 324 Wechselhau
330 1148 330 Daniel_Yeh
353 1148 353 Gullesnuffs
380 1148 380 robertthethirtieth
406 1148 406 joon
460 1148 460 fastle233
497 1148 496 Juney

Congratulations!

•  » » 13 months ago, # ^ |   +44 WOW! Never expected this to happen! How can I receive the prize?
 » 13 months ago, # |   +16 Why you rejudge some submissions even after the rating calculation?
•  » » 13 months ago, # ^ |   0 I hope that I rejudged only a couple of upsolving submissions. I added a test from the comment above and wanted to check it. Why not?
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +8 Okay. I think it better not to recalculate ratings. And you may do it in system test phase next time.By the way, MikeMirzayanov why don't CF release an open hack system like uoj?
•  » » » » 13 months ago, # ^ |   +22 Of course we are not going to recalculate ratings/change standings/anything. egor.lifar only rejudged practice submissions.
•  » » » » » 13 months ago, # ^ | ← Rev. 4 →   +8 In fact, you rejudged contest submissions, changed standings without recalc ratings. Now it looks really confusing xDDo you find anything strange in the image?
 » 13 months ago, # |   -132 This is the worst round I have ever seen. Terrible pretests. Problem writers made it purposely weak. Makeing bad pretests doesn't show the skill of the participants. I will never participate in these problemsetter's round. I made well in the contest, ended up losing a lot because of the stupid pretests. If you feel disapointed too, downvote the contest! (By a red user with fake account).
•  » » 13 months ago, # ^ |   +68 You sure care a lot about a round you didn't compete in.
•  » » » 13 months ago, # ^ |   +33 I can say it not from fake account. I don't even know why people create fake accounts to show their opinion. Afraid of downvotes? I just got sad because of increadibly weak SYSTESTS on F and G.How can this solutions even pass? That's so disappointing. It is the first wrong shitty idea, that you can come with. How is it possible to not test this out? Is that what meant in announcement by "8 tricky tasks for you"? That we must guess the tests? Or sorting by comparator and writing greedy algorithm on 2 pointers are "tricky" maybe?I didn't compete in first 2 rounds, but I already heard opinions that they were incredibly bad. I will for sure not participate in next global rounds, because in my opinion there are enough bad samples to not do it.By the way, why the round from XTX-markets is not prepared by XTX-markets employers if they are looking for people from CP community? Isn't that illogical? I wonder how many qualified high-rated people will they get after these rounds.
•  » » » » 13 months ago, # ^ |   0 Now I'm glad I missed registration by seconds and didn't feel confident enough to try with extra registration.
•  » » » » 13 months ago, # ^ |   +10 There will be many accepted submissions (without proof) if they include up to 20 pretest.
•  » » » » » 13 months ago, # ^ |   +61 I don't care about pretests weakness. Systests must be strong enough to cut out shitty solutions.
•  » » » » » » 13 months ago, # ^ |   +8 Here another accepted solution that gives wrong results for the test case: 6 3 49 25 25 6 2 3 
•  » » » » » » » 13 months ago, # ^ | ← Rev. 3 →   0 By the time this solution was accepted, I also thought that the test data for this problem was a little weak:D
•  » » » » » » » 13 months ago, # ^ |   0 Added your test for the upsolving, thanks!
•  » » » » 13 months ago, # ^ |   +43 How can this solutions even pass? That's so disappointing. It is the first wrong shitty idea, that you can come with. Hmm, it was your third attempt and it was after the contest... Is that what meant in announcement by "8 tricky tasks for you"? That we must guess the tests? Or sorting by comparator and writing greedy algorithm on 2 pointers are "tricky" maybe? Problem F had an author's solution with induction, which I can call tricky. Also, problems G and H both had a deterministic solution without any random.Of course, it's not ok that such solutions pass systests. But in such problems like F or G there can be a very huge amount of strange unintended solutions and it's very complicated to create tests against all of them. In my opinion, weak pretests enable such tasks to exist. Maybe we should have warned about it in the announcment to make system testing not such disappointing.
 » 13 months ago, # |   -61 I think this contest is really hard and unbalaced contest. I think that there should be more easy questions in the contests.
 » 13 months ago, # | ← Rev. 7 →   -25 Codeforces Globle Fail System Test Round 3
 » 13 months ago, # |   +11 Why is there no one asking for editorial?
 » 13 months ago, # |   +6 Isn't Codeforces even try full feedback contests? Many other websites already use full feedback. Why does Codeforces use this system?
•  » » 13 months ago, # ^ |   +26 Why not?
 » 13 months ago, # |   -75 following is my code to the 2nd ques Born this way. I dont know about the correctness as I was getting Runtime error for the 1st TC. However the other two passed in the custom invocation.Please tell me whats the problem here. int main() { ll n,m,ta,tb,k; cin>>n>>m>>ta>>tb>>k; multiset s1,s2; for(int i=0;i>x; x = x+ta; s1.insert(x); } for(int i=0;i>x; s2.insert(x); } ll c = 0; multiset::iterator it,temp; for(it=s1.begin();it!=s1.end();it++) { ll x = *it; auto f = s2.lower_bound(x); if(f!=s2.end()) { temp = it; s1.erase(temp); s2.erase(f); c++; } if(c>=k) { break; } } ll ans=-1; for(it=s1.begin();it!=s1.end();it++) { ll x = *it; auto f = s2.lower_bound(x); if(f!=s2.end()) { ans = *f+tb; break; } } cout<
•  » » 13 months ago, # ^ |   0 Don't try to erase and iterate through the same container at the same time. Instead use another container with the same contents as of the one which you would like to modify and do further implementation with that dummy container
•  » » 13 months ago, # ^ |   +5 Please use spoiler tags to share your code, or use a link, it makes it difficult to scroll through the comments if a long code is posted.
 » 13 months ago, # | ← Rev. 2 →   0 Can anybody please help to point out where I am going wrong in problem B it failed on 8th pretest Using the first flight from A to B I find the first flight from B to C using binary search . Now I have two options to cancel the flight a. Cancel the flight from A to B and use the next Flight from A to Bb. Cancel the flight I found by binary search and choose the next flight from B to C I find the time to reach C and which option between the above two gives higher value I go with that. If in this process the next flight from B to C cannot be chosen I print -1.
•  » » 13 months ago, # ^ |   +3 We can cancel atmost k flights. Start with value i=0 to i=k. Every time you will cancel i flights in A and You have to cancel k-i flight in B which firstly Available. n=10 m=10 t1=1 t2=1 k=3 A= 1 2 3 4 5 6 7 8 9 10 B= 3 4 5 6 7 8 9 10 11 12 If i=0 You have to cancel k flight in B which available for a [0] Every time you have to do same. I hope you got me.
•  » » » 13 months ago, # ^ |   0 I got your approach,It's fine. but what 's wrong with mine?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Your code is hard to read and I think you are missing out on some details.You need to sort the A_flights. and when you are checking for the i'th flight in A_flights array you need to make sure that flights 1 to i-1 in the A_flights array are also cancelled.(you are probably not doing this) now you can cancel (k -(i — 1)) flights from B_flights. (B_flights is again sorted). This you can do using binary search. You need to make sure of the following:You do not need to cancel flights in B_flights if the starting time is before the starting time in A(current flight whatever you are checking).i.e you do'not need to cancel flights: starting_time(B_j) < starting_time(A_i).If you are doing all this then the fault lies in your implementation.
 » 13 months ago, # |   0 First and foremost thing is to read problem statement carefully and see examples. For problem B, i did not at all read problem statement correctly and almost ended up in solving another variant of problem B which according to me , somehow is not straightforward, variant of which is Arkady minimises the wait time between two flights from A to B and B to C and I maximise this time after cancelling at-most k flights . Wait time here is same as flight overlay time. eg .A(start from city A) = 1, 3 , 4 , ta = 1,B(Start from city B) = 2, 6 , 7 , tb = 1 .Then arrival at B are 2,4,5 . So if K=2, we can cancel flights from original A where start time = 1,4 so that max wait time is between flight A = 3 to B = 6 and ans = 2; please note here there would be no use of tb. I ended up in solving this , to only learn at last moment this was not asked :(
 » 13 months ago, # |   +45 Editorial?
 » 13 months ago, # | ← Rev. 2 →   -52 abc
 » 13 months ago, # |   +18 Editorial??
 » 13 months ago, # | ← Rev. 2 →   0 Can anyone please check my following submission for Problem B and figure out what's wrong with it? I got a runtime error on test case 9, and my logic seems to be working fine for all cases I'm dry running it for. Thanks in advance! :) https://codeforces.com/contest/1148/submission/54942140
•  » » 13 months ago, # ^ |   0 There is no boundary check for j in here:  while(b[j]
•  » » » 13 months ago, # ^ |   0 Thank you. Finally submitted it successfully! :)
 » 13 months ago, # |   +25 How to solve G？ Or can anbody give me some hint for how to use gcd（ai，aj）>0 and 2k<=n?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +8 Find a spanning forest of the compliment graph. In the compliment graph if there are more than n/2 components then we have an n/2 clique in original graph. Else we can choose nodes only from components with size >=2 such that we take atleast 2 from each component we choose( can be proved that it is always possible to choose for any k st 6<=2k<=n ). In this set every vertex has an edge in the compliment graph, and hence this set is antifair.For finding the components, bitsets can be used to get a complexity of O( n^2 * MAXP /64) where MAXP is the max number of prime divisors of a number.
 » 13 months ago, # |   0 Oh,it's not very good to the participants who cannot submit any code in the first 10min like me... and I was sad when I saw that the score I got on each problem is less than the score 5min ago a lot after I submit each problem...(and I just need 3 point to go to the red! I wish I can get a red account in the next round...) All in all, it's a not bad contest, although it need "a lot of" constructive algorithms and basic tricks in the problem from A to E. F is an amazing problem with short words, but I can't solve it. Can anyone help me with it?
 » 13 months ago, # |   0 Can Someone explain how to solve C.
•  » » 13 months ago, # ^ |   0 Try order the array begining from the numbers that need to be at middle, so that, we can use the positions 1 and N of array to make swaps.If a number cant go to its right position, we can keep swaping it with position 1 or N until it can be placed to the right position.N = 8, order of verifications: 4, 5, 3, 6, 2, 7, 1, 8Ps: my english is not that good.
 » 13 months ago, # |   -8 just curious why problem F is named Foo Fighters
•  » » 13 months ago, # ^ |   +12 Because both Foo and Fighters start with F.
 » 13 months ago, # |   0 54973406 My submission is Accepted after contest, but it's actually wrong. For instance, when get such inputs 6 3 18 75 245 847 1859 26 it outputs 6 5 4 
•  » » 13 months ago, # ^ |   +10 Added your tests into the upsolving, thanks!
 » 13 months ago, # |   0 Did anyone's randomized solution for F pass the systests ?
 » 13 months ago, # |   +25 Editorial?, opening Codeforces after every 10 minutes just to see if editorial has been released.:-|
 » 13 months ago, # |   0 Solution for G that got accepted: 54972721 How??
•  » » 13 months ago, # ^ |   0 I call that phenomenon "Let's create 150 random tests and not write shitty solutions to test their strength"
 » 13 months ago, # |   +20 Editorial for this contest please.
 » 13 months ago, # | ← Rev. 2 →   +3 I made a silly bug in F and still got accepted 55273526, so I scanned through the first page of standings and successfully hacked an accepted deterministic solution. 54935870 egor.lifar Can you add these testcases to upsolving testcases? 3 0 1 -1 2 -1 3  3 0 1 1 2 1 3  3 0 2 1 1 1 3  3 0 2 -1 1 -1 3 
•  » » 13 months ago, # ^ |   0 Thank you! Added them.
 » 8 days ago, # |   0 Problems similar to Problem C, Crazy Diamonds 432C - Prime Swaps (Almost same statement) 1365B - Trouble Sort It is interesting to note that this "temp variable" idea is repeated, and with each repetition the rating of the problem drops.