It isn't brute force actually, the while loop runs for nlogn, it's the same pattern as n+n/2+n/3+..n/n, also the lower_bound call adds another factor of logn making it nlog^2n

Ya got it, so you are removing the candidates which don't have prefix of length l same so they wont be checked ever again, and in the worst case if no candidate are removed then its the same as nlog^2n when all char are equal. Great!

Do you have any proof for the upper bound when using hash? I did with zfunc worst case O(N* (logN)^2)

Hopefully yes because out of top 250 many are from the same colleges mostly IITs, NITs, and BIT so you should qualify

link

What is the number of slots for each site can anyone tell? For Amritapuri it's 250 but for rest no idea.

Auto comment: topic has been updated by Gwynbleidd_ (previous revision, new revision, compare).

Us bhai us.. literally us momint hogya.. conragts

pretty cool ain't it?

conragts to Gwynbleidd_ for finally reaching CM ( ME )

What i did was just printed the g(x) value for start and end point for each f(x), i.e. 2^i, 2^(i+1)-1 and it turned out the difference between them is atmax 1. and since it is monotonic u can find the point where it changes using binary search.

f(x) ranges from 2 to 60 and for each f(x), g(x) is monotonic. Also for each f(x) if you check g(x) can have atmax 2 values. Precompute for all such ranges and answer it. tc: q*70 ig

For easy version I checked for every pair of segments that occur together so when I saw m=10 I thought maybe we could use bitmask dp and it would pass but didn't had time to try it out. Thanks!

If 2 index are same then doing operation between them does nothing and doing an operation that don't cancel either one of them affects the rest elements outside them also. Rest was proofbyAC.

Always use 1 and try greedy

can E2 be done with bitmask dp?

mine just printed around 41 of them idk if my code crashed or the test cases had issue with the test case so can't say for sure. Also didn't get any error, the code compiled perfectly fine for me just didn't get all the outputs.

They haven't released it yet for this year, although you can lookup the last years announcements. About 130-140 seats were there for Amritapuri last year ig.

The point is that the solution considers 0 as a perfect square

I don't know why would someone think of putting 0 in the test case

hopefully atleast +6 this time

No need to do it for each bit. If you want to make a whole subtree equal then you need to make all children of the root equal to root otherwise its not possible. There is no way we can change the root value to be equal to the value of the child without changing the child.

If you have the formulae to calculate dp for any parent from it's children then you can also use the same formulae to reroot the tree to the child from it's parent. Keep doing it recursively in dfs and calculate answer for every node

tree dp / rerooting

Why the skill difference between D and E so high everytime. btw how to approach E anyone?

just search sum of xor of all subarrays and you'll find it on gfg. Link

C seemed pretty easy at first but after getting 3 WA and getting AC finally I realized that I was right

D was just a modified version of an existing problem with just a few changes needed while implementing it.

Updated with links

Auto comment: topic has been updated by Gwynbleidd_ (previous revision, new revision, compare).

Can't you just sort them or use a priority queue?

Yup understood the same and thought wouldn't it make this a trivial solution for each k it would be square of length 1 if it exists in array but then figured out later that it meant that the smallest rectangle that would cover all the points with same value

Can we solve E with tries or is it some dp or something else that my small brain couldn't think of?

me spending 10 minutes trying to understand what problem C was trying to say

Anyone having any idea about 2023-24 prelims for amritapuri? The official site shows the registration has started and it would be held on 26ht november but apart from that i can't find any other discussion or announcement blogs.

Maybe that's why people don't like codechef anymore

As CodeChef_admin said in the comment below debug wa feature doesn't work for that problem so your code could be failing in some other test cases. Link

Then this AC solution is wrong and the test cases are poorly written. Also your code might be failing on some other test case then.

My solution outputs the same and got accepted maybe there is a bug in your implementation submission

No rank and score updates, long queues, constructive problems in div2 and also didn't understood why my code works fine for Ant and passes all test cases but it just does.

Firstly you are doing one operation outside the loop and then for each iteration in loop you are doing 2 operations and the loop runs for 2n+1 times resulting in 1+2*(2n+1) operations that is more than the required 2n+2 I/O operations needed

Whenever i encounter an interactive problem in the future this contest would remind me to read the I/O format completely before attempting it. Thnx

The game ends when Bob cannot make a move or after 2⋅n+1 moves so why did i need to take another input after completing the 2*n+1 moves which resulted in me getting 4 runtime errors

This ruined my contest. Literally i got 4 runtime errors on pretest 2 for this reason. In the question it was mentioned if 2*n+1 moves are done then the game finishes. Also there were no pretests that had 2*n+1 moves to make it more clearer.

Hopefully I reach closer to cm

idk bro. i didn't do it by manipulating the bits directly but by trying 2 options for each element. Either it gives first some power of 2 and then takes some power of 2 or the other way around and whichever worked without violating the conditions stored it in the map and then checked whether the counts are equal or not

222801225

ok mb i didn;t see your rating

deserve the downvotes ngl

This was my first approach which gave WA. So you are good

Idk but i also got WA on pretest 6 due to silly mistake(Writing — instead of +). I also ignored all elements equal to the target final value because we can always use them as the middle man for some operation.

For each element you need to give some power of 2 to someone and also take some power of 2 from someone and for each element not equal to the average of the whole array this give take pair is unique. Also if the sum of all elements of the array is not divisible by it's size then answer doesn't exist.

Thought i had D1 in 5 min but after getting 2WA realized i was wrong. Really nice contest!

ya insted of storing xor of all zeros i used xor of all values since you can get xor of zeros just by doing xor1 ^ xorall

If you swap the values for a node it's children's values also have to be swapped

222304569

I stored the xor of 0's in the range and xor of all 1's in the range and for lazy updates whenever i find a range that is inside the needed range just swap the values and set its children to do lazy updates whenever they are visited. And before accessing any range check if it has to be updated or not, if yes then update its value and set its children to do lazy update whenever they are visited.

For range updates you need to use lazy propagation, otherwise if you try to update all values in the range then cost for each update is O(n). If you are given q queries each of size n leading to O(n.q) so the TLE

Ntg's wrong with it except the fact that my brain decided to stop working for few minutes

Got it thnx. I first thought about 2 separate prefix xor array's one for ones and other for zeros complicating it that's why i aborted the idea and went with segment trees.

I thought about using prefix sums but it would have taken some time to figure out the correct way for it so instead I used segment trees with lazy propagation which was pretty obvious. Still messed up the code and got 2 WA's

Was it just me who wasted 5 min on problem A because of this:

Segment Tree

Kind of but the constraints are also important. 1<=n<=1e4 and 1<=w<=26 where n is number of nodes and w is weight of edges, which allows for simpler approaches to work also and doesn't require ds like segment tree or such. Also the answer would be different if the operation is increase or decrease by 1 rather than change it to any value.

you can select an edge and increase or decrease its weight by 1. If you are talking about today's leetcode contest question 4 then you read the question wrong. You can change the weight of edge to any value rather than increasing or decreasing it by 1.

Now my username make sense. Thanks

I also thought the same but couldn't figure it out.

    int n, ai;
    cin >> n;
    map<int, vi> p;
    rep(i, 1, n)
    {
        cin >> ai;
        p[ai].push_back(i);
    }
    ll ans = 0, x;
    for (auto &itr : p)
    {
        vi t = itr.second;
        x = 0;
        rep(i, 1, t.size() - 1)
        {
            x += t[i] - t[i - 1] - 1;
            ans += x;
        }
    }

I think my E should have worked but it gave WA. Can anyone tell me where I got it wrong.

List of numbers inserted in order: 1,2,4,3,5,6.

The first 4 elements are not sorted so the 0 and after inserting remaining 2 elements you remove the last 3 elements which leaves us with1,2,4 which is sorted so the 1.

If you only multiply by positive number then the answer would be number of elementsi such that a[i]>=a[i+1]. Instead what we can do is for some i turn the prefix before it to a negative increasing array. If the prefix contains k strictly decreasing segments then the number of operations needed to convert the whole prefix to an strictly increasing prefix such that all it's elements are negative is k. So we can just check it for each index i and calculate the minimum

I went about it like this:

If n = 2^k then we can at every step subtract it by n/2 to finally reach 1 using every number exactly once. Eg: 8->4->2->1

Now suppose the highest set bit in the binary representation of n is k. Then we know that we can reach 1 from 2^k. Now how to reach 2^k from n? At each step we turn off the LSB of n from it till it reaches 2^k since the number formed by the LSB always divides the number and using this operation we use each number only once.

Ya ig i did oversimplify it. Thanks tho.

Yes my approach was also similar. For every a[i] I found the ranges it covers consisting of elements greater than or equal it then used a prefix sum array to calculate the total cost. Could you tell what was wrong in my approach?

In the constraints it is given k<n every time all odds and even wont get swapped

Suppose if you sort the whole string you know which characters are at odd and even indices in the final sorted string. Then you can use the second operation to change the parity of any character that is not in it's correct parity list and finally sort it using first operation.

What is the intended solution for F? My approach was for a query [L,R] first check if L==R if yes then only one operation is needed otherwise we need to bring all element in range [L+1,R] to L and then use one operation to reduce all to 0 but it gave WA on pretest 5. Submission: 220592550

Because of the first kind of operation you can sort all the odd indices and even indices separately. Now if the other kind of operation allows to swap characters at the end of an even window then you can use it to send any odd index element to even index. This allows us to sort the whole array.

Lol i thought it was question F nvm mb

First we could break it down to 2 different cases. Since the relative position of Bob and Alice doesn't matter then for query i let u=min(U[i], V[i]) and u=max(U[i],V[i]):

Case 1: if a[u] < a[v], then whoever was at position u can go to position v since both condition are satisfied(we initially set u to the min and v the max) and it would be the answer.

Case 2: if a[u] >= a[v], then we need to find the first index j > v such that a[j] > a[u]. For this we could use a Segment Tree. We build a range max query segment tree where each node stores the max for the range. Then we binary search on the segment tree to find the range. Suppose the max of the range [v+1, n] is <= a[u] then the answer is -1, otherwise we check the left subsegment and the right subsegment. If the max of left subsegment > a[u] then we move to the left subsegment(since we want the first index in the range) otherwise we move to the right subsegment. Tc: O(logn)

Not a very efficient approach but i think it should work: Think of all groups to be max heaps containing the elements. Also remember each elements index in its respective heap or group after each operation. Inserting element in group would simply be heap push operation O(logn), Changing score of element would be using the elements index in its heap and doing decreaseKey() operation in the respective heap 0(logn), changing all elements in a group would be changing each value in heap to O(group size) and printing max score of a group would be heap.top() O(1).

Deleted