When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By deltixlab, 3 years ago, In English

deltix

Hi Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

  • aggregation, storage, and processing large volumes of time-series data
  • data modeling
  • testing and deployment of quantitative models

In our team we value such skills as:

  • knowledge of algorithms
  • high-performance coding
  • low latency data streams processing

We are excited to announce that one of our products TimeBase Community Edition joined a FinTech Open-Source Foundation (FINOS) on the 14th of July.

TimeBase is a multi-faceted, open-source data-streaming powerhouse, combining a time-series database, message broker, data modeling, and a well-optimized serialization framework. Originally, TimeBase was designed to address use cases in the financial domain. Nevertheless, we take on new challenges in other areas such as IoT, cloud computing, clustering, high-performance computing, parallel data processing, and Big Data to name a few.

Learn more about DELTIX

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the second installment of our rounds (joined Div. 1 and Div. 2) — Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on Aug/29/2021 17:35 (Moscow time).

It is an open and rated round for both divisions.

We have prepared the following trophies for you:

  • 1st place = MacBook Air
  • 2nd place = iPad Pro
  • 3rd place = iPad Air
  • 1-100 = branded t-shirts

Another 100 t-shirts will be distributed randomly between participants outside the top-100 but within the top-1000 and who participated in rated Codeforces rounds before.

All problems, except the last one, have been prepared by members of our team: Vladik, netman and AleXman111.

We would like to say a word of appreciation to:

We will offer participants 8 problems and 150 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in employment opportunities or would like to speak with recruiters or members of our team.

Contact Form →

UPD: After processing all testers' feedback, we decided to extend the competition by 15 minutes. The total duration is 150 minutes.

UPD2: The scoring distribution is 500 — 1000 — 15001500 — 2000 — 2500 — 3000 — 3500. Note the equal complexity of C and D.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. Rewinding
2. jiangly
3. Benq
4. Egor
5. TLE
6. ainta
7. Radewoosh
8. Golovanov399
9. ecnerwala
10. maroonrk

  • Vote: I like it
  • +595
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +234 Vote: I do not like it

Another Mac Book for tourist? He has like 10 of those.

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

For me ,the blog looks really attractive and fascinating

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

Another Deltix round. Just really love these rounds. Quality problems, quality prizes.

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

    Quality problems for all,quality prizes for some

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

Who else was surprised by looking at that waving hand gif.....

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

I am really looking forward to these prizes which I can never win.

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

100 T-shirts for the top 101 to 1000. There is 1/9 chance if I get in there :D

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

150 minutes or 135?

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

    150 minutes

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

      Successful hacking attempt

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

        rejudging....

        UnSuccessful Hacking Attempt

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

        But how??? please also tell me

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

          The duration of this contest was 135 minutes initially. The author accidentally wrote 150 minutes in the blog. (later it was changed into 150 minutes)

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

[deleted]

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

100 in (100,1000], probability=1/9=0.1111.... :)

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

    probability of getting in top 1000 where div 1 users exists: 0.000001%

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

Hope problems statement will be less confusing then the last time. ʕ•ᴥ•ʔっ

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Div1 + Div2 is really good opportunity for anybody to develop programming skills

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

i hope i dont win nullptr again.

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

did anyone got those randomly distributed t-shirts ?

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

Visit the site guys, you won't regret. Also, good luck to everyone!

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

*Wind_Eagle's round announcement* Am I a joke for you?

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

    I am sure that soon it will appear above our announcement. By the way, I participated in testing and the round is cool :)

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

Tourist is going to open an apple store after this contest.you know why XD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice rewards but i don't think that I can reach top 1000th or less . :))

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

The animation that links to the main site is so cool

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

EDIT — Commented on this forum by mistake, wanted to comment on today's competition's forum

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I might be wrong but I thought initially they offered 150 minutes and now I see 135 minutes now.

»
3 years ago, # |
Rev. 3   Vote: I like it -30 Vote: I do not like it

Probability of Me getting T shirt 100/1000=1/10 Probability of Me coming under 1000 rank 0.0000000000000000000000001

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

    Your comment would have made sense if it was top 103 participants get 100 prizes...

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

      I think i can't come under 1k

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

        What's wrong with that? Only if 103 participants and total of 100 prizes, each participant can't get a prize.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 5   Vote: I like it -26 Vote: I do not like it

          Tourist after reading comments of this blog.

          ![ ](20210828-114412)

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

    Probability of YOU to get a t-shirt: 0.0000000000000000000000001*0.1 = 0.00000000000000000000000001

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

Tourist's Macbook has a update feature, he doesn't have to buy the lastest version.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to get MacBook Air from Tourist?

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

    Forget that, I still have not got my t-shirt from the last deltix round.

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

      What was happened to them, I haven't seen anything about the random t-shirt winners?

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

      DontLookBack is all I will say on this.

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

To tell the truth, when opening codeforces, this moving arm is really scary.

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

    Oh no, he just wants to give you a big surprise.

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

the problem set of the last delix round was hard to me D:

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really want to reach CM in the last contest in my summer hoilday TAT

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

    You got this :) Btw you have a very interesting rating graph lol

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

    I have to do something else so i can't enter it qaq

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

I love rotavirus

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm curious about scoring distribution. Any predictions?

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

Please update the scoring distribution fast

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it -32 Vote: I do not like it

    Ok

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

      Hello. We sent all the T-shirts to codeforces and I am sure they will be delivered to all the winners soon.

      We could not start printing T-shirts before all participants submitted their actual data.

      Sorry for the delay, but I don't know how to make this process faster.

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

        It's okay ,in fact thanks for interesting contests and interesting prizes.

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

    added, sorry for the delay

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

      It's ok.It's nice seeing you guys being responsive

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

        Yes ,that's the reason i took back my false words and appreciated their hard work

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

As a tester, I recommend you to solve all problems!

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

    Not everyone is a CM bro, I think you meant read all the problems :P

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

      actually for us even reading all the problems isn't recommended during contest understanding a problem will drain our small brain battery (small is for the battery not the brain XD) So that could affect our ability to solve a,b,c,d so read all the problems after the contest unless you see a problem being solved alot

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

As a tester, I confirm that problem statements are to the point, no long stories.

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

as a participant I couldn't even solve 2nd problem :"(

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

great contest !!

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

Being a noob, I don't know how people solve interactive problems like D... :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
3 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Problem D is effectively an easier version of 1451E1 - Bitwise Queries (Easy Version) (use sum = or + and to get other elements as well since we don't have xor here, it works since we have 2n queries anyway).

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

    Is that not the intended solution? If so, is there any other solution?

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

      I meant "easier" in the sense that without the xor that problem has its slightly more trivial. In that problem you have to make all the observations in this problem + another 2 xor observatioss (one to get it from 2n to n + 3, one to get it from n + 3 to n + 2).

      Also I should note that while that problem has $$$[0, 2^n - 1]$$$, the soln for E1 can solve arbitrary ranges like in this problem, only the E2 soln needs that exact range.

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

Thanks for the interesting problems! Really enjoyed problem E

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

Could only solve A, -91 incoming KEKW

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Big dislike for Bs "funny" overflow twist.

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

    can you explain what it is? it was so disheartening to not be able to solve what seems like an easy problem

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

    Rip my rating. It would've been great if one of the pretests had the maximum constraint values. Oh well.

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

Feedback on the problemset.

  • A: Cute cakewalk problem.
  • B: Ok standard easy problem (though a bit hard for its position). I don't see why you decided to consider parities instead of giving an array of zeroes and ones.
  • C: Amazing problem. The statement is clean and asks a very natural question. The difficulty is appropriate for its position. For some reason, I liked this one a lot (most likely, because the solution is just so clean and does not require any advanced technique). I was wondering if it can be solved in pseudo-linear time.
  • D: Nice problem. For me, this required some serious thinking, but the standings suggest that it is not as hard as I perceive. Maybe I perceived this one as hard because I did not realize for a long time that if I know $$$x, x\text{ and }y, x\text{ or }y$$$ then I know also $$$y$$$.
  • E: Nice problem (but a bit standard). I was pretty annoyed by the fact that the word "even" was not highlighted in the statement and the first pretest which catches the bug of allowing also sequences of odd length is the 17th. Moreover, I don't see how asking for answers on intervals makes the problem more interesting than asking just for the answer on the whole array.
  • F: Very nice problem. Knowing the chain-structure of the strongly-connected components of a tournament, this one felt easy for its position.
  • G: I just read the statement, which is amazing.
  • H: Not read.

Overall, there was not a single problem I disliked, and more than one that I really liked. The only complaint I have is that the difficulty-gap between F and G was huge, which made the contest a speed-contest for those with a rating similar to mine.

As a final remark, the images were awesome (it's the first time ever I appreciate images in statements). Whose the author of the images?

I really enjoyed taking part in the contest, which seemed to be really well-prepared. Thanks to the authors :)

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

    For C, I have a stack solution that should hopefully work in O(N).

    Solution — https://codeforces.com/contest/1556/submission/127374965

    The idea is that you keep track of open bracket sequences and completed ones in a stack and update accordingly. It works in O(N) because each value either adds a new entry in the stack or deletes a few.

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

    Hey, Is E that easy to solve ? Also there are so many people solved E. I thought of this way, we can take, if a[i] < b[i], then consider there are b[i] — a[i] opening brackets are there and else a[i] — b[i] closing brackets. So, for each i, we want to know what is the closest j, where if l = i and r >= j, then it becomes impossible to solve. But it seemed very tedious and on top of that the query is also asked on segments.

    If it is just the whole array, then it becomes very simple right ? as you can just do that above easily.

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

      The actual solution requires a few more observations but is easier to implement.

      If you take a range $$$[l, r]$$$ and toy around with the equations of what you need to add to balance elements in it from left to right, you'll see the addition requirement at a position $$$i (l \leq i \leq r)$$$ after fixing all positions $$$[l, i - 1]$$$ is just $$$\sum_{j = l}^{i} {b_j - a_j}$$$. This implies that $$$\sum_{j = l}^{r} {b_j - a_j} = 0$$$ must hold for the subarray to be fixable. Additionally we can notice that if $$$\sum_{j = l}^{i} {b_j - a_j} \lt 0$$$ for some $$$l \leq i \leq r$$$, then we can't fix this subarray as we can't fix the range $$$[i, l]$$$.

      The first can be checked with prefix sums, and the second with a range min query on the prefix sums.

      Otherwise we can notice that if we have a prefix of the subarray $$$[l, i]$$$ with $$$\sum_{j = l}^{i} {b_j - a_j} = x$$$, we have at least $$$x$$$ positions that will be the first position of some operation since there is no position with $$$b_j - a_j \lt 0$$$ which can appear before it in a chosen operation subsequence. So the answer is just the maximum value of $$$\sum_{j = l}^{i} {b_j - a_j}$$$, this can also be calculated using range max query on prefix sums.

      The implementation is pretty short except for the actual RMQ template.

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

    I missed the word "even" in the 5th question and was stuck on wa on test 17th. I think this should be highlighted given, they represented the sequences ending with dot. But, this is error from my side, have to be careful from next time :(

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

Problem C test 13. Couldn't debug my code.

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

    same

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

      Impatient to see solution of B and C . I struggled a lot today.

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

     i can't take this

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

    For me, it was: Wrong answer on pretest 20

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

    I also couldn't pass problem D pretest 13, and just worked out why. For some queries, I was passing the wrong index — I had an off by one error in queries beyond the first three. So I think 13 is the first test case where the answer is not in the first three numbers. I feel very silly :-)

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

The only prerequisite for D is this equation -> a + b = a&b + a|b

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, is there any way to solve E if we can choose an integer $$$x$$$ and increase / decrease the specified elements by $$$x$$$ instead of using 1 each time? I misread the statement and tried to solve this for quite some time.

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

My solution to G (which passed pretests) runs in 4.5secs and takes 1130MB of memory in the worst case. Oh, woe is me!

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

C murdered my brain I felt I was so close :(

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

    Yup, here is the comment I was going to write. Weirdest problem for me as it looks so easy and still I don't have an approach I can have confidence in. I threw everything I had at it and it is still unsolvable, waiting for the editorial, yey.

»
3 years ago, # |
Rev. 4   Vote: I like it -20 Vote: I do not like it

https://codeforces.com/problemset/problem/727/C (same as today's D because a+b = a&b + a|b)

found this by googling and solved.

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

In Problem E, I didn't find that k is always even, so I wasted my time for meaningless debugging. sad.

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

Is 4^n meant to pass in F?

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

    My solution was $$$O(n^2 \cdot 2^n + n \cdot 3^n)$$$.

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

    I got my solution passed after the contest and it is O(4^n).127393758

»
3 years ago, # |
  Vote: I like it -73 Vote: I do not like it

C and D are just boring standard problems.

E is yet another prefix sum transformation problem.

F is basically a rip-off of this.

0 interesting ideas out of the first 6 problems.

At least there is no problem which requires constant optimization.

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

    H requires constant optimization.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C

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

    stack + dp

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

      Not really necesary, you can solve it easily in $$$O(n ^ 2)$$$ by taking all opening brackets associated with a certain position $$$l$$$, then iterating from $$$r=l+1$$$ onward as long as it can be a valid bracket sequence, eliminating matching ranges, it leads to a pretty simple and elegant solution.

      Code
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah I know, I overkilled it, that's why missed few corner cases and got few WA.

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

        can you elaborate on the intersection part? (what is lto, lfrom, ...)

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

    Hint 1: Take the number of closing brackets as negative. Сount the current amount.

    Hint 2: Start from every odd position (Open brakets)

    Hint 3: For each starting position, go through all the positions and try to remove some of its brackets (Do not use some opening and some closing ones for the current position).

    Hint 4: Remember that you may have a lot of opening brackets that you need to use (you have the right to remove only the starting ones)

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

Felt really good when I submitted B and C, only to have that feeling snatched away by pretests 2 and 9 respectively :(

Great problems though, interested in knowing the corner cases.

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

problem D is same as this problem.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my problem B code giving run time error? Can anybody please help me? https://pastebin.pl/view/95d9737e

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

    For array 6 6 1, the j you are finding in the inner loop will be -1, resulting in runtime error.

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

For problem H, I think we need to fix the edges between the k special nodes (since there are at most 2^10 such ways) and then use min cost matroid intersection for the rest of the edges, thought about the solution, but couldn't implement it during the contest.

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

    I just coded that and it seems to be too slow for a big case.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    It works. Unfortunately, I was too dumb to realize that out of the edges connecting vertices $$$k+1\ldots n$$$, you only need to include those that are part of the MST of vertices $$$k+1\ldots n$$$, so I spent a lot of time optimizing (and eventually passing) my solution that was a factor of $$$n$$$ too slow (matroid intersection on $$$O(n^2)$$$ edges). :P

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

      It looks like I need to optimize my weighted matroid intersection code :(

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

      There are few AC submissions only adjusting the answer greedily, check these:

      127391319 and 127391995...

      The first one is just finding and applying the current optimal exchange operation repeatedly. And the second one is applying any cost-reducing exchange it finds (with random and time trick).

      I think if we can prove that there always exists a path from any non-optimal to optimal solution (similar to those k-maximum spanning trees or degree-restricted spanning trees algorithm), these solutions are correct. Since the maximum answer is n*maxw, and each time your answer will definitely decrease.

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

How to solve E, many people solved it ? I thought of this way, we can take, if a[i] < b[i], then consider there are b[i] — a[i] opening brackets are there and else a[i] — b[i] closing brackets. So, for each i, we want to know what is the closest j, where if l = i and r >= j, then it becomes impossible to solve. But it seemed very tedious and on top of that the query is also asked on segments.

  • »
    »
    3 years ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    Construct a bracket sequence as you've described. It is impossible if the bracket sequence is not a correct bracket sequence. Otherwise, the answer is the maximum balance of open brackets and closed bracket on a prefix, since each operation corresponds to the removal of one or more adjacent open and closed pairs, e.g., xxxx()xxx()xxx()(), and we will always try to remove the adjacent pairs that reduce the maximum balance.

»
3 years ago, # |
Rev. 5   Vote: I like it +56 Vote: I do not like it

Edit: Somehow the wrong solution also passed system test

Weak pretests for E

I found a counter-example for my approach that passed pretests but I'm sure will fail system test because I forgot to handle one impossible case. (When there exists a negative prefix sum of $$$b[i]-a[i]$$$ starting from $$$l$$$ in a query)

Can't believe that there are 20 pretests yet none that there are none that targeted this rather common mistake

My submission
My counter example
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +40 Vote: I do not like it

    Wow lol my code doesn't pass that case either since I had a typo in my segtree :\ also wondering why pretests didn't have anything similar to this.

    EDIT: Systests weak too lol it passed

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

    Same, my solution only uses a min RMQ and doesn't use a max RMQ to check the sum is always negative.

    The systests are weak so it passed LMAO.

    Counter example:

    2 1
    2 0
    1 1
    1 2
    
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Now I suspect the test generator generates $$$\sum_{1}^{i} b_i - a_i >= 0$$$ at all positions and just chooses $$$0$$$ positions for the queries. Now I'm curious if the author's soln even handles it (not that it matters since no correct soln got rejected and there is a provable soln).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for B?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Store the frequencies of parities If absolute difference between odd and even parities if greater than 1 then -1 Else either both parities are equal(n is even) or one parity is +1 of other (n is odd ) For n even ,you can place like odd even odd even.... or like even odd even odd For n odd ,you have to start with the parity which is in more frequency . Now for calculating swaps i just checked for 0 ,like what is the min ways to place a 0 at the desired position .if i do that for every 0 ,automatically 1 will get placed at proper positions My submission

    https://codeforces.com/contest/1556/submission/127355908

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone wants to share his thought process for problem B.

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

When you finally get an AC on problem C with a linear solution, then you find that the problem can be solved in quadratic. QQ

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a doubt. Why is the value of n given as 1000 for C, As this can be easily solved in O(N) time, is it to keep the answer within 64 bits ?

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

    There is an easy $$$O(n^2)$$$ solution to this problem. However, both you and I use linear solution which requires two stacks.

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

      yeah I know but they could have easily increased the value of n, as a linear solution exist, I am confused why keep n small?

»
3 years ago, # |
Rev. 5   Vote: I like it +144 Vote: I do not like it

I hate weak pretests.

Look at my code for B and E the first time.
B:if (tot=n/2+1) cout<<chk(1)<<"\n";else {puts("-1");return;}
Noticed that there is only one = in the code,but it can passed the pretest!
It can be hacked by datas like 1 3 2 2 2 but it passed the pretests.

E:int Max=max(mx[l][k],mx[r-(1<<k)+1][k])-d[l-1];int Min=max(mx[l][k],mx[r-(1<<k)+1][k])-d[l-1]; Noticed that the Max and the Min are same!!!
it can be hacked by datas like 2 1 2 1 1 2 1 2 but it passed the pretests.

Luckily I noticed these mistakes and resubmitted them.

These mistakes will be only made by few people,but both of them are wrong obviously.
I wonder why the pretest are so weak that these two obviously wrong code can pass the pretests.

I can't imagine how mad will I be if I don't find these two mistakes and get FST!!!

I want to say,it's not funny to make weak pretest and see a lot of $$$\color{red}{\mathrm{-1}}$$$ on the standings.

update:It seems that my first code for E can pass not only the pretests but also the system tests!I don't know how the gen work.

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

    This means there are no queries in the system tests + hacks, for which the minimum suffix sum of the interval $$$(a[l] - b[l], \ldots, a[r] - b[r])$$$ is negative and the maximum suffix sum is positive? How is that possible even with random samples?

    I must have misunderstood something in your code.

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

      Actually that means in the system test, for each $$$[l_i,r_i]$$$ :

      • $$$\sum_{i=l}^r a_i\neq \sum_{i=l}^r b_i$$$ , or
      • $$$\min(b_l-a_l, ..., b_r-a_r) \ge 0$$$ or
      • $$$\max(b_l-a_l, ..., b_r-a_r) \le 0$$$

      I think that maybe possible when the data is taking randomly.

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

        there $$$a$$$ and $$$b$$$ means the prefix sum of the arrays $$$a$$$ and $$$b$$$ in this problem :D

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

      Your understand is right.And that's why I say the system tests for E are very weak.

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

    Weak Pretests and System Tests are like s**t

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

I spend so much time thinking the reason why I only need to output the k-th smallest element in Problem D. I thought it would be very important. However, it doesn't.

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

I literally hated D. I thaught my solution was wrong just because I was finding the whole array within 2*n queries and thaught it was impossible to do so. However, all the other problems were great!

»
3 years ago, # |
Rev. 2   Vote: I like it -68 Vote: I do not like it

Why are jiangly solutions not being judged are they suspecting he's cheating or something?

Edit: they did but they were so late

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

why this submission can pass Problem E? 2 1 2 1 1 2 1 2 the answer of this Sample should be -1,but the result of this code is 0

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

One of the best rounds in a while.

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

Even D has weak systest in this set. My code that only uses the information of ai & ai+1, ai | ai+1 passes systest

it cannot distinguish 0 3 0 3 and 1 2 1 2 so it should be wrong and it prints wrong answer, but the systest is passed.

I think the problem was really nice but not data sets :(

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

The pretests of Problem B is too weak lol.

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

Lucky to get to the top 1000,So hopefully get a T-shirt (laugh).

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

The system test for the problem E is very weak.

For example, the code that outputs 1 in

2 1

2 1

1 2

1 2

passes the system test.

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

An amazing fst about B

I submit ↓ get a fst T_T

void solve()
{
    int n;
    cin >> n;
    int a[maxn]{};
    vector<int> b, s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            b.push_back(i);
        else
            s.push_back(i);
    }
    //...
}

then I find bug long time find:

void solve()
{
    int n;
    cin >> n;
    int a[maxn];
    vector<int> b, s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            b.push_back(i);
        else
            s.push_back(i);
    }
    //...
}

can AC

I used to think that initializing with {} wasn't too slow . I was wrong.

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

    You may initilize an array of maxn elements for $$$10^4$$$ times, that will certainly cause TLE. Note that it is guaranteed that the sum of n over all test cases does not exceed $$$10^5$$$.

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

why tourist is not in top 20...after solving 1st 6 problems in 30 minuits :[

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

For problem B , i converted array in such a way that for odd numbers from left to right i took them as 1 , 3 , 5...so on and similarly for even i took them as 2 , 4 , 6 ,......(like coordinate compression) and then calculated minimum adjacent swaps to get sorted permutation.

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

When would be editorial out?

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

    you are wrong, TL receives a solution from one of the testers, which we marked as correct. Please try the hack again, I removed this solution.

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


      Thanks!

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

        Thank you for complementing our tasks with test cases! I am sure that the participants who will solve these problems in the future will appreciate this. Apparently, we missed some extreme cases.

        Thanks!

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

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

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

Great contest! Most problems are nice. I like G, and H is a good and typical 300iq problem.

Maybe I could blame on the weak tests though? :)

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

How my implementation bug accidentally got me a lucky AC in F:

for (int mask = 1; mask < 1 << n; mask++)
{
  int bit = __builtin_popcount(mask);
  for (int submask = ...)
  {
    ...
    if (__builtin_popcount(submask) % 2 == bit) f[mask] += curF; // <---- this line does nothing
    else f[mask] -= curF;
  }
}
»
3 years ago, # |
Rev. 2   Vote: I like it -66 Vote: I do not like it

Hello,queueforces!:(

I used another account to take part in this contest,and in fact,I don't think this contest is of high quality.

Problem B 1556B - Take Your Places! is too hard for div2B(since its code is too long) and Problem D 1556D - Take a Guess and E 1556E - Equilibrium is too easy for div2DE.In fact, I think Problem D is very similar to a question in a CF contest before, and I will try to find the original question later.

In addition,for the first 10 minutes of this contest,I'm just waiting.In queue,In queue,In queue.This has seriously reduced my contest experience.

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

When will the list of random t-shirt winners be published?

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

tourist doesn't update his macbook, he gets a new updated one.....

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

Can anyone kindly help me to find the bug in my solution of problem C

at each index i maintain a list of open and close brackets using two arrays op and cl, ex.

A: 5 3 4 2
op: 5 0 4 0
cl: 0 3 0 2

Then I do the traversal in array from left to right and whenever I come to closing bracket index i, I do a traversal from i-1 to 0 where If I find the corresponding opening bracket I add it to my answer, and update op at that position and cl at position i, and during my traversal from i-1 to 0, all the j where cl[j] == 0, I add 1 to accomodate from cases like two regular bracket sequence besides one another [ ()() ]. I do this for all i from 0 to n-1 and output the answer

My Solution

Any help will be appreciated

»
3 years ago, # |
  Vote: I like it -72 Vote: I do not like it
»
3 years ago, # |
Rev. 2   Vote: I like it -45 Vote: I do not like it

Hi coders .. can you help me ? how can I begin in DP topics ?

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

    You can try Atcoder DP contest or CSES Dynamic Programming But I recommend you not to post this here , or you will get many downvotes , just like me

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

I'm sorry to ask this but when will the list of random t-shirt winners be published?Thank you very much!

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

    I made a list with seed = 12176 (Miracle03's score):

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 118 126 140 152 161 165 167 177 180 181 183 186 193 194 199 202 219 225 229 239 243 258 260 262 269 275 277 292 298 299 300 303 310 319 326 360 373 381 383 402 427 429 435 447 453 454 461 466 471 478 491 504 519 520 524 525 532 537 539 543 544 548 552 554 556 577 585 622 625 658 665 670 711 717 720 730 735 737 780 792 798 829 844 845 851 860 882 906 908 911 913 919 921 925 926 928 960 963 971 977
    
»
3 years ago, # |
Rev. 2   Vote: I like it +186 Vote: I do not like it

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1556 1 Rewinding
2 1556 2 jiangly
3 1556 3 Benq
4 1556 4 Egor
5 1556 5 TLE
6 1556 6 ainta
7 1556 7 Radewoosh
8 1556 8 Golovanov399
9 1556 9 ecnerwala
10 1556 10 ugly2333
11 1556 10 maroonrk
12 1556 12 nick452
13 1556 13 BigBag
14 1556 14 Um_nik
15 1556 15 tatyam
16 1556 16 yhx-12243
17 1556 17 Subconscious
18 1556 18 Maksim1744
19 1556 19 Sugar_fan
20 1556 20 MonkeyKing
21 1556 21 Nyaan
22 1556 22 tourist
23 1556 23 ksun48
24 1556 24 VivaciousAubergine
25 1556 25 gamegame
26 1556 26 SSRS_
27 1556 27 zscoder
28 1556 28 xtqqwq
29 1556 29 LJC00118
30 1556 30 Isonan
31 1556 31 kobae964
32 1556 32 abc864197532
33 1556 33 JettyOller
34 1556 34 dlalswp25
35 1556 35 Rubikun
36 1556 36 Karry5307_AK_NOI2024
37 1556 37 hitonanode
38 1556 38 MoRanAirConditioner
39 1556 39 QAQAutoMaton
40 1556 40 aaaaawa
41 1556 40 receed
42 1556 42 cnoi
43 1556 43 endless-chase
44 1556 44 huhaoo
45 1556 45 risujiroh
46 1556 46 gop2024
47 1556 47 orzdevinwang
48 1556 48 mango_lassi
49 1556 49 Amoo_Safar
50 1556 49 pikel_rik
51 1556 51 feecIe6418
52 1556 52 maspy
53 1556 53 tute7627
54 1556 54 uwi
55 1556 55 PinkieRabbit
56 1556 56 oleh1421
57 1556 57 Tlatoani
58 1556 58 _h_
59 1556 59 never_giveup
60 1556 60 kmjp
61 1556 61 leaf1415
62 1556 62 moe.tsuki
63 1556 63 Toxel
64 1556 64 Noam13
65 1556 65 noimi
66 1556 66 Egor.Lifar
67 1556 67 tzc_wk
68 1556 68 turmax
69 1556 69 AliShahali1382
70 1556 70 Monogon
71 1556 71 lucaperju
72 1556 72 AlexLuchianov
73 1556 73 ezLadder
74 1556 73 nutella_waxberry
75 1556 75 vkgainz
76 1556 76 eecs
77 1556 77 Farhod
78 1556 78 nuip
79 1556 79 Noam527
80 1556 80 dfcmd
81 1556 81 KADR
82 1556 82 fanache99
83 1556 83 hank55663
84 1556 84 Froggay
85 1556 84 dl720125
86 1556 86 minakami
87 1556 86 starusc
88 1556 88 BurnedChicken
89 1556 89 AQT
90 1556 90 dorijanlendvaj
91 1556 91 Itst_boyfriend
92 1556 92 Imagine076
93 1556 93 yuyue
94 1556 94 Aleks5d
95 1556 95 SirShokoladina
96 1556 96 sd0061
97 1556 97 kotatsugame
98 1556 98 magnified
99 1556 99 yzc2005
100 1556 100 wangziji
108 1556 108 _wrz_
110 1556 110 jtnydv25
112 1556 111 Karuna
118 1556 118 conan1412yang99
121 1556 121 natsugiri
131 1556 131 Rafbill
133 1556 133 se1ka2
135 1556 135 maximumSHOT
145 1556 145 MAOoo_Love_Molly
151 1556 151 AK-Dream
157 1556 157 Ant_Man
163 1556 162 ShadowLight
176 1556 176 jovialll
177 1556 177 PaiGuLong
179 1556 179 bthero
182 1556 182 noshi91
183 1556 183 pealfrog
185 1556 185 aesKawaii
198 1556 198 Kite_kuma
204 1556 204 rembocoder
208 1556 208 est_stella
209 1556 209 torisasami
236 1556 236 Pub
253 1556 253 cn449
258 1556 258 HailHomura
271 1556 271 Seyaua
272 1556 272 egor_bb
276 1556 276 lavish315
301 1556 302 Hemose
320 1556 320 ne_deyan
360 1556 361 2little2late
379 1556 380 cscse
382 1556 383 Septimelon
397 1556 398 pb0207
400 1556 400 AceKing
413 1556 414 average_frog_enjoyer
421 1556 421 phocom
441 1556 441 Cadillac
453 1556 453 18Michael
454 1556 453 lgzhy12138
470 1556 471 Nson
471 1556 472 WA_King
479 1556 479 Emiso
480 1556 481 Bohun
484 1556 485 eggag32
504 1556 505 Wailydest
525 1556 526 geschmack_cr7
529 1556 530 ExplodingFreeze
530 1556 531 RBurgundy
540 1556 541 Maezra6
548 1556 549 DimaTomsk
553 1556 554 syksykCCC
561 1556 562 LoadinGG
563 1556 563 Teja-Smart
575 1556 576 dannyboy20031204
581 1556 581 _FireGhost_
588 1556 588 ljcleo
603 1556 603 yash.gupta224a
608 1556 609 pooty
613 1556 614 TKT_YI
633 1556 634 GGN_2015
634 1556 634 Alchemi5t
636 1556 637 Setsuna
639 1556 637 Zesty_Fox
641 1556 642 spy20051623
647 1556 648 TheBlackDog
658 1556 659 retawB
666 1556 667 __23333
673 1556 673 b3ng
684 1556 685 clyring
688 1556 689 TearsFreeze
718 1556 719 -14
723 1556 724 ShJ
746 1556 747 BSBandme
752 1556 753 emthrm
770 1556 771 ouqingliang
774 1556 775 DDima
778 1556 779 TsukikoTsutsukakushi
783 1556 784 Misaka23336
787 1556 788 Aeon
789 1556 790 PsephurusGladius
811 1556 811 Kniaz
813 1556 813 Satoru
819 1556 820 Dormi
823 1556 824 MahiruShiina
830 1556 830 MaddyBeltran
860 1556 860 YanLei
879 1556 879 sapphire15
880 1556 879 ikaurov
884 1556 885 YxqK
887 1556 888 LoneNut
894 1556 894 zhylj
895 1556 896 Osaaama
913 1556 913 Kuzey
914 1556 913 apilat
928 1556 929 vaibhavvg
939 1556 938 this_is_ami
944 1556 945 Yahli
948 1556 949 flashsonic
952 1556 950 tobias.glimmerfors
  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +35 Vote: I do not like it

    What's the meaning of private messages ?
    By Codeforces's usertalk ?

    upd : oh I know, sorry.