It can be done even easier, instead of treaps let's just store a sorted list of values. You can rebuild first and last block by merging two sorted lists, one with changed and the other with not changed values.

Sadly, even if we restrict the query to the subarray $$$[1, n]$$$ and $$$x$$$ to a particular value, say $$$x=0$$$, we believe there is no faster online solution than $$$\tilde{O}(\sqrt{n})$$$ per operation (even amortized). A reduction using Online Matrix Vector Multiplication (OMv) hypothesis can be shown.

Of course, you can easily achieve something like $$$\tilde{O}(\sqrt{n\log{n}})$$$ using sqrt decomposition.

I'm not sure about this at the moment, but probably same reduction can be done to show that you can multiply matrices in $$$\tilde{O}(n^2)$$$, if you can solve this problem (even offline) in polylogarithmic time per operation.


It's still same for me.

If you compress the string (skip zeroes), then you can get complexity n * A instead of n * A^2. In fact this is a problem from 18th POI.

And on the other hand if you have a graph you can for each edge (a, b) make a set {a, b} so these problems are equivalent.

In Round 3 — that was my final position. It doesn’t make much sense to use positions from previous rounds.

I was 150th in codejam last year and Google rejected me basing on my CV, so definitely that's not the rule :)

Yes, it’s kinda similar to the bubble sort. At each step add element to the end of the array and move it to the left until it will end at the good position.

Oh, you’re right. I’ve misunderstood the question.

In this task array is not sorted.

That's exactly problem from XXI POJ: Link. If you allow randomization then there exists even O(n+q) solution.


Solve more problems :)

On 998koverIZhO 2021, 3 years ago

Can you say how to solve D?

O(3^n) is OK, because the constant is very low, my solution passed in 0.5s/6s

On kuvimanAI Cup 2020, 3 years ago

Ok, I actually did it last year, so let's make it a tradition: I still didn’t get the t-shirt from 2018. Is there any way to contact somebody responsible for this?

On AckoBubble Cup 13 — Kick-Off, 4 years ago

Also there is a wildcard rule and the only one was given to team DEUSSS.

On AckoBubble Cup 13 — Kick-Off, 4 years ago


On kuvimanAI Cup 2019, 4 years ago

I’ve mailed you few days ago. Maybe there is a problem with google mails.

On kuvimanAI Cup 2019, 4 years ago

I've mailed them at 5th August and still didn't get the reply.

On kuvimanAI Cup 2019, 4 years ago

I still didn’t get the last year t-shirt. Is there any way to contact somebody responsible for this?


Huh, I messed something up, but I’ve come up with another solution. Let’s find the rightmost 0, we know it’d be the 0-th element. Also all elements before him, should move „one position to the right” so we add 1 to the elements, which were before this one. We can see that we can go on with this algorithm, so in every step: we pick rightmost minimum, add 1 to all elements before this one (on prefix) and then change this element to inf. We can handle this operations with seg tree.


Segment tree is enough, try to add elements from the last to the first one.


The key observation is that we don’t want to go very far and don’t want to speed very much. You should think about limits on those two values and then you can run simple bfs where the state is (position, current speed). Also maybe greedy or dp approach is possible — I’ll think about it.

On SHOToRSAVARE_KAZEMSHAHRsegment, 5 years ago

If x is fixed you can maintain two segment trees. First one is just simple add and get maximum. After each add operation you query for maximum on the whole sequence and until it’s greater than x add +1 on the second tree in corresponding place and add -inf on this place in the first tree. Complexity O((n+q)logn)

On ShashwatS1HELP Maximum Subtree, 5 years ago

Is there any online solution for this problem?

Hey, isn’t it problem from ongoing contest? Why you didn’t asked after end of the contest?

I think it's better to use actually implemented comparators. If you want to reverse priority queue to be min heap, you should declare it as follows: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>.

k*(k-1)/2 = C(k, 2)

As you are looking for the least amount of movements solution, just rearrange your backtrack to BFS-like algorithm. The vertices are board's "states" and the edge between two states is if we can do one move to achieve it. Of course it's pointless to compute whole graph, you can find edges if you are considering given vertex.

On kpw29Camp IT is for you!, 5 years ago

I guess this subset should be connected.

On kpw29Camp IT is for you!, 5 years ago

It's located in Milówka, Poland. The easiest way to get there is by train. Travel costs (non-premium tickets) — from Katowice ~15 PLN — 4 USD, Krakow ~17 PLN — 4.50 USD, Warsaw ~60 PLN — 15 USD, Gdansk ~70 PLN — 17.50 USD. I think the most expensive are flight tickets, just check them yourself.

Can you fix University of Wroclaw logo? It looks like you have Jagiellonian's University instead.

What does to 18 mean? Is it possible to participate for person A (birthday 1.01.2000) or for person B (birthday 1.12.2000)? How does it work? And why is it alongside with codejam round 2?