Quoting from the post : "Div. 1 and Div.2 editions are open and rated for everyone."

No its not wrong its technocup for both divisiors

Fixed. Sorry for the stupid mistake while copying.

Can I borrow your time machine. I would like to retake my math (yes MATH) test from last week. Thank you!

Why do you write this? Just curious

9 am to be precise... you guys have no mercy :/ Can you al least tell us the number of problems and scoring?

It's OK! You will win!

Where I live, the contest runs from 12:05am to 2:05 am! And I still will be writing the contest :D

Competitive Programming >>>> Sleep >>>> School

the same question

you can calculate the suits that points change is zero, and substract it,than it's double the answer

Do not know about java, but in c++ I have heard there is PBDS for this purpose.

This task can be done using Binary Lifting

I used one segment tree, with finding the kth in the query, but it is not implemented in java :/

I think there is no such thing in Java. You need to do Binary Search and Segment Tree query to get the nth element.

You can use segment tree with operations: add 1 in point, find nth element. It's quite simple to find nth element. You just run from node v = 1 in tree and check whether the sum of subtree of left son is bigger than n. If it is then you look for (n-sum[left_son])th element in subtree of rightson. Otherwise you look for nth element in subtree of leftson.

i solved it using ordered_set in pbds in c++,but in java you can use binary lifting technique,follow this, you can use this type of method

I think that it was also a lot of "implementation-forces" too?

You can't. C++ set is not addressable.

you can have an iterator and then use advance().

set<ll> st;
int position = 4;
// fill up the set
auto iter = st.begin();
advance(iter, position);
// iter is now on 5th position.

Can't do that in set since it's complexity will be O(n) which is not optimal in most of the required cases.

Use find_by_order from the Policy based data structure.

link

I do not think you can. Try to use __pbds or write a segment-tree/BST instead.

1
3
1 3
2 2
6 7

answer 4

1
3
1 5 
1 4 
7 9 
answer is 7-4=3
and this
1 
3
1 5 
2 3 
7 9 
answer is 7-3=4

try this : 1 3 1 5 2 3 4 7

answer >>> 1

It is. With super cache-efficient binsearch, it wouldn't be a problem, but both BFS and partial sums on such huge arrays are costly simply because we need to jump between rows.

Did you try BFS with a custom queue (static buffer + pointer to front)? In my experience, it can be really damn faster than std::queue.

I got AC (~500ms) 65655948 using prefix sums, without any optimization.

Weird... I just did binary search + bfs with the same complexity without consciously optimizing anything and it passed in 343ms.

Let's put aside the question about tight limits for now. The problem in your solution is next: Instead of $$$O(n \cdot m \cdot \log(\min(n, m)))$$$, your solution is actually $$$O(n \cdot m \cdot \log(\max(n, m)))$$$, because checking

if (ans + step > n && ans + step > m) continue;

is wrong.

P.S.: Sorry for being a slowpoke.

It can be solved using dp with n^2 states. If the adjacent two values are equal then whatever value you give to the current index it won't affect your answer. If they are not equal then we have 3 cases 1. Difference between next suite and current suite added by 1 2. Subtracted by 1 3. Remains same.

Such solution is quite obvious, so I guess it was intended to get MLE.
It seems we can optimize one of logs by processing bits one by one, so instead of storing all result ranges in form $$$[X, X+2^K)$$$, we should generate and process them iterating over K.

The memory limit indeed seems too tight. Naively writing the obvious solution uses around $$$(100 \cdot 2 \cdot \log(10^{18}))^{2} \approx 1.4 \cdot 10^{8}$$$ memory so the limits could be much higher. I had to do memory optimization on my correct solution (65667891) with memory usage around $$$4 \cdot 100^{2} \log(10^{18})$$$ to get it to pass (65668033)

The trick to optimise from $$$100^{2} \log(10^{18})^{2}$$$ to $$$100^{2} \log(10^{18})$$$ is just to notice that you don't have to check all pairs of dyadic intervals, you can just loop dyadic intervals formed from the first list and regular intervals from the second list, then do the same the other way around. For every pair you have to add at most 4 intervals.

This also shows that maintaining the intervals dynamically doesn't use too much memory.

3
1 3
1 3
1 3
ans = 0

If left<right, the answer is 0.

Answer the queries offline. Sort all the queries on the basis of k first. Then use PBDS or BIT to find the value at index j in sorted array for prefix.

For D1, sort the array in increasing order values and decreasing order of indexes so that we can get the lexicographically smallest subsequence from the end of array for each query.

For D2, I solved it offline

1. Sort queries by their increasing length
2. Since length of queries is sorted, we can keep inserting elements into a treap/policy based data structure(pbds) such that it has number of elements equal to the length of given query.
3. Give kth smallest element from the treap.

Solution

I'm not sure this is best way but...

You shouldn't minimize number of operations so as first step you can just sort your array: ()()(()) -> (((()))) Second step is to change array to satisfy number of k: one of easy ways is to swap second element with first opposite: first swap: (((()))) -> () ((())) k=2, second swap: () ((())) -> ()() (()) k=3, etc...

I solved the question the following way.

12 1
))())()()(((

• First convert the string into a string with maximum possible prefixes. ()()()()()()
• The above conversion can be performed with n / 2 operations ( Not sure how to prove this yet. But I basically brute forced to match every element)
• Then depending on the value of k, one can start decreasing the prefixes one by one.
• The prefixes can be decreased by 1 in each step by swapping adjacent elements starting from 2nd index.
• Swapping 2, 3 gives (())()()()(). The number of prefixes decreases by 1.
• Then swapping 4, 5 gives (()())()()(). The number of prefixes decreases by 1.
• Similar operations can be continued until the number of prefixes becomes 1.
• The above operations are also n / 2. So we'll never exceed total operations n.

Link to solution

Take the interval between leftmost of endpoints and rightmost of start-points of intervals.

Same :(

I prefer it, what is your issue with them exactly? Seems like a nice way to give you some partial credit for working on a problem but failing to fully solve it. A trade-off between IOI and ACM style.

The same here. Vote you up! Subtasks are also boring for me and make me upset.

I don't know if I agree with you or not because more often than not I just end up ignoring the smaller subtask, but it's weird for sure. I've seen 2 interesting subtasks in cf the rest feels like filler problems.

I think we should take a vote

I think it makes more sense to add easier versions of tasks in Div 2 contest and harder version in Div 1 contest, or maybe something in between. Subtasks are necessary for Div 2 to make the difficulty gap smooth, especially when problems are shared between divisions.

Unfortunately undefined behaviour does not guarantee a RE, so the $$$O(N^2)$$$ loop triggered TL before the out-of-range managed to trigger RE.

This is why undefined behaviour is annoying, you have no guarantees on what will happen.

The color was updated but the rating wasn't after ratings were updated for this round. May be a caching issue.

qoqoqoqo did 2 contests at the same time today

Used unnecessary hash, and the modulo is $$$998244353$$$

It has 2 regular prefixes. () and ()((()))

Probably you were using operation {i,i} and wanted to flip i'th character from '(' to ')' or vice versa. And came to the conclusion because of the checker's response.

It seems like FFT/NTT but it can be solved in an easier way...

If you work out the formula in a mode like DP

Let a[n+1]=a[1], dp[i][j] stands for the first i problems new solution has j points more than the previous one.

You can work out such a formula:

if(a[i]!=a[i-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]+dp[i-1][j]*(k-2);

else dp[i][j]=dp[i-1][j]*k

You may realize this means...

Let g=sum(1,...,n)[a[i]==a[i+1]], h=n-g

Your answer is sum of (r[1],r[2],...,r[n]) in f(x)=(r[0]+r[1]x+r[2]x^2+...)+(r[-1]*(1/x)+r[-2]*(1/x^2)+...)

And f(x)=k^g * (x+k-2+1/x)^h

(This is really an NTT problem !)(deleted) :)

It can be concluded that r[i]=r[-i]

So the answer is (r[-inf]+...+r[-1]+r[1]+...+r[inf])/2 = (r[-inf]+...+r[-1] +r[0]+r[1]+...+r[inf])/2 — r[0]/2

The highlighted area is obviously (k^n)/2 (let x=1, f(x)=(r[-inf]+...+r[-1]+r[1]+...+r[inf]) = k^(g+h) = k^n) , and we now only need to work out r[0].

Then we can expand f(x) = k^g * (x+k-2+1/x)^h

Let C(n,r) be combinatorial number:

Then it is nothing but combination problems...

r[0]=C(h,0)*C(h,0)*(k-2)^(h)+C(h,1)*C(h-1,1)*(k-2)^(h-2)+...+C(h,i)*C(h-i,i)*(k-2)^(h-i*2)

This is my code and you might better understand my explanation after rreading it.

65652697

Great use of Persistent Segment Trees!!!

Hello Leonardo_Paes,

Can you help with the logic you've used? Basically how you're dealing with the children nodes and how persistence helps here?