Egor.Lifar's blog

Codeforces Global Round 3
By Egor.Lifar, 5 years ago, translation, In English

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!

  1. mnbvmar
  2. tourist
  3. Petr
  4. yutaka1999
  5. LHiC
  6. Egor
  7. ksun48
  8. sunset
  9. krijgertje
  10. kczno1

UPD. 4:

Editorial.

Announcement of Codeforces Global Round 3
  • Vote: I like it
  • +121
  • Vote: I do not like it

Comments Comments (250)
| Write comment?
»
5 years ago, # |
  Vote: I like it +76 Vote: I do not like it

Another rated round after a long break! Yeah!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope it will be a balanced contest. Not like the previous one :)

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it -35 Vote: I do not like it

deleted :(

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Where is the number of problems and score distribution?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +12 Vote: I do not like it

    It will be posted not long before the contest starts, maybe.

    (It is posted just two minutes before starts.)

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope everyone can have a good performance! (and hope I can get red again)

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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!

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I'm interested in XTX Markets job but are they interested in me XD ? (I know the answer don't tell me)

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -52 Vote: I do not like it

I like global rounds (I didn't entered any of them)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

Do global rounds support hacking? if yes then, during or after the contest?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    During the contest of course, just like in regular rounds.

    → Reply
»
5 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Are there remote jobs at XTX Markets?

→ Reply
»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Here we go!!

→ Reply
»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

How many problems will be shown

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1.. 3.. 5.. 7.. 9.. Finally!! the contest season is back!

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

hopes this contest will bring happiness in our life

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -40 Vote: I do not like it

round will be rated for those who have not solve anything?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    If you do not make a single attempt, it won't be rated for you. Otherwise it will be.

    → Reply
»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Why you don't thanks MikeMirzayanov for amazing systems Codeforces and Polygon! ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    LOL what an attempt to get free upvotes

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I was told that too many request and couldn't submit my code?

→ Reply
»
5 years ago, # |
  Vote: I like it +43 Vote: I do not like it

JOJO's Bizarre Adventure? That's pretty cool!

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +24 Vote: I do not like it

    This comment has been edited and I sincerely apologize for my lack of knowledge about this great anime

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Still cannot believe I lost this round...

    → Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Is this a JoJo reference ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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!

    → Reply
»
5 years ago, # |
  Vote: I like it +58 Vote: I do not like it

Problem D was easier than Problem C. Am I the only one who felt that way?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      What is the trick?

      I can't think anything as a trick. Is it "if $$$|i-j|*2>=n$$$ then $$$|i-j|>=n/2$$$"?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't know how you used that in this problem but I don't see any similarity.

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oppositely I thought E was easier than D.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Weird flex, but D was extremely hard for me, lol

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Did we have to use the fact that every integer from 1 to 2⋅n is mentioned exactly once anywhere in the solution? I think I have not used it anywhere in my soln. But its complexity is nlog(n) using segment tree. UPD: Got it.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, see my solution 54947377 Hopefully it would be correct, coded it in the last few minutes

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i felt is was easier than B also.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maintain sum and try to randomly switch bits?

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

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

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it -8 Vote: I do not like it

    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:

    Testcase
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +61 Vote: I do not like it

      Try this test case:

      262144

      1 131072

      1 131073

      1 131074

      ...

      1 393215

      The only answer is $$$393216+524288*k$$$.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +15 Vote: I do not like it

        Wow, incredible. :)

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        amazing. how did you get this?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Given the fact that only the bits being set on for at least one mask are counted, I guess your testcase can still be intercepted: 54974178.

        Changing $$$n$$$ into $$$262145$$$ and adding a line: 1 2^62-1 will counter such solutions.

        The systest of F still looks surprisingly weak as of now, which is strange.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How about changing stack to queue?

      I think I have implemented algo like that, but I got WA.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        I thought so during the contest, but probably no...

        ok, then it still yes, I guess :)

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

what the hell is pretest 14 on E ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    Something like this maybe? I got WA on 14 until I fixed this case

    4
1 4 5 8
2 3 6 7
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah. That works. Thanks. Forgot to pair j with the max i, instead put min i, which lead to wrong solution.

      → Reply
»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Too greedy contest

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Problem H proved once again that Za Warudo's true power is, indeed, the power to reign over this world

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give hints for question: C. Crazy Diamond.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Consider how to use no more than $$$5$$$ swaps to move number $$$i$$$ to position $$$i$$$.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi! Im sorry I still did not understand it, can you or anyone please explain it. tia!

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +26 Vote: I do not like it

        Maybe there are simpler solutions, I will explain mine.

        1. $$$p_i=i$$$, we don't need to do anything. $$$0$$$ swaps.

        2. $$$abs(at_i-i)\ge\frac{n}{2}$$$, just swap directly. $$$1$$$ swaps. (Edited, should be $$$\ge$$$ but not $$$>$$$)

        3. $$$i\le\frac{n}{2}$$$ and $$$at_i\le\frac{n}{2}$$$, use $$$p_n$$$ as temporary variable. $$$3$$$ swaps.

        4. $$$i>\frac{n}{2}$$$ and $$$at_i>\frac{n}{2}$$$, use $$$p_1$$$. $$$3$$$ swaps.

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is also fine. (Although I didn't think of that way during the competition.)

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          2 should >=

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I was not able to deal with the 5th case . :(

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Too Greedy Contest, the setters want to steal our rating :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

what is pretest 14 in problem E? why this code gets WA? 54943503

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also had this problem. I think we need to add d=min(d, (s[j] — s[i])/2)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your code will fail on tests like

    4
1 6 7 10
3 5 8 8

    Your code gives the output "NO" but the correct output will be "YES"

    YES
3
1 2 1
1 4 1
3 4 1

    here^ is one of the suitable output for the above test case

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Please tell me problem F is not about trying different $$$s(hit)$$$ randomly...

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    (retracted my previous claim; turns out there are counter tests)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +90 Vote: I do not like it

    System test haven't started yet. I think they're trying to make that test :)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +74 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, the expected value is just for convenience, the solution isn't random. In a bit more detail:

        For a mask $$$m$$$ with length at most $$$62$$$ let $$$f(m)$$$ be the expected value of the sum described in the problem if we choose a mask uniformly at random from among the masks of length $$$62$$$ that have $$$m$$$ as a prefix. (Using sum or average instead of expected value would give the same argument, I just found expected value clearer). By the linearity of expectation we can expand

        $$$f(m) = \displaystyle\sum_{i = 1}^n \displaystyle\sum_{s}\mathbb{E}\left[val_i \cdot (-1)^{popcount(s, mask_i)}\right]$$$

        Where the right sum goes over all masks of length 62 that have $m$ as a prefix. In particular for masks of length $$$62$$$ this is just the sum in the problem statement, which we want to make negative. So basically we build each digit of the mask while decreasing or keeping the expected value the same at each step. Initially the expected value is $$$0$$$, so this way we do get an answer at the end. The main claim is that the expected value for a certain $$$i$$$ and $$$m$$$ is $$$0$$$ if $$$i$$$ contains some $$$1$$$ after $$$m$$$, and $$$2^k \cdot val_i$$$ otherwise. This is because half of the masks with prefix $$$m$$$ have $$$popcount(s, mask_i)$$$ odd and half even as long as there's at least one on bit after $$$m$$$ (basically just restating that a set has the same number of odd size subsets as even size).

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +29 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that tourist's solution is not that kind of solution.

    → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

10 seconds too slow to submit correct F :(

Too slow :(

→ Reply
»
5 years ago, # |
  Vote: I like it +121 Vote: I do not like it

Did somebody find a counter-test that makes random solution fail on problem F?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    There's no such thing!!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      He didn't lock problem F, so...

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

        I know that my F is in big danger. I was just joking. Deep inside I am afraid of losing it.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +195 Vote: I do not like it

    Yep, cdkrot found some about a week ago :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      Cool! I hoped there were. How would one construct such a test case?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      It's very brave not to put that test in pretests, given the fact that people complain about weak pretests each time.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        What should they be scared of?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Huh, but it's not the case when you don't pass systests due to some silly error. This one here is pretty essential...

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it -8 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +56 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it -7 Vote: I do not like it

                There's surely no point in catching all such solutions, otherwise there would be nothing to hack.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +33 Vote: I do not like it

                  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?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  As I said, the issue is that it's a hard problem that almost nobody in the same room will solve.

                  → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        If tests are weak, people complain about weak pretests. If tests are strong, more people solve F, so people complain about difficulty distribution. :)

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Could you also add that test case by dorijanlendvaj to upsolving testcases? It seems to break even more solutions.

      262144
1 131072
1 131073
1 131074
...
1 393215
      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      In case somebody wonders, the test structure is as follows:

      Take some number of bits $$$k$$$ (must be odd)

      Then for every bitmask except the zero ($$$2^k - 1$$$ in total), add the item with this mask and the weight:

      • if bitmask == $$$2^k - 1$$$, the weight is some constant $$$-B$$$ (e.g. $$$B = 10000000$$$).
      • if bitmask has even number of bits, the weight is $$$+A$$$ (e.g. $$$A = 20000000$$$).
      • otherwise the weight is $$$-A$$$.

      One can see that the only way to change the sign of the sum is to use the mask $$$2^k - 1$$$. Which is $$$2^{-k}$$$ probability if you select the mask randomly. I also fill tests with some amount of random noise so you shouldn't be able just to use largest mask in the test data. Since $$$2^k$$$ must be at most $$$n$$$, the probability is about $$$\frac{1}{n}$$$, which is $$$n^2$$$ expected running time.

      It was also me who suggested not to put this thing in pretests, I thought it would be a good idea to allow hackers to came up with this test as well and probably the bad impact is not too large, you wouldn't have expected that some random trash solution will get AC on the problem F, don't you? :)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

So many constructive and greedy problem!

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

any hints to b plzz??

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can solve using two pointers too instead of binary search! Here's my code

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +55 Vote: I do not like it

The worst feeling in life: Waiting main tests with unproven random solution for F.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

How could this solution get TLE 12? Just because of slow output? Thanks in advance.

→ Reply
»
5 years ago, # |
← Rev. 33   Vote: I like it -34 Vote: I do not like it

it's my cake day so can i get 7 upvotes please

→ Reply
»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Problem C was great, very enjoyable to solve.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What was your approach to solve C ? Please help! as I couldn't get it.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like 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

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

The difficulty gap between problem F and G. It was good for the other colors, but it was bad for reds.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +129 Vote: I do not like it

    And the new one:

    Good enough, I think.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I felt q(D) easier than q(C). Is there anyone who felt same ?

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

If mnbvmar did not get a hack in the last five minutes tourist was likely to have a new personal best rating.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G would be pretty cool if the graph was given. That shit with bitsets ruined it.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Author's solution doesn't use bitset.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Why so many people use random algorithms to pass F?

Are they really correct?

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

System Testing hasn't started; when will it start?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the upper-bound on number of operations in prbE.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What if in C we had to minimize the number of operations?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +115 Vote: I do not like it

Codeforces Global Failed System Test Round .

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Never have seen so many FSTs in my life.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Me either

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -33 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +43 Vote: I do not like it

There are literally 5 times more failed on main tests submission for F than Accepted.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Could somebody take a look at C 54937652? I have an O(n) solution that is getting TLed. Is this intended?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Don't use endl. It flushes the output stream, and this problem has a large amount of output.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it -6 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +181 Vote: I do not like it

The most accurate description of pretests:

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem C. Same code, replacing endl with \n. TLE with endl 54949525, Accepted, 452 ms with \n 54949838. This is awful :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same thing, absolutely.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Endl flushes the output in addition to outputting new line, so it's slower. At least you won't make the same mistake again :)

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

https://codeforces.net/contest/1148/submission/54936686. how it can be ml 38?! help me please

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

get_tshirts.py
randgen.cpp

And the tshirt winners are:

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

Congratulations!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    WOW! Never expected this to happen! How can I receive the prize?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in the cpp source code, what is "testlib.h" ?

    → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why you rejudge some submissions even after the rating calculation?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Of course we are not going to recalculate ratings/change standings/anything. Egor.Lifar only rejudged practice submissions.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 4   Vote: I like it +8 Vote: I do not like it

          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?

          → Reply
»
5 years ago, # |
  Vote: I like it -132 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    You sure care a lot about a round you didn't compete in.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      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://codeforces.net/contest/1148/submission/54952521 https://codeforces.net/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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Now I'm glad I missed registration by seconds and didn't feel confident enough to try with extra registration.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        There will be many accepted submissions (without proof) if they include up to 20 pretest.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +61 Vote: I do not like it

          I don't care about pretests weakness. Systests must be strong enough to cut out shitty solutions.

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

            Here another accepted solution that gives wrong results for the test case:

            6 3
49 25 25 6 2 3
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              By the time this solution was accepted, I also thought that the test data for this problem was a little weak:D

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Added your test for the upsolving, thanks!

              → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        How can this solutions even pass? That's so disappointing. It is the first wrong shitty idea, that you can come with.

        Hmm, it was your third attempt and it was after the contest...

        Is that what meant in announcement by "8 tricky tasks for you"? That we must guess the tests? Or sorting by comparator and writing greedy algorithm on 2 pointers are "tricky" maybe?

        Problem F had an author's solution with induction, which I can call tricky. Also, problems G and H both had a deterministic solution without any random.

        Of course, it's not ok that such solutions pass systests. But in such problems like F or G there can be a very huge amount of strange unintended solutions and it's very complicated to create tests against all of them. In my opinion, weak pretests enable such tasks to exist. Maybe we should have warned about it in the announcment to make system testing not such disappointing.

        → Reply
»
5 years ago, # |
  Vote: I like it -61 Vote: I do not like it

I think this contest is really hard and unbalaced contest. I think that there should be more easy questions in the contests.

→ Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it -25 Vote: I do not like it

Codeforces Globle Fail System Test Round 3

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Why is there no one asking for editorial?

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Isn't Codeforces even try full feedback contests? Many other websites already use full feedback. Why does Codeforces use this system?

→ Reply
»
5 years ago, # |
  Vote: I like it -75 Vote: I do not like it

following is my code to the 2nd ques Born this way. I dont know about the correctness as I was getting Runtime error for the 1st TC. However the other two passed in the custom invocation.

Please tell me whats the problem here.

int main()
{
	ll n,m,ta,tb,k;
	cin>>n>>m>>ta>>tb>>k;
	multiset<ll> s1,s2;
	for(int i=0;i<n;i++)
	{
		ll x;
		cin>>x;
		x = x+ta;
		s1.insert(x);
	}
	for(int i=0;i<m;i++)
	{
		ll x;
		cin>>x;
		s2.insert(x);
	}

	ll c = 0;
	multiset<ll>::iterator it,temp;
	for(it=s1.begin();it!=s1.end();it++)
	{
		ll x = *it;
		auto f = s2.lower_bound(x);
		if(f!=s2.end())
		{
			temp = it;
			s1.erase(temp);
			s2.erase(f);
			c++;
		}
		if(c>=k)
		{
			break;
		}
	}

	ll ans=-1;
	for(it=s1.begin();it!=s1.end();it++)
	{
		ll x = *it;
		auto f = s2.lower_bound(x);
		if(f!=s2.end())
		{

			ans = *f+tb;
			break;
		}
		
	}
	cout<<ans<<endl;

}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody please help to point out where I am going wrong in problem B it failed on 8th pretest

  1. Using the first flight from A to B I find the first flight from B to C using binary search .

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

  1. I find the time to reach C and which option between the above two gives higher value I go with that.

If in this process the next flight from B to C cannot be chosen I print -1.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Editorial?

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Editorial??

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please check my following submission for Problem B and figure out what's wrong with it? I got a runtime error on test case 9, and my logic seems to be working fine for all cases I'm dry running it for. Thanks in advance! :) https://codeforces.net/contest/1148/submission/54942140

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no boundary check for j in here:

            while(b[j]<a[i]){
            // cout << "b[j]: " << b[j] << endl;
            // cout << "a[i]: " << a[i] << endl;
            // cout << "j: " << j << endl;
            j++;
        }
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. Finally submitted it successfully! :)

      → Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

How to solve G？ Or can anbody give me some hint for how to use gcd（ai，aj）>0 and 2k<=n?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone explain how to solve C.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

just curious why problem F is named Foo Fighters

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Because both Foo and Fighters start with F.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

54973406 My submission is Accepted after contest, but it's actually wrong. For instance, when get such inputs

6 3
18 75 245 847 1859 26

it outputs

6 5 4
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Added your tests into the upsolving, thanks!

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone's randomized solution for F pass the systests ?

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Editorial?, opening Codeforces after every 10 minutes just to see if editorial has been released.:-|

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for G that got accepted: 54972721 How??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I call that phenomenon "Let's create 150 random tests and not write shitty solutions to test their strength"

    → Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Editorial for this contest please.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I made a silly bug in F and still got accepted 55273526, so I scanned through the first page of standings and successfully hacked an accepted deterministic solution. 54935870

Egor.Lifar Can you add these testcases to upsolving testcases?

3
0 1
-1 2
-1 3

3
0 1
1 2
1 3

3
0 2
1 1
1 3

3
0 2
-1 1
-1 3
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems similar to Problem C, Crazy Diamonds

  1. 432C - Prime Swaps (Almost same statement)
  2. 1365B - Trouble Sort

It is interesting to note that this "temp variable" idea is repeated, and with each repetition the rating of the problem drops.

→ Reply