Codeforces Global Round 14
source link: https://codeforces.com/blog/entry/90194?f0a28=1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
On Sunday, May 2, 2021 at 14:35UTC, we will host Codeforces Global Round 14.
This is the second round of the 2021 series of Codeforces Global Rounds. The rounds are open and rated 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 2021:
- 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.
Thanks to XTX, which in 2021 supported the global rounds initiative!
All problems were written and prepared by me FieryPhoenix and dragonslayerintraining.
Huge thank you to everyone who made this round possible:
You will have 3 hours to solve 9 problems. Scientific studies have shown irrefutable evidence that upvoting this blog and participating in this round will lead to longevity and happiness. GLHF!
UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3500 — 4250 — 5000
UPD: Editorial is here!
UPD: Congratulations to the winners!!
19 months ago, # | PurpleCrayon orz! |
19 months ago, # | Scientific studies have shown Global Round are usually hard, but I will participate for longevity and happiness. |
19 months ago, # | As a tester, there's a reason this round is a Global Round (cf's flagship contest). The statements are natural and concise, the problems are elegant, and I hope you have a great round! |
-
PurpleCrayon orz
-
PurpleCrayon Skittles orz
-
PurpleCrayon Skittles Lunchbox orz
-
PurpleCrayon skittles lunchbox izhang orz
-
PurpleCrayon skittles lunchbox Izhang moo. orz
-
I know a geniosity when I see one. PurpleCrayon orz!!!!!!!!!!!!!!!!
-
-
-
-
-
19 months ago, # | sto PurpleCrayon orz |
Relatable >_< |
19 months ago, # | omg, a round prepared by the Americans with Chinese names |
19 months ago, # | Global Rounds always provides a very good opportunity to boost up your rating... Excited!!!! |
-
lol no. for the same performance you get much more rating in div2 than in global/div1. Not that it should matter but that's not the point here.
-
It may vary from individual to individual depending on the topics in the round for example.
However in general for the same performance you get the same rating. That's the whole point of ELO.-
I can barely get any positive delta if I solve A,B,C in Div.1, whereas in Div.2 Solving up to E once made my rating go as high as 2255.
-
First, from your history, you never ever solved A-B-C in div.1 only rounds, so I don't quite get what you're talking about
Also when you got your 2255, you had rank 8, there were only seven "violets" who performed better. Just compare it to your performance in div.1 rounds
-
-
ELO system is not perfect. It makes very simplistic assumptions about the estimated probability of one player beating the other, based on just a single number (player's rating score). My understanding is that if rating scores of players are very far apart, then ELO based predictions become much less accurate. And isn't this the primary reason why division based restrictions exist?
Anyway, all of this can be probably confirmed or debunked by just re-calculating rating score updates of div.2 contests without filtering out the normally non-rated people with 2100+ rating. My guess is that it would be a bad news for the rating scores of weaker participants. But of course I may be wrong.
-
-
19 months ago, # | As a tester, unfortunately, I don't have any witty joke to write in this message. |
Can't we participate from m1.codeforces.com or m2 or m3? I couldn't find this contest on any of these versions of codeforces. UPD: Its added. Thanks. |
19 months ago, # | |
19 months ago, # | Omg 5000 points for a problem. Focus on the last problem, problem I with 5000 points, that's enough. :D |
19 months ago, # | Are the two contest authors related? |
19 months ago, # | What is ORZ, I've seen it in many comments. |
Me, a football lover coder today |
19 months ago, # | This round has extremely strong pretests. |
19 months ago, # | First contest in isolation! I hope I have the energy to compete. #COVID_coders |
19 months ago, # | Scientific studies have shown irrefutable evidence that upvoting this blog and participating in this round will lead to longevity and happiness 1000 people : wow we will upvote! |
19 months ago, # | |
19 months ago, # | wer retin chains ? |
19 months ago, # | Is it only me who can't do anything for 1 hour before the contest and keep switching between different tabs until it starts? |
19 months ago, # | There is a long queue, about 4 pages show only "running". Would that affect the round? |
19 months ago, # | My first Global Round,nervous. |
19 months ago, # | My rating after this global round going down like Wheeeeeeeeee |
19 months ago, # | I upvoted the blog and participated. I guess the scientific studies and their evidences for longevity and happiness are wrong :( |
19 months ago, # | I wonder if D is that easy felt like a normal C |
-
I worked like two hours on d but didnt get it :/
-
it happens sometimes i can't solve an A problem even so more like 11000 solved it that's weird and I thought so hard and still didn't get it XD
-
Yeah man, your rating graph and game is truly inspirational! (y)
-
it will be better trust me I had a hard time and couldn't learn anything new for like 2 years and a half but now things really changed
-
-
-
Well here's what i did for pretests(don't know if it will pass or not)-
if $$$l==r$$$ then count how many numbers are same in both $$$l$$$ array and $$$r$$$ array call this count and answer would be $$$ans = r - count$$$
if $$$l!=r$$$ then we are sure we need to shift $$$abs(l-r)/2$$$ elements from larger array to smaller array to make size equal, add it into the ans and now before shifting we will first remove those numbers from both the arrays which are same (as shifting them would cost an additional money to change the color) after this we shift those elements from larger array first that are similar to each other so that 1 copy of that element stays in larger array and 1 copy in smaller array and we don't need to spend additional money to change the color, even after this if elements are not same we will change their color and add it into the answer.
consider this-
14 10 4
1 1 1 1 2 2 2 2 3 4
1 1 1 1
we will first remove all the ones as they are present both in $$$l$$$ and $$$r$$$ arrays, after this its better to remove two 2s from $$$l$$$ as it will prevent us from spending extra money on them by changing color now the arrays would become-
1 1 1 1 2 2 3 4
1 1 1 1 2 2
now we just shift either 3 and 4 and also change its color.
19 months ago, # | D is not even close to 2000 score |
19 months ago, # | lol, how to do well in global round? Weirdly I perform badly whenever I participate in global round(somewhat not bad in other Div. 1 + Div. 2 round). |
19 months ago, # | Once again C was much tougher than D to me |
How to solve E? I can only come up with $$$O(n^4)$$$ $$$dp[i][j] =$$$ ways to turn on $$$i$$$ computers with $$$j$$$ operations used |
-
Note that there cannot be more than one consecutive light that turns on automatically. So, our final answer will have some segments of $$$1$$$'s (lights that are turned on manually) separated by exactly one $$$0$$$ (lights that are turned on automatically). We need to find the number of ways to make such an arrangement.
Let's take this one step at a time.
In how many ways can we turn all the lights on manually?
You can only choose one starting light in a segment of n lights, then at each step you can either go left or go right. For better visualisation, consider n points coloured red. Pick a starting point and colour it blue. In each step, you can move from a blue point to an adjacent red point.
Number of ways to do this = $$$(L + R)! / (L! * R!)$$$ , where L is the number of steps to the left of the starting point that one can take, and similarly, R is to the right.
To meet the constraints, we will be precomputing these answers till $$$n$$$.
Now, coming to the main solution.
Let $$$dp[i][j]$$$ = number of ways we can arrange the first $$$i$$$ lights such that the $$$i$$$ $$$th$$$ light is manually turned on and a total of $$$j$$$ lights were turned on automatically among the first $$$i$$$ lights.
Let $$$k...i$$$ be the last segment of $$$1$$$'s. This means that at position $$$k-1$$$ we will have a $$$0$$$ and at position $$$k-2$$$ there will be a $$$1$$$. If there are exactly $$$j$$$ $$$zeros$$$ in the segment $$$1...i$$$ then there are exactly $$$j - 1$$$ $$$0$$$s in the segment $$$1...k-2$$$.
Let's define an operation, as we turning a light manually on (or placing a $$$1$$$). So in the segment $$$1...k-2$$$ we have to place $$$k - 2 - (j - 1)$$$ ones, and in the segment $$$k...i$$$ we have to place all $$$i - k + 1$$$ ones. This is similar to the question we answered above for placing all ones. We have to tell the number of permutations of $$$(L + R)$$$ items, in which the order of the $$$L$$$ items and $$$R$$$ items are fixed.
Therefore, the ans for $$$dp[i][j] = dp[k - 1][j - 1] * nCr((k - 2 - (j - 1)) + (i - k + 1), (i - k + 1)) * ways$$$ $$$to$$$ $$$arrange$$$ $$$(i - k + 1)$$$ $$$ones$$$
PS: I know it's a little too verbose. But hope you can understand the solution.
19 months ago, # | How to solve B and C ? |
-
In C, keep assigning the block to the tower with minimum current height. Can be done using set <pair<int, int > >. Also the answer can never be NO,
-
How to justify this solution i.e how to prove that difference in height won't exceed x ?
-
Suppose we have formed m blocks(B1,B2...Bm) with some i(i<n) smallest height towers.
h[B1] < h[B2] < .... h[Bm] and h[Bm] — h[B1] <= x
now h[i+1] can at max be x, So, if we add it to B1 then abs(h[i+1]+h[B1]-h[Bm]) <= x. So our condition holds always.
-
Nice prove. thanks. Can you share your thought process for solving this ? Like how you approached this problem before coming to final solution ?
-
-
As every height is <=x as mentioned in the question and also we are filling blocks in sorted order of their heights, the maximum height between 2 stacks will always be atmost 1(because we are filling all the m stacks each with a block and start the next iteration).
So, as the size difference between stacks is atmost 1. The difference between the stacks will always be the block which we are keeping at the top as it was mentioned each block is having height <=x filling this way will always give our answer.
Hope this helps :) Please correct me if there are any mistakes.
-
-
-
Assuming that I will not fail system tests.
Problem B: Notice that we can only form squares using 2 or 4 isosceles triangles. So just check if the given number of triangles is divisible by 2. If it is, then check if (n/2) is a perfect square. (We can form a square of size sqrt(n) considering 2 triangles as a single block). Now, if this fails then check if n is divisible by 4. If it is, then repeat the process above. The answer in any other case is NO.
Problem C: I have done this greedily. Using a priority queue, I always select the tower with minimum height and add the blocks in decreasing order after sorting. After adding all the blocks, I check if the difference between the minimum and maximum height is smaller than or equal to x.
19 months ago, # | how to solve problem D? |
-
Remove all the already matching pairs as they do not affect the overall answer.
Now, check if number of left socks = number of right socks, then the answer is simply the number of left socks (this happens because we have already removed matching socks and hence we can just change the color of socks from any one leg to match it with the other leg)
Now, we know that we have to transfer some socks from one leg to the other.
-
- Observation: It is always better to transfer socks which form a pair.
-
- Example: Consider we have Left: 2 2 1 3 Right: 4 5 Now, we know that we have to transfer one sock from Left to Right, and it will be best if we transfer sock 2 from left to right, as it then forms a pair with the one sock 2 which would remain in left.
Now, after transferring greedily, we again remove the matching pairs of socks in left and right. Now, if the remaining number of socks in left and right are same, then the answer is simply number of transfers we made + number of left socks (we change the color to match the right socks as we already have removed the pairs). If the number of socks are still not the same, then we can simply transfer any socks from the pile having greater number of socks to the other and then change the colour of the remaining socks. In this case, the answer becomes the number of transfers we made earlier(greedily) + greater pile size.
-
I did exactly the same but I am getting WA on test 3
https://codeforces.com/problemset/submission/1515/116187499
Can you please help point out my mistake? Thank you!
19 months ago, # | How to solve E ??? |
19 months ago, # | Lets hope the pretests for F are strong :) |
how to solve problem no D? |
19 months ago, # | How to solve F orz... I try to merge two nodes $$$u$$$ and $$$v$$$ which $$$a[u] + a[v]$$$ is maximum. |
-
As long as initially $$$\sum_i a[i] \geq (n-1) x$$$ and the graph is connected, there is always a road you can build, no matter which roads you build and in which order. This means you can discard all edges but some $$$n-1$$$ that form a tree.
Then, start doing arbitrary possible operations. Maintain in every component the values $$$a[j]$$$ for the components $$$j$$$ of children of the component, and in a priority queue the maximum current value $$$a[i] + a[j]$$$ over pairs (component $$$i$$$, component of child of $$$i$$$).
Complexity is $$$\mathcal{O}(n \log^2 n)$$$ with small-to-large merges.
19 months ago, # | Did anyone get an FFT solution to pass for E? I'm having a rough time getting my code faster than 5 seconds sadly... |
-
what is the FFT solution?
-
So we're going to work with ranges of computers that are off. Let $$$dp[k, t, end]$$$ be the number of ways to turn on a segment of length $$$k$$$ when toggling exactly $$$t$$$ computers, with $$$end = 1$$$ if the left end of the segment is the end of the whole array and $$$0$$$ otherwise (the only time both ends are the ends of the array is when $$$k = n$$$, which we case out). We assume that the right end of the segment is always adjacent to a computer that is already on Then our transition is
$$$\displaystyle dp[k, t, end] = \sum_{i=0}^{k-1} \sum_{j=0}^{t - 1} \binom{t - 1}{j} dp[i, j, end] \cdot dp[k - 1 - i, t - 1 - j, 0]. $$$Basically, we are choosing to toggle the $$$i+1$$$th computer, splitting our segment into two. The lengths of these segments are $$$i$$$ and $$$k - 1 - i$$$ respectively, and we allocate these segments $$$j$$$ and $$$t - 1 - j$$$ toggles respectively. Then, for the remaining $$$t - 1$$$ toggles that we have, we choose $$$j$$$ of them to use on the left size, and $$$t - 1 - j$$$ of them on the right side. We can rewrite this as
$$$\displaystyle dp[k, t, end] = \sum_{i=0}^{k-1} \sum_{t_L + t_R = t - 1} (t-1)! \frac{dp[i, t_L, end]}{t_L!} \cdot \frac{dp[k - 1 - i, t_R, 0]}{t_R!}, $$$which we can optimize to a convolution as follows: let $$$dp[k, end]$$$ be a polynomial in $$$x$$$, where the coefficient of $$$x^t$$$ is the value of $$$\displaystyle \frac{dp[k, t, end]}{t!}$$$ (our old DP). Let's fix some $$$k$$$ and $$$end$$$. Let $$$p(i)$$$ be the polynomial
$$$p(i) = dp[i, end] \cdot dp[k - 1 - i, 0],$$$and let $p(i)[t]$ denote the coefficient of $$$x^t$$$ in $$$p(i)$$$. Then, we make a new polynomial $$$q(i)$$$ (I know my naming is getting egregious), with
$$$ q(i)[t] = p(i)[t] \cdot t!, $$$i.e. we multiply the coefficient of $$$x^t$$$ in $$$p$$$ by $$$t!$$$. Then, we let $$$r$$$ be the polynomial
$$$\displaystyle r = x \sum_{i=0}^{k-1} q(i). $$$Then, the coefficient of $$$x^t$$$ in $$$dp[k, end]$$$ is exactly
$$$\displaystyle \frac{r[t]}{t!}. $$$The overall runtime is $$$O(n^3 \log n)$$$. I think there's a way to further optimize this by doing some 2D convolution, but I don't really know how to do anything like that (or if it's even possible). The idea for all of this is based on generating functions, but I'm not very well versed with those either, so maybe some trick from those can be useful here.
Here's my code: 114957402. It runs in about $$$5.5s$$$ locally, and with some annoying optimizations I've gotten it a bit further down, but not by much.
update: I got it to pass (114970160) with some optimizations + pragmas
-
-
No need for FFT. You work with segments of manually toggled computers, with single automatically toggled ones in between. Then DP states are (first $$$i$$$ computers toggled, the last one is automatic or right endpoint of a segment, number of manually toggled computers up to computer $$$i$$$), and there are just $$$O(N^3)$$$ state transitions.
-
Can you explain the transitions? i might not solve it on my own.
-
-
You can solve this task without FFT.
We can see on array as blocks set of consecutive computers.
Let write the 1st DP f[len][cnt] — answer for on first len computers, where cnt computers we turned on themselves. Calculating DP looks like f[len + bs + 1][cnt + bs] += f[len][cnt] * fullblock[bs] * C[cnt + bs][bs], where fullblock[bs] — number of permutations for turned on by hand bs computers among bs computers.
For fullblock[bs] we need in the 2nd DP. dp[len][last_pos][flag] — number of permutations with len computers, there is computer with index len stay in position last_pos, flag = 0 when position of index len — 1 stay to the left of last_pos
19 months ago, # | Phoenix Played with all of us |
19 months ago, # | The comment is hidden because of too negative feedback, click here to view it |
-
damn, you have crazy expectations for problems..
-
The comment is hidden because of too negative feedback, click here to view it
-
The first comparison criteria among the participants is the number of problems they solve, second is the time they spend on each problem and the amount of penalty they receive, easier problems may fade the impact of the first criteria but the second still stands and that's what makes you one of the worst second division participants of this contest.
-
19 months ago, # | I wonder that if there is a contest without graph theory problems...... |
19 months ago, # | hmm how F checker works? |
19 months ago, # | How to solve E ? |
-
I used dp to find all the possible combinations of switches that we manually turn on. For example, X_XXXX_XX_X, XX_X_X are some valid sequences. The gaps represent switches that automatically are on. It is easy to see that the size on contiguos gaps will be atmost 1.
Now, for each such combination we've to find the number of permutations to fill the X's. To do that I used 2 more states, {position, continuos X's till pos, number of skips}. I use skips to calculate how many were manually ONed before the contiguos Xs until pos.
Now another important thing to note is that, The number of permutations to arrange r numbers such that theres no gap between them is 2^(r-1). (Try to prove it)
After that we just have to use some more combinatorics to combine 2 contiguous segments of X's in our dp. There will only be 2 transitions, pos->pos+1 and pos->pos+2 (skip->skip+1). Rest of the details should be clear in my code
19 months ago, # | I am getting Memory Limit Exceeded using multisets in problem D. Please have a look at my code: https://codeforces.com/contest/1515/submission/114956539 Why using map instead of multiset do not give this error? |
19 months ago, # | mgmggmgm greedies and observations go brr |
19 months ago, # | WA on pretest 3 on problem D again and again. |
19 months ago, # | Pending System Testing for everyone? |
19 months ago, # | Passed samples of problem E just before the end of the contest, submitted it and got a The retribution of bad habits comes. |
19 months ago, # | There is something called greedy algorithms, Problem D was based on ultra greedy Algorithm. |
-
It felt like programming some robot to jump, move, etc in a game using too many if else statements.
-
I checked my solution to D, found only two if statements,
-
19 months ago, # | A to D seemed doable but still I was only able to get A correct, looking forward to editorials to understand the missing cases. |
19 months ago, # | Idea for E? |
19 months ago, # | The setters wanted to emphasize "Problem C uses constructive algorithms" (Some other problems also have two same tags) |
19 months ago, # | A-D weren't very pretty problems but weren't too bad either. I liked E though. |
19 months ago, # | In case you're curious about B: it should be obvious that since the sides of triangles are $$$1$$$ and $$$\sqrt{2}$$$, the side of the resulting square has to be $$$a+\sqrt{2}b$$$. Then, the area is $$$N/2 = a^2+2b^2+\sqrt{8}ab$$$, but since $$$a,b$$$ are rational, $$$\sqrt{8}ab$$$ can be a rational number only if $$$ab = 0$$$. That means $$$N/2 = a^2$$$ or $$$N/2 = 2b^2$$$. |
19 months ago, # | The comment is hidden because of too negative feedback, click here to view it |
-
Stop bullshitting everywhere. Contest was good, maybe your ass got burned with D. So keep your shitty opinions to yourself, ultrashitposter.
-
Ok, I agree that its my rage but I dont get how a person who didnt even do the contest live is giving feedback.
-
I wrote from my other account and solved A-D.(I just created that a week ago to see how I performed if I started anew). You can verify in the discord server if youdoubt me, I already discussed it there.https://discord.gg/5DCnEpbB
-
Well, first of all alting is against the rules, better wish mike doesnt read it message lol.
-
-
-
19 months ago, # | Wow, such a balanced contest |
19 months ago, # | Can someone tell me why this code is failing even for the first pretest for problem C. It is running fine in my local. Any help would be very very much appreciated. Thanks in advance. |
19 months ago, # | I'm in love with my solution to I, so I'll share it in case it's different from the model solution: Ofc. let's sort the diamonds by the order we we'll pick them, the leftmost item is the first to pick. Let's define $$$f(x)$$$ as the maximum integer $$$k$$$, such that $$$2^k \leq x$$$. Let's build the segment tree on the sequence of diamonds and for each query of the third type let's run dfs on it. Ofc. in leaves we can normally consider the diamonds, but it would be too slow, so we are looking for a speedup. Let's split into two smaller segments each time when $$$f(size~of~our~backpack)$$$ will decrease somewhere in it. If it won't change, then let's do something smart to skip the whole segment in $$$O(1)$$$. When will it decrease? It'll happen for sure if in the segment that we currently are is some diamond with weight $$$w$$$, such that $$$f(w) = f(size~of~our~backpack)$$$ and $$$w \leq size~of~our~backpack$$$. It will happen also if the sum of the weights of all diamonds with $$$f(weight) < f(size~of~our~backpack)$$$ is at least $$$size~of~our~backpack$$$. In these two cases let's just solve the segments recursively. If neither of the conditions hold, we know that we'll simply take all the diamonds with $$$f(weight) < f(size~of~our~backpack)$$$. Final observation: $$$f(size~of~our~backpack)$$$ will decrease at most $$$\log$$$ times and for each time it decreases we we'll do only $$$O(\log(n))$$$ splits, so the complexity for each query will be $$$O(\log^2)$$$. Let's then build $$$O(\log)$$$ segment trees. Each of them will keep the minimum weight of a diamond with $$$f(weight) = id~of~tree$$$ and the sum of weights and values of diamonds with $$$f(weight) \leq id~of~tree$$$. We can modify these values in $$$O(\log^2)$$$ per query and the query about finding the score also can be done in $$$O(\log^2)$$$ then. |
19 months ago, # | Thanks for the contest! The problems I read were all pretty nice. I'm a bit salty that I failed E and didn't think of working on F instead but that's part of the CP experience :) |
WTH is wrong with this solution for B??? Input can't exceed 1e9, what am I missing and why does it fail test 5? code EDIT: Fuck me, I'm dumb. |
19 months ago, # | When you fix the bug(1 char bug)in your code 15 seconds before the contest end and then your internet decides to load the page very slowly and you miss submitting the problem by 1 second.(It turns out it took me less than a minute to ac in upsolving :( now I will lose rating instead of becoming IGM)The bug was that I used variable xx instead of x at place |
19 months ago, # | no brain me solving question A by shuffling the array multiple times codeforces: we wont let u cry this time, Accepted |
19 months ago, # | To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again! |
19 months ago, # | tfw OEIS doesn't work |
19 months ago, # | Why system testing is happening again? |
Today's global was the coolest of all that I handed in. Thank you very much FieryPhoenix ! I will wait for more competitions from you |
19 months ago, # | Great contest! (and thanks for the IGM) |
-
sqrt(n) can be found in O(logn). You have written O($$$\sqrt{n}$$$) logic
-
Editorial has mentioned sqrtn solution also..
-
It has mentioned that it is possible to write an O($$$\sqrt{n}$$$) solution, not that it will be AC. For $$${10^4}$$$ test cases with $$$\sqrt{10^9}$$$ complexity, your solution won't pass the time limit.
EDIT: I don't get why the comment is getting downvotes. I still stand by my statement, O($$${10^{8.5}}$$$) should not get an AC.
-
People have ac with square root solutions also.. Plz see that as well.. They have the same function as I have written
-
Can you share those solutions?
-
https://codeforces.com/contest/1515/submission/114909506 You can look at this After the constest I used fast io in my code aand submit it again but tle only...so fast io is not problem here ...
-
https://codeforces.com/contest/1515/submission/115008964
This passed. I just updated the way you were checking if a number is a perfect square or not. Though I'd advise against writing O($$${10^{8.5}}$$$) complexity as then it depends a lot on the constant factor of your code as is in this case.
-
It makes a lot of difference when you write something of O($$${10^{8.5}}$$$). The most expensive operation in your code is sqrt and this change decreases the number of operations required to half of what it was. Therefore, avoid writing something that could be TLE'd because of constant factor.
-
-
-
-
-
-
19 months ago, # | somebody please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.com/contest/1515/submission/114967116 |
-
You might be missing some key points. Link to Explanation
114951091 Don't know why getting Wrong Answer. Can somebody find a testcase which gives wrong answer to the code. How the answer in following test case is 3 and not 4 4 5 3 5 8 5 5 10 10 4 |
-
With initial socks $$$[4, 5, 3, 5, 8, 5]$$$ and $$$[5, 10, 10, 4]$$$,
- Change one $$$5$$$ from left to right to get $$$[4, 5, 3, 5, 8]$$$ and $$$[\color{red}{5}, 5, 10, 10, 4]$$$.
- Now there are equal number of left and right socks. Only two pairs of socks have different colors, so we can change these two socks: $$$[4, 5, \color{orange}{10}, 5, \color{orange}{10}]$$$, $$$[5, 5, 10, 10, 4]$$$.
19 months ago, # | can anyone kindly explain why greedily adding the 2 smallest values in the array not work in c. like if we have [2,4,7,9,10] and if we want 3 block just add the smallest 2 and replace, by this we get [6,7,9,10] and then again do the same thing, thus getting [13,9,10] the max difference is 4 which is okay, if we were to do any further operation we would have done that to 9,10 but this gives WA, can anyone suggest a counter example |
-
Here's a test case that fails your code:
The towers produced by your code have heights $$$4$$$, $$$2$$$, and $$$2$$$.
-
wow thanks, couldn`t figure out why the above algo didnt worked and hence struggled in the contest too. is there any way to find countertest to your algorithm or just you have to think about it for long
-
someone please explain why i am getting wrong answer in test 4 in D . my submission: 114958100 |
19 months ago, # | Commenting this again because did not get any response in the previous comment. Can someone explain why this solution for problem C is failing even for the first pretest. It works fine in my local machine. |
19 months ago, # | Got this message from System Attention! Your solution 114875501 for the problem 1515B significantly coincides with solutions nmp/114873698, calabashgirl/114875308, bnkalya1502/114875501, sleeping_samurai/114904548. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. First of all , I do not even know who the above mentioned people are , neither did I used any online compiler . Although I agree that the above codes are similar but this is probably a coincidence because for an easy problem like this (given that there were 10K+ participants) , there are a limited types of implementations possible . |
19 months ago, # | False Accusation of cheating in Codeforces Global Round 14. Got this message today. MikeMirzayanov
My Submission: 114904088 ......His Submission: 114880136 Problem B was quiet straight forward, and there are not much ways you can write the code for this problem if you try the same approach. In this case, me and tem_shett happened to use same approach for this problem. This is just a mere coincidence, and is quiet shocking for me becasue my solution has never been skipped or hacked before. Will this be rectified or I have to lose +43 for this contest ?. PS — I had a doubt, why am I the only one between the two of us who is penalized. |
19 months ago, # | When will t-shirt winners be announced? |
-
-
What seed did you use?
-
Usually,seed is the score of rank 1.
-
-
18 months ago, # | Congratulations to t-shirt winners!
|
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK