FieryPhoenix's blog

By FieryPhoenix, 11 days ago, In English

Hi!

On May/02/2021 17:35 (Moscow time), 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!!

  1. Radewoosh
  2. ksun48
  3. Um_nik
  4. Benq
  5. yhx-12243
  6. tourist
  7. duality
  8. jiangly
  9. LJC00118
  10. NotaMotuaQAQ
Announcement of Codeforces Global Round 14
 
 
 
 
  • Vote: I like it
  • +1585
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it -33 Vote: I do not like it

Is it rated?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The rounds are open and rated for everybody.
    Mentioned in the second line ...

»
11 days ago, # |
  Vote: I like it -63 Vote: I do not like it

For anyone wondering what GLHF (in the last line) means — Good Luck, Have Fun!

»
11 days ago, # |
Rev. 3   Vote: I like it +61 Vote: I do not like it

ugh i cant make good meme : (

»
11 days ago, # |
  Vote: I like it +49 Vote: I do not like it

PurpleCrayon orz!

»
11 days ago, # |
  Vote: I like it +67 Vote: I do not like it

Scientific studies have shown Global Round are usually hard, but I will participate for longevity and happiness.

»
11 days ago, # |
Rev. 8   Vote: I like it +77 Vote: I do not like it

As I tester of this round people are giving me downvotes.

»
11 days ago, # |
  Vote: I like it +197 Vote: I do not like it

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!

»
10 days ago, # |
  Vote: I like it -29 Vote: I do not like it

Hope I will remain a specialist after this contest.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If science says to upvote this blog, then i believe in flat earth.

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

sto PurpleCrayon orz

»
10 days ago, # |
Rev. 3   Vote: I like it +62 Vote: I do not like it

Relatable >_<
original meme

  • »
    »
    10 days ago, # ^ |
    Rev. 5   Vote: I like it +58 Vote: I do not like it
    (≧▽≦)
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    Very original meme

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Woaahhh, Directly trying to defeat red coders. Nice MEME!!!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    OK I guess global rounds are really hard this was my first codeforces contest I guess i shouldnt be demotivated because i didnt even submit a single thing right just got close on phoenix and puzzle(failed test 2 lol)

»
10 days ago, # |
  Vote: I like it -43 Vote: I do not like it

Can we expect to have subtask?

»
10 days ago, # |
  Vote: I like it +88 Vote: I do not like it

omg, a round prepared by the Americans with Chinese names

»
10 days ago, # |
  Vote: I like it -19 Vote: I do not like it

Global Rounds always provides a very good opportunity to boost up your rating... Excited!!!!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    And a very good opportunity to boost it down, too =)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    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.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 4   Vote: I like it +12 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        Nah

        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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +50 Vote: I do not like it

          Nah

          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

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I have observed there's a lot more cheating in global rounds than normal rounds. Honest participants usually suffer in global rounds imo.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      Most probably because it's of 3hrs and cheaters get sufficient time to cheat .

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wow, it's been a long time since the last global round.

»
10 days ago, # |
  Vote: I like it +238 Vote: I do not like it

As a tester, unfortunately, I don't have any witty joke to write in this message.

»
10 days ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

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.

»
9 days ago, # |
  Vote: I like it +37 Vote: I do not like it

Nice

»
9 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Omg 5000 points for a problem. Focus on the last problem, problem I with 5000 points, that's enough. :D

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I like the strategy which has a possibility that we don't solve anything in the contest XD.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    by the time I solve it, it would be worth a negative amount of points.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      By the time I solve it, it will time for codeforces global round 100.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You guys are solving 5000 pts problem :(

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the best bro.

»
9 days ago, # |
  Vote: I like it -35 Vote: I do not like it

Contest time is really bad

Why aren't contests more late or earlier (for example 15:35 or 21:35)

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the two contest authors related?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They're both americans with a chinese name, i guess

»
9 days ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

Please dm me the problems I promise to not tell anyone

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is ORZ, I've seen it in many comments.

»
9 days ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

Me, a football lover coder today

»
9 days ago, # |
  Vote: I like it +9 Vote: I do not like it

This round has extremely strong pretests.

»
9 days ago, # |
  Vote: I like it +54 Vote: I do not like it

First contest in isolation! I hope I have the energy to compete. #COVID_coders

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Same here brother, me too suffering from covid, I can feel your pain. T_T :(

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Same situation. Tested positive yesterday. Unlike others I am having a headache, so decided to take some rest.

    If you are not well, I advise you to do the same.

»
9 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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!

»
9 days ago, # |
  Vote: I like it +59 Vote: I do not like it

  • »
    »
    9 days ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    Hmmm, I was imagining a closet full of segment trees, linked lists and a few queues. Never thought of the struct t_shirt. Hmmm..

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      So many down votes because if you meant a typename then you should have used shirt_t by cpp convention.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces is temporarily unavailable. Please, return in several minutes.

Hope this doesn't happen during the contest.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

PurpleCrayon orz!!!!!!

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wer retin chains ?

»
9 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Is it only me who can't do anything for 1 hour before the contest and keep switching between different tabs until it starts?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you have to do the same thing after 2 hrs in this contest(considering the difficulty of global round).

»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

There is a long queue, about 4 pages show only "running". Would that affect the round?

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My first Global Round,nervous.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can i even solve the 1st question huh...... i don't think so :(

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

After having 10 Wrong answer on pretest 2 for a and b. ORZ

»
9 days ago, # |
  Vote: I like it +4 Vote: I do not like it

My rating after this global round going down like Wheeeeeeeeee

»
9 days ago, # |
  Vote: I like it +12 Vote: I do not like it

I upvoted the blog and participated. I guess the scientific studies and their evidences for longevity and happiness are wrong :(

»
9 days ago, # |
  Vote: I like it +10 Vote: I do not like it

I wonder if D is that easy felt like a normal C

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I worked like two hours on d but didnt get it :/

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it

      And I worked two hours on C

      xD

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like 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

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah man, your rating graph and game is truly inspirational! (y)

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            I feel your pain in these comments. Whatever the hard time you had I am sorry for that. Your consistency is brilliant. I hope God gives you the power to battle these hard times and you learn new things and reach the master level or so.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

D is not even close to 2000 score

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Once again C was much tougher than D to me

»
8 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    And it can pass the pretest.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can simply let computer $$$i$$$ in $$$dp[i][j]$$$ be turned on automatically.

    so you just have to enumerate the last automatically turned on computer before computer $$$i$$$ for $$$dp[i][j]$$$

»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve D?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B and C ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For b check the if number is divisible of 2 or 4 and the remaining number should be a square number.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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,

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      How to justify this solution i.e how to prove that difference in height won't exceed x ?

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Nice prove. thanks. Can you share your thought process for solving this ? Like how you approached this problem before coming to final solution ?

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
            Rev. 4   Vote: I like it +2 Vote: I do not like it

            Initially i just tried random greedy strategies but got WA. Then i thought of somehow using the fact that each height < x and tried proving a greedy approach.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    For C, just sort by block lengths and assign to each stack.

    For B, divide by 2 and 4, and see if number is a square.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B — If I don't FST, if dividing by 2 or 4 gives you a square (number) its a yes C — no idea I kept WAing

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did the same for your C solution, let's hope we pass!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem D?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My Approach : (Got All Clear) At first cancell all the matches on left and right basket. then in left basket if you have 2 socks of same colour you can move it to right baket to make pair, so remove the same colour socks and increment counter. do the same to right basket. At the end print(count+ max(remaining_leftBasket , remaining_rightBasket)

    Used HashTable (Python 3)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • 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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -18 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E ???

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Lets hope the pretests for F are strong :)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you give me an insight to your approach? I would really love to understand how to approach such a problem.

»
8 days ago, # |
  Vote: I like it -30 Vote: I do not like it
»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve problem no D?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F orz... I try to merge two nodes $$$u$$$ and $$$v$$$ which $$$a[u] + a[v]$$$ is maximum.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone get an FFT solution to pass for E? I'm having a rough time getting my code faster than 5 seconds sadly...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    what is the FFT solution?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 5   Vote: I like it +15 Vote: I do not like it

      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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the transitions? i might not solve it on my own.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If the $$$r$$$-th computer is the right end of a segment (so $$$r+1$$$ would be automatically toggled or $$$r=N$$$) and the $$$l$$$-th is its left endpoint, then $$$dp_{l-1,k} \rightarrow dp_{r,k+r-l+1}$$$ for each $$$k$$$ (number of manually toggled computers before $$$l$$$).

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Phoenix Played with all of us

»
8 days ago, # |
  Vote: I like it +43 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it -47 Vote: I do not like it

shitiest ABCD. also the scoring distribution was bullshit. 2000 fucking points for D :\

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +73 Vote: I do not like it

    damn, you have crazy expectations for problems..

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it -52 Vote: I do not like it

      No,u just set them very poor and there is no wrong in accepting that. Problem D is not supposed to be solved by 4.5k people. Thats just dumb problem

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        Then why did you spend almost 2 hours on it and get it done only from a 7th try?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like 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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It was a good contest dont let them tell u otherwise!![user:FieryPhoenix]

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -49 Vote: I do not like it

    Very shit contest for div2 participaants indeed (seeing most of them usually do upto D). Stupid problems, just stupid

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I wonder that if there is a contest without graph theory problems......

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hmm how F checker works?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It uses union-find to track connected components of the graph, augmented with the amount of asphalt in each component (stored at the roots of the union-find data structure).

»
8 days ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve E ?

  • »
    »
    8 days ago, # ^ |
    Rev. 5   Vote: I like it +6 Vote: I do not like it

    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

    Submission

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 days ago, # |
  Vote: I like it -9 Vote: I do not like it

mgmggmgm greedies and observations go brr

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

WA on pretest 3 on problem D again and again.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Pending System Testing for everyone?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Passed samples of problem E just before the end of the contest, submitted it and got a MEMORY_LIMIT_EXCEEDED on test 1. And there's not enough time to fix it. :(

The retribution of bad habits comes.

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

rainboy orz.

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

There is something called greedy algorithms, Problem D was based on ultra greedy Algorithm.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -79 Vote: I do not like it

    No it was based on mega ultra shit algorithm

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Here I see a blue coder complaining that D's solution is shit and tried 7 times to get AC.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It felt like programming some robot to jump, move, etc in a game using too many if else statements.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I checked my solution to D, found only two if statements,

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it -33 Vote: I do not like it

        That's because you used for loops instead and took 30 minutes to optimize if else.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is using loops against the rules ? I think algo-police would be on their way to catch everyone using loops.

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

A to D seemed doable but still I was only able to get A correct, looking forward to editorials to understand the missing cases.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Idea for E?

»
8 days ago, # |
  Vote: I like it +36 Vote: I do not like it

The setters wanted to emphasize "Problem C uses constructive algorithms" (Some other problems also have two same tags)

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

A-D weren't very pretty problems but weren't too bad either. I liked E though.

»
8 days ago, # |
  Vote: I like it +44 Vote: I do not like it

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$$$.

»
8 days ago, # |
  Vote: I like it -149 Vote: I do not like it

Thank you setters for a very shitty round. Enjoyed every inch of it. Please dont make such shit problems in the future

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    Stop bullshitting everywhere. Contest was good, maybe your ass got burned with D. So keep your shitty opinions to yourself, ultrashitposter.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, I agree that its my rage but I dont get how a person who didnt even do the contest live is giving feedback.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, first of all alting is against the rules, better wish mike doesnt read it message lol.

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Your account seems alt also,why don't you have your name, country name in your account. So go on and sue me .

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it -8 Vote: I do not like it
              Hope this might help
              • »
                »
                »
                »
                »
                »
                »
                »
                6 days ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                Yeah, glad I was able to help you, keep extending that help to others.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, such a balanced contest

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

link to solution.

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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a good contest for me

»
8 days ago, # |
  Vote: I like it +88 Vote: I do not like it

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.

»
8 days ago, # |
  Vote: I like it +26 Vote: I do not like it

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 :)

»
8 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Isn't it because your set s will contain numbers up to only $$$10^6$$$ instead of $$$10^9$$$?

»
8 days ago, # |
  Vote: I like it -117 Vote: I do not like it

fuck u motherfuckers, it was the most bullshit global contest ever. please dont let this son of the bitches make contest, MIKE.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it -109 Vote: I do not like it

    fuck u motherfuckers, it was the most bullshit global contest ever. please dont let this son of the bitches make contest, MIKE.

    Update: This was a poor attempt at starting a copypasta designed to make fun of the original comment. I didn't even participate in the contest and I liked the problems.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Ok then why don't you become master and show everyone how to set contests ಠ_ʖಠ

»
8 days ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it

(╥﹏╥)

Pics-Art-05-03-12-20-01

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone tell , in problem D, test case 3 what is test 164. Thanks in advance.

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
8 days ago, # |
  Vote: I like it +12 Vote: I do not like it

no brain me solving question A by shuffling the array multiple times codeforces: we wont let u cry this time, Accepted

»
8 days ago, # |
  Vote: I like it +81 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

tfw OEIS doesn't work

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it +38 Vote: I do not like it
    might be the reason
  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    I coded up a brute force solution and generated the answer for N up to 20. Plugged that into OEIS. Nope lol.

    I have no idea why I even tried. Great job problem authors! It's your win this time :D

»
8 days ago, # |
  Vote: I like it +23 Vote: I do not like it

Why system testing is happening again?

»
8 days ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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

»
8 days ago, # |
  Vote: I like it +83 Vote: I do not like it

Great contest! (and thanks for the IGM)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1515/submission/114966463 why does this give tle on b problem? plz explain its sqrt(n) only.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sqrt(n) can be found in O(logn). You have written O($$$\sqrt{n}$$$) logic

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Editorial has mentioned sqrtn solution also..

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it -11 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          People have ac with square root solutions also.. Plz see that as well.. They have the same function as I have written

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you share those solutions?

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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 ...

              • »
                »
                »
                »
                »
                »
                »
                »
                8 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But this is not right ..what diff does it make ..??I should get ac in that..

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The diff is that you're performing 2 divisions (modulo is division) for something that can be done in one multiplication. The constant factor is less in the latter.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  it hardly makes any diff at all

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sometimes constant optimization really matters.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is the line #define int long long int. Computation and I/O is more costly for long long integers and so, often the overhead in such cases causes a TLE.

    I just commented out that line and it got accepted.

    114980681

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

10 6 4

4 5 3 5 8 5 5 10 10 4

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With initial socks $$$[4, 5, 3, 5, 8, 5]$$$ and $$$[5, 10, 10, 4]$$$,

    1. Change one $$$5$$$ from left to right to get $$$[4, 5, 3, 5, 8]$$$ and $$$[\color{red}{5}, 5, 10, 10, 4]$$$.
    2. 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]$$$.
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Here's a test case that fails your code:

    1
    8 3 1
    1 1 1 1 1 1 1 1
    

    The towers produced by your code have heights $$$4$$$, $$$2$$$, and $$$2$$$.

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just tested with many tests until I found one that is not correct. Since your idea seems correct, I suspected that it was probably wrong on some kind of special cases.

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

someone please explain why i am getting wrong answer in test 4 in D . my submission: 114958100

»
8 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Commenting this again because did not get any response in the previous comment.

Solution

Can someone explain why this solution for problem C is failing even for the first pretest. It works fine in my local machine.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you're not iterating through the whole vector, missing i = m. So, one value you're getting is just garbage value.

    Also, you might have to sort it in descending to work.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help in Problem D, I cant understand where it's going wrong. My code

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

False Accusation of cheating in Codeforces Global Round 14. Got this message today. MikeMirzayanov

Attention!

Your solution 114904088 for the problem 1515B significantly coincides with solutions shart23/114880136, ThakurSaab/114904088. 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.

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 shart23 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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Both of these codes are line by line the same except variable names.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Yeah, I know. And that's mere coincidence. For such simple problems, the probablity of people writing similar codes is much higher.

»
7 days ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

System

I have to talk to you about that i have got a message for the "System" of codeforces that my solution is same as the solution of JB-James-Brown-/114935692, acktron/114935957.

and for this as well 114894526, acktron/114894659.

I want you to tell that those were just problem A and C which were same. There code was small so this is a coincidence that our codes are same please leave as we will not do this again. Sorry if i did some thing wrong pls forget it.

»
7 days ago, # |
  Vote: I like it -13 Vote: I do not like it

I am is having a coincidence that my solution is same acktron for A.

[user:system]this is the coincidence.

»
6 days ago, # |
  Vote: I like it -153 Vote: I do not like it

Congratulations to tshirt winners!

List Place Contest Rank Name
1 1515 1 Radewoosh
2 1515 2 ksun48
3 1515 3 Um_nik
4 1515 4 Benq
5 1515 5 yhx-12243
6 1515 6 tourist
7 1515 7 duality
8 1515 8 jiangly
9 1515 9 LJC00118
10 1515 10 NotaMotuaQAQ
11 1515 11 tatyam
12 1515 12 Golovanov399
13 1515 13 LayCurse
14 1515 14 Elegia
15 1515 15 Maksim1744
16 1515 16 _h_
17 1515 17 maroonrk
18 1515 18 kefaa2
19 1515 19 paulll
20 1515 20 nocriz
21 1515 21 receed
22 1515 22 never_giveup
23 1515 23 nantf
24 1515 24 hitonanode
25 1515 25 heno239
26 1515 26 Ormlis
27 1515 27 natsugiri
28 1515 28 dlalswp25
29 1515 29 Isonan
30 1515 30 gisp_zjz
31 1515 197 Paliukh
32 1515 164 yuyue
33 1515 337 Lidox1145143344
34 1515 230 solaimanope
35 1515 444 MrPupsik
36 1515 361 re_eVVorld
37 1515 422 zhoufangyuanPT
38 1515 449 wangziji
39 1515 49 noimi
40 1515 142 kotamanegi
41 1515 66 1-gon
42 1515 117 Juanzhang
43 1515 243 KillerX
44 1515 307 Seyaua
45 1515 318 Volkov_Ivan
46 1515 363 Andreasyan
47 1515 283 jell
48 1515 406 SSerxhs
49 1515 463 EmilConst
50 1515 213 Hyperbolic
»
6 days ago, # |
  Vote: I like it -117 Vote: I do not like it

Congratulations to actual tshirt winners!

List Place Contest Rank Name
1 1515 1 Radewoosh
2 1515 2 ksun48
3 1515 3 Um_nik
4 1515 4 Benq
5 1515 5 yhx-12243
6 1515 6 tourist
7 1515 7 duality
8 1515 8 jiangly
9 1515 9 LJC00118
10 1515 10 NotaMotuaQAQ
11 1515 11 tatyam
12 1515 12 Golovanov399
13 1515 13 LayCurse
14 1515 14 Elegia
15 1515 15 Maksim1744
16 1515 16 _h_
17 1515 17 maroonrk
18 1515 18 kefaa2
19 1515 19 paulll
20 1515 20 nocriz
21 1515 21 receed
22 1515 22 never_giveup
23 1515 23 nantf
24 1515 24 hitonanode
25 1515 25 heno239
26 1515 26 Ormlis
27 1515 27 natsugiri
28 1515 28 dlalswp25
29 1515 29 Isonan
30 1515 30 gisp_zjz
31 1515 57 orzdevinwang
32 1515 90 atomicenergy
33 1515 95 Egor.Lifar
34 1515 102 dorijanlendvaj
35 1515 124 Keewrem
36 1515 131 SheepRanger
37 1515 169 ADMathNoob
38 1515 186 natofp
39 1515 195 YeongTree
40 1515 223 N.N_2004
41 1515 227 Arg_007
42 1515 255 yuto1115
43 1515 260 __23333
44 1515 262 aa2985759
45 1515 311 njupt_lyy
46 1515 322 lucasr
47 1515 323 frost_
48 1515 337 Lidox1145143344
49 1515 362 Emilan
50 1515 463 EmilConst
  • »
    »
    6 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    fake news again?

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      the random thing is kinda sus XD

      but one of my friends names is in the list so i hope its true : ))

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      No, this time 100% authentic. Congratulations!!!!!!!!!!!

  • »
    »
    100 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm, this table seems to be almost the same as the list below.

    So when will the real list come out?

»
6 days ago, # |
  Vote: I like it -6 Vote: I do not like it

My code is not running since I have proper network connecton

»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

When will t-shirt winners be announced?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I have made a list,according to this code:

    T-shirt winners:

    Spoiler