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 Jatana. We are glad to say that we have prepared 8 tricky tasks for you. We hope you will enjoy them!
Thanks to KAN and cdkrot for the help with coordinating the round, and cookiedoth, Lewin, voidmax, 300iq, Aleks5d, Learner99, Jeel_Vaishnav, arsijo, KAN, Ashishgup, AlexFetisov, vintage_Vlad_Makeev 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:
Another rated round after a long break! Yeah!
Hope it will be a balanced contest. Not like the previous one :)
Fortunately the wish came true. Good problemset!
IMHO bad problemset
deleted :(
Where is the number of problems and score distribution?
It will be posted not long before the contest starts, maybe.
(It is posted just two minutes before starts.)
Hope everyone can have a good performance! (and hope I can get red again)
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!
I'm interested in XTX Markets job but are they interested in me XD ? (I know the answer don't tell me)
I like global rounds (I didn't entered any of them)
Ok, ok I deserved it (-52)
Do global rounds support hacking? if yes then, during or after the contest?
During the contest of course, just like in regular rounds.
Are there remote jobs at XTX Markets?
Here we go!!
How many problems will be shown
eights
1.. 3.. 5.. 7.. 9.. Finally!! the contest season is back!
hopes this contest will bring happiness in our life
happiness is a state of mind.
round will be rated for those who have not solve anything?
If you do not make a single attempt, it won't be rated for you. Otherwise it will be.
Why you don't thanks MikeMirzayanov for amazing systems Codeforces and Polygon! ?
LOL what an attempt to get free upvotes
Why I was told that too many request and couldn't submit my code?
JOJO's Bizarre Adventure? That's pretty cool!
This comment has been edited and I sincerely apologize for my lack of knowledge about this great anime
Still cannot believe I lost this round...
Is this a JoJo reference ?
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!
Problem D was easier than Problem C. Am I the only one who felt that way?
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.
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.
What is the trick?
I can't think anything as a trick. Is it "if $$$|i-j|*2>=n$$$ then $$$|i-j|>=n/2$$$"?
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.
I don't know how you used that in this problem but I don't see any similarity.
Oppositely I thought E was easier than D.
Weird flex, but D was extremely hard for me, lol
Did we have to use the fact that
every integer from 1 to 2⋅n is mentioned exactly onceanywhere 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.No, see my solution 54947377 Hopefully it would be correct, coded it in the last few minutes
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:(a<b)
Note:All are distinct so they will not be equal
Then the part which has more pairs will be the answer
If part 1 has more elements then the answer will be the pairs sorted in increasing order of first element. (a1>b1b2) 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.
i felt is was easier than B also.
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.
Regarding problem F, is it true that there will always exist at least one $$$s$$$ with not more than $$$2$$$ bits being set? :O
My solution only checked for those (and their compensation, just in case) and got Pretest passed :O
UPD: It did fail at test 49. GG. :D
UPD2: My source code was actually screwed up a bit. Still AC after fixing some bugs and optimizing a bit. ;) (54974178)
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.
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. :)
How to solve F?
Maintain sum and try to randomly switch bits?
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).
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:
10 0 45 -1 11 -1 21 -1 45 0 6 -1 51 0 19 0 40 0 60 0 51
Try this test case:
262144
1 131072
1 131073
1 131074
...
1 393215
The only answer is $$$393216+524288*k$$$.
Wow, incredible. :)
amazing. how did you get this?
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-1will counter such solutions.The systest of F still looks surprisingly weak as of now, which is strange.
How to solve E?
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$$$.
How about changing stack to queue?
I think I have implemented algo like that, but I got WA.
I thought so during the contest, but probably no...
ok, then it still yes, I guess :)
But, I think my submission 54936636 did something like yours.
Oh! I found a stupid mistake.
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.
what the hell is pretest 14 on E ?
Something like this maybe? I got WA on 14 until I fixed this case
yeah. That works. Thanks. Forgot to pair j with the max i, instead put min i, which lead to wrong solution.
Too greedy contest
Problem H proved once again that Za Warudo's true power is, indeed, the power to reign over this world
Can someone please give hints for question: C. Crazy Diamond.
Consider how to use no more than $$$5$$$ swaps to move number $$$i$$$ to position $$$i$$$.
Hi! Im sorry I still did not understand it, can you or anyone please explain it. tia!
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.
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.
That is also fine. (Although I didn't think of that way during the competition.)
2 should >=
I was not able to deal with the 5th case . :(
Too Greedy Contest, the setters want to steal our rating :(
what is pretest 14 in problem E? why this code gets WA? 54943503
I also had this problem. I think we need to add d=min(d, (s[j] — s[i])/2)
Your code will fail on tests like
Your code gives the output "NO" but the correct output will be "YES"
here^ is one of the suitable output for the above test case
Please tell me problem F is not about trying different $$$s(hit)$$$ randomly...
(retracted my previous claim; turns out there are counter tests)
Why tf it's div. 1 F then...
Don't forget about Div.2 people :)) It's combined!
System test haven't started yet. I think they're trying to make that test :)
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.
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.
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
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).
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?
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.
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.
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.
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->61
Let the sum of all the values with current_bit as the highest set bit be current_sum
Now, 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.
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.
This argument is so elegant.
I think that tourist's solution is not that kind of solution.
10 seconds too slow to submit correct F :(
Too slow :(
Did somebody find a counter-test that makes random solution fail on problem F?
There's no such thing!!
WTF!!
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.
He didn't lock problem F, so...
I know that my F is in big danger. I was just joking. Deep inside I am afraid of losing it.
Yep, cdkrot found some about a week ago :)
Cool! I hoped there were. How would one construct such a test case?
https://mirror.codeforces.com/blog/entry/67316?#comment-515034
I 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:
I tried extending it to higher n and succeeded.
It's very brave not to put that test in pretests, given the fact that people complain about weak pretests each time.
What should they be scared of?
of people disliking the round
Huh, but it's not the case when you don't pass systests due to some silly error. This one here is pretty essential...
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.
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.
xd
One 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.
There's surely no point in catching all such solutions, otherwise there would be nothing to hack.
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.
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.
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?
As I said, the issue is that it's a hard problem that almost nobody in the same room will solve.
If tests are weak, people complain about weak pretests. If tests are strong, more people solve F, so people complain about difficulty distribution. :)
Could you also add that test case by dorijanlendvaj to upsolving testcases? It seems to break even more solutions.
Done
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:
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? :)
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.
So many constructive and greedy problem!
any hints to b plzz??
How to solve B?
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.
Suppose you cancel the first x flights from A to B. That means Arkady will take flight x+1 from A to B
Doing 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
Can solve using two pointers too instead of binary search! Here's my code
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?
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
Problem C: You can solve this task in less than 3*n moves is this true?
No.
Could you please tell me what the minimum number of moves required is then?
Near 5*n in worst case.
54945437 solution with at most 4*n (no idea how it works)
Yes Enumeration sort can be used and you will need at most n operations to sort.
No, because we have condition:
Okey thanks!
No.
Yes.
https://mirror.codeforces.com/contest/1148/submission/54929490
I solved C taking less than 3*n moves. code
At first your code looked like maggi (Noodles) :D .
busy to solving problems, I forgot using function XD
So, the answer to the first question is, YES. In my code the operation works within 3n times.
The worst feeling in life: Waiting main tests with unproven random solution for F.
How could this solution get TLE 12? Just because of slow output? Thanks in advance.
too many flushes. try without endl perhaps
Alex's right: 54950010
it's my cake day so can i get 7 upvotes please
Problem C was great, very enjoyable to solve.
What was your approach to solve C ? Please help! as I couldn't get it.
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
The difficulty gap between problem F and G. It was good for the other colors, but it was bad for reds.
And the new one:
Good enough, I think.
I felt q(D) easier than q(C). Is there anyone who felt same ?
I felt the same, and there's my comment like yours in the middle of comments.
I did
If mnbvmar did not get a hack in the last five minutes tourist was likely to have a new personal best rating.
Yes, Really interesting in the last minutes.
Codeforces' best rating *
Problem G would be pretty cool if the graph was given. That shit with bitsets ruined it.
Author's solution doesn't use bitset.
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.
Why so many people use random algorithms to pass F?
Are they really correct?
https://mirror.codeforces.com/blog/entry/67316?#comment-515010
But later it turned out that it caused so many FSTs
System Testing hasn't started; when will it start?
started
Oh, I see.
What's the upper-bound on number of operations in prbE.
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.
What if in C we had to minimize the number of operations?
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.
Codeforces Global Failed System Test Round .
Never have seen so many FSTs in my life.
Me either
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.
We are definitely playing different games
There are literally 5 times more failed on main tests submission for F than Accepted.
Could somebody take a look at C 54937652? I have an O(n) solution that is getting TLed. Is this intended?
Don't use endl. It flushes the output stream, and this problem has a large amount of output.
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...
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.
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.
Is this a test that cdkrot came up with?
The most accurate description of pretests:
Sad for DearMargaret
first time see -300+ sad for him
I remember him, he got +400 on predictor when I checked leaderboard
What is predictor?
CF Predictor
Problem C. Same code, replacing endl with \n. TLE with endl 54949525, Accepted, 452 ms with \n 54949838. This is awful :(
Same thing, absolutely.
Endl flushes the output in addition to outputting new line, so it's slower. At least you won't make the same mistake again :)
https://mirror.codeforces.com/contest/1148/submission/54936686. how it can be ml 38?! help me please
Try this
thank you very much)
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
good-look random (×)
randomize random (√)
How does the first one pass?
now it cannot pass...
+1 to this question
Why did it pass test 15?
As usual, we used the following two files to determine tshirt winners:
And the tshirt winners are:
Congratulations!
WOW! Never expected this to happen! How can I receive the prize?
in the cpp source code, what is "testlib.h" ?
Why you rejudge some submissions even after the rating calculation?
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?
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?
Of course we are not going to recalculate ratings/change standings/anything. Egor.Lifar only rejudged practice submissions.
In fact, you rejudged contest submissions, changed standings without recalc ratings. Now it looks really confusing xD
Do you find anything strange in the image?
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).
You sure care a lot about a round you didn't compete in.
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.
https://mirror.codeforces.com/contest/1148/submission/54952521 https://mirror.codeforces.com/contest/1148/submission/54950156
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.
Now I'm glad I missed registration by seconds and didn't feel confident enough to try with extra registration.
There will be many accepted submissions (without proof) if they include up to 20 pretest.
I don't care about pretests weakness. Systests must be strong enough to cut out shitty solutions.
Here another accepted solution that gives wrong results for the test case:
By the time this solution was accepted, I also thought that the test data for this problem was a little weak:D
Added your test for the upsolving, thanks!
Hmm, it was your third attempt and it was after the contest...
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.
I think this contest is really hard and unbalaced contest. I think that there should be more easy questions in the contests.
Codeforces Globle Fail System Test Round 3
Why is there no one asking for editorial?
Isn't Codeforces even try full feedback contests? Many other websites already use full feedback. Why does Codeforces use this system?
Why not?
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.
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
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.
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 B
b. Cancel the flight I found by binary search and
choose the next flight from B to C
If in this process the next flight from B to C cannot be chosen I print -1.
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.
Editorial?
Editorial??
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://mirror.codeforces.com/contest/1148/submission/54942140
There is no boundary check for j in here:
Thank you. Finally submitted it successfully! :)
How to solve G？ Or can anbody give me some hint for how to use gcd（ai，aj）>0 and 2k<=n?
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.
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?
Can Someone explain how to solve C.
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, 8
Ps: my english is not that good.
just curious why problem F is named Foo Fighters
Because both Foo and Fighters start with F.
54973406 My submission is Accepted after contest, but it's actually wrong. For instance, when get such inputs
it outputs
Added your tests into the upsolving, thanks!
Did anyone's randomized solution for F pass the systests ?
Editorial?, opening Codeforces after every 10 minutes just to see if editorial has been released.:-|
Solution for G that got accepted: 54972721 How??
I call that phenomenon "Let's create 150 random tests and not write shitty solutions to test their strength"
Editorial for this contest please.
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?
Thank you! Added them.
Problems similar to Problem C, Crazy Diamonds
It is interesting to note that this "temp variable" idea is repeated, and with each repetition the rating of the problem drops.