By deltixlab, 21 month(s) 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. fantasy
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?
»
21 month(s) ago, # |
  Vote: I like it +234 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

For me ,the blog looks really attractive and fascinating

»
21 month(s) ago, # |
  Vote: I like it +56 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +107 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    i was startled by that gif, SO SCARY!!!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that it'll stop after about 1 minute...
    But to tell the truth I was scared at first too.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that scared me first

»
21 month(s) 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.

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

150 minutes or 135?

»
21 month(s) ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

[deleted]

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    21 month(s) 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%

»
21 month(s) 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. ʕ•ᴥ•ʔっ

»
21 month(s) ago, # |
  Vote: I like it -21 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

i hope i dont win nullptr again.

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

did anyone got those randomly distributed t-shirts ?

»
21 month(s) 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!

»
21 month(s) 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?

  • »
    »
    21 month(s) 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 :)

»
21 month(s) 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

»
21 month(s) 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 . :))

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

The animation that links to the main site is so cool

»
21 month(s) 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

»
21 month(s) 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.

»
21 month(s) 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

  • »
    »
    21 month(s) 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...

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to get MacBook Air from Tourist?

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      DontLookBack is all I will say on this.

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    Spoiler
»
21 month(s) 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:

»
21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

I love rotavirus

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm curious about scoring distribution. Any predictions?

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Please update the scoring distribution fast

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 4   Vote: I like it -32 Vote: I do not like it

    Ok

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    added, sorry for the delay

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +40 Vote: I do not like it

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

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

great contest !!

»
21 month(s) 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... :(

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
21 month(s) 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).

  • »
    »
    21 month(s) 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?

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

Thanks for the interesting problems! Really enjoyed problem E

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes! Problem E was very beautiful! :)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Could only solve A, -91 incoming KEKW

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Big dislike for Bs "funny" overflow twist.

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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.

»
21 month(s) 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 :)

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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
  • »
    »
    21 month(s) 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 :(

»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    same

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

     i can't take this

  • »
    »
    21 month(s) 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 :-)

»
21 month(s) 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

»
21 month(s) 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.

»
21 month(s) 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!

»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    21 month(s) 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.

»
21 month(s) 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.

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Is 4^n meant to pass in F?

  • »
    »
    21 month(s) 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)$$$.

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    H requires constant optimization.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    stack + dp

    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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)

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +59 Vote: I do not like it

problem D is same as this problem.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    Without the xor operation, how is it the same?

»
21 month(s) 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

  • »
    »
    21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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
  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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
    
  • »
    »
    21 month(s) 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).

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for B?

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone wants to share his thought process for problem B.

»
21 month(s) 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

»
21 month(s) 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 ?

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Weak Pretests and System Tests are like s**t

»
21 month(s) 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.

»
21 month(s) 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!

»
21 month(s) 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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

One of the best rounds in a while.

»
21 month(s) 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 :(

»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

The pretests of Problem B is too weak lol.

»
21 month(s) 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).

»
21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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$$$.

»
21 month(s) 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 :[

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

When would be editorial out?

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it
  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +53 Vote: I do not like it


      Thanks!

      • »
        »
        »
        »
        21 month(s) 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!

»
21 month(s) 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!

»
21 month(s) 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? :)

»
21 month(s) 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;
  }
}
»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +90 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it -72 Vote: I do not like it
»
21 month(s) 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 ?

  • »
    »
    21 month(s) 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

»
21 month(s) 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!

  • »
    »
    21 month(s) 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
    
»
21 month(s) 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 fantasy
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 Heltion
20 1556 20 MonkeyKing
21 1556 21 Nyaan
22 1556 22 tourist
23 1556 23 ksun48
24 1556 24 greenheadstrange
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 cabbit
34 1556 34 dlalswp25
35 1556 35 Rubikun
36 1556 36 Karry5307_AK_NOI2023
37 1556 37 hitonanode
38 1556 38 MoRanSky
39 1556 39 QAQAutoMaton
40 1556 40 q-w-q-w-q
41 1556 40 receed
42 1556 42 cnoi
43 1556 43 endless-chase
44 1556 44 huhaoo
45 1556 45 risujiroh
46 1556 46 DmitryGrigorev
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_Farmon
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 HeinzGuderian
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 SirRembocodina
208 1556 208 est_stella
209 1556 209 torisasami
236 1556 236 youbot
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 kerO_o
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 ikuyo_kita
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 Puranya_
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
  • »
    »
    21 month(s) 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.