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.

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:

- KAN and budalnik for the round management.
- 300iq for creating a great problem that has naturally fitted in our set of problems for this round.
- to all testers: antontrygubO_o, 244mhq, andrew, Mediocrity, Vaseline_Warrior, g1phy, nweeks, ptd, phattd, dmitriyklebanov, Alladdin, wxhtzdy, Shinchan01, Fasys and sovspace.
- MikeMirzayanov for Codeforces and Polygon systems.

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

**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 — 1500 — 1500 — 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

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

And a new iPad for Um_Nik

I will not be surprised if tourist starts his own macbook store

The biggest Apple store ever lol

tough life :(

tdpencil i am jealous of your contribution.

I invite everyone to participate in the selection of prizes for the top3 of the next round. The participant whose set of prizes gets the most likes will receive a T-shirt :)

P.S.We won't be able to give teslas to the winners100% ownership of Deltix.io to the winner

https://imgflip.com/i/5l3mke (unrated can't post images sob).

Now you know what to give as prizes next round

I propose @jiangly gonna win that one.

He missed it!

Don't post things we already know.

Of Course! How is anyone going to have enough space for 11 mac books? Imagine all the warranty costs and electricity!

oh!

jinxed

For me ,the blog looks really attractive and fascinating

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

Quality problems for all,quality prizes for some

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

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

It seems that it'll stop after about 1 minute...

But to tell the truth I was scared at first too.

that scared me first

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

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

150 minutes or 135?

150 minutes

`Successful hacking attempt`

rejudging....`UnSuccessful Hacking Attempt`

[deleted]

good luck

Me too!

GREAT!

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

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

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

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

It's time to upsolve Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)

i hope i dont win nullptr again.

did anyone got those randomly distributed t-shirts ?

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

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

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

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

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

The animation that links to the main site is so cool

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

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

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

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

I think i can't come under 1k

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

Tourist after reading comments of this blog.

![ ]()

Probability of

YOUto get a t-shirt: 0.0000000000000000000000001*0.1 = 0.00000000000000000000000001Tourist's Macbook has a update feature, he doesn't have to buy the lastest version.

Are you ready to shave your head? https://codeforces.com/blog/entry/93138

Bro, there are still 4 and a half week to go :(

There are just 4 and a half week to go .all the best bro

Is it possible to get MacBook Air from Tourist?

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

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

DontLookBack is all I will say on this.

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

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

SpoilerHope this contest will be another big surprise!

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

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

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

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

I love rotavirus

Ok,but she might like you only if you are straight

of course she loves herself

he*

enjoy being blocked

Sure ,we will enjoy

I'm curious about scoring distribution. Any predictions?

Please update the scoring distribution fast

Ok

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.

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

added, sorry for the delay

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

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

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

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

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

Not everyone is a LGM.But hopefully one day I will become LGM and then take your recommendation

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

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

great contest !!

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

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

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

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.

Thanks for the interesting problems! Really enjoyed problem E

Yes! Problem E was very beautiful! :)

Could only solve A, -91 incoming KEKW

Big dislike for Bs "funny" overflow twist.

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

Answer can be bigger than 1e9.

I used int to store my answer and it got accepted.

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

Feedback on the problemset.

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

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.

This aged badly.

Like milk lol.

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.

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.

CodeMy bad. No wonder many people solved this. Thanks for sharing.

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

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

same

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

i can't take this

Also include tc 17 in that list :(

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

The only prerequisite for D is this equation ->

a + b = a&b + a|bare there any more tips like this one?

I remembered this property because of this bloghttps://codeforces.com/blog/entry/84150

thanks man.

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.

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

D is (almost) a copy of https://codeforces.com/contest/1451/problem/E1

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

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.

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.

Isn’t that considered cheating ? Just asking.

No

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

Is 4^n meant to pass in F?

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

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

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.

H requires constant optimization.

how to solve C

stack + dp

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.

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

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

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)

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.

problem D is same as this problem.

Without the xor operation, how is it the same?

(A ^ B) = (A | B) - (A & B)

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

For array

`6 6 1`

, the`j`

you are finding in the inner loop will be`-1`

, resulting in runtime error.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.

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

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

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

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.

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.

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.

Edit: Somehow the wrong solution also passed system testWeak 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 submission127388621

My counter exampleThe correct answer is

`-1`

but my code outputs`1`

and somehow none of the pretests have any sort of these.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

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:

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

Any hints for B?

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

Anyone wants to share his thought process for problem B.

I have shared that above.

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

Wtf, My C — O(N^3) passed.

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 ?

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

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?

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

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

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

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

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

need moar tosters!

Weak Pretests and System Tests are like s**t

I spend so much time thinking the reason why I only need to output the

k-th smallest elementin Problem D. I thought it would be very important. However, it doesn't.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!

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

Edit: they did but they were so late

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

One of the best rounds in a while.

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

The pretests of Problem B is too weak lol.

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

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.

An amazing fst about B

I submit ↓ get a fst T_T

then I find bug long time find:

can AC

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

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$$$.why tourist is not in top 20...after solving 1st 6 problems in 30 minuits :[

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.

how to solve C?

When would be editorial out?

https://codeforces.com/contest/1556/hacks?verdictName=&chosenProblemIndex=G

The official solution of G (maybe) gets TLE.

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.

Thanks!

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!

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

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

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

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.

Ah yes,the problem D is very similar to this problem:1451E1 - Bitwise Queries (Easy Version)

And the trick in F is basically the same with this.

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

Maybe after the anti-cheating check.

Yes, you are right :)

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

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

opandcl, 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

opat that position andclat 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 answerMy Solution

Any help will be appreciated

Fantastic ! ! ! ! https://www.youtube.com/watch?v=L0Z3XyVKmZw

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

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

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

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

Did you use codes from this comment?

Yes I set len = 1000 . But it seems that "within 1000" means 1 to 999.

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.pyrandgen.cppWhat's the meaning of

`private messages`

?By Codeforces's usertalk ?

upd : oh I know, sorry.