MridulAhi orz tester

Video Solutions for problems A-D!

F can be also done in O(Nlog(max(A[i]))logQ):

We can notice that from each starting point, only at max 30 positions are important ie. Whenever a new bit is added in the range bitwise OR.

So we only need to look at these ~30N potential answers instead of the n^2 potential answers.

Now for each potential answer, we get a prefix of queries that can be satisfied, so we can use a difference array type technique, for minimums instead of for sums.

submission: 212515812

Video Solutions for A-E

I made Video Solutions for A-E.

You can find some filters here: Link

Binary search, use digit DP for the checker.

Use simple polynomial multiplication and binary exponentiation.

I had the same doubt (indeed Matrix exponentiation TLE's). If you look closely, we don't really need a k*k matrix, all we need is a k*1 vector. Notice the nature of the transitions:

dp[i+1][j+k]+= dp[i][j]*g[k].

Where g[k] = 1 if the digit k is allowed for the value of S that we fixed.

So, all we need is g^n.

How to solve SUMPROD? I know some n*k solutions passed; how to do it faster, though?

Thanks a lot for wasting everyone's 2 hours. spent the whole contest trying to debug A :)

Will you guys be sponsoring the travel/accommodation for the onsite participants?

I made video Solutions for A-E.

Screencast with solutions for all problems in case someone is interested.

This is because y would be the smallest number whose square is a multiple of x. any other such number would end up being a multiple of y. and we know that for 2 numbers n1 and n2 such that n1 is a multiple of n2, dp[n2] <= dp[n1]

The solution Idea was good, but it could have been framed in a much better way

There are a lot of comparisons to be done, so the probability of 1-dimensional hashes colliding is not that small. Hence you should use 2-d hashes.

here is my submission: https://atcoder.jp/contests/abc284/submissions/37840173

Video Solutions for A-E

Try to fix the number of indices i such that b[i] is the prefix maximum, then, since we know that maximums will occur in increasing order and minimums in decreasing order, we only need to choose the indices where we will keep the maximums.

there is a caveat, though, you need to make sure that all places other than the maximums will surely be minimums to avoid overcounting; try to figure that out, it isn't very hard.

Precisely, what he means to say is that what you've written should have been there in the editorial.

I made video Solutions for A-E.

Congratulations! :)

Here are video Solutions for A-D, in case someone is interested.

The pain of missing out on a problem by 2 mins in 2 consecutive rounds

When will the editorial of the finals be released?

Would be nice to become Master by the end of the year

Will the editorial be released on codedrills? Also, can anyone share their approach for problem D, sequences?

I think sending a mail to everyone who registered might be a good idea to avoid that.

Team: "Fast_input_slow_output"

Members: Ramanauj Goel taitaisama, Aryaman Das WAtoAC2001 and me (sharmaharisam)

Qualified for Kanpur regionals and no hope for Amritapuri xD

Nope. If my solution is correct then he can never win since this observation is the sole basis for my solution lol

This is what we did(without any Complicated data structures):

Define dp[i][j] as the maximum score for the suffix [i..n] such that the first substring starts at index i and has a length j.

Now, step 1 is to precompute longest_common_prefix[i][j] as the length of the longest common prefix of substrings starting at i and j respectively for all i,j. This can be done naively in O(n^3) time.

Now, coming to the transitions, to calculate dp[i][j], we will iterate for k, that is, the starting point of the next substring. Now if lcp[i][k] is 'L' and s[k+L] > s[i] OR if L>=j, then we can say that dp[i][j] = max (dp[k][L+1] + a[j], dp[k][L+2] + a[j]....).

This can be done quickly by maintaining suffix maximums.

Am I the only one who did E using Binary lifting and tree dp? all submissions seem way less complicated.

Video Solutions for all problems.

for E2. "Turns out that for the current constraints, for every k, we can iterate over all pairs of 1≤i<j<k, where i and j are divisors of 2.k and check if the triplet is bad."

Why can we do this? I know that the sum of number of factors of all numbers from 1 to n is O(nlogn), but here we are iterating over each pair of factors for every number, what is the bound for that?

I made video Solutions to the first 4 problems in case people are interested.

here are the video Solutions for A-D.

I made a video Solutions for A-D in case people are interested.

This, This, and This

I made video Solutions for A-D in case someone is interested.

You don't really need binary lifting to figure out the starting point, there will be a few initial starting points, and after that, we will get a cycle so we can simply find out the starting point based on k%cycleSize.

Since there is no editorial yet, can you please share your approach?

Sure,

dp[i][0]->optimal score if we start from the i'th pile and it's Alice's turn

dp[i][1]->optimal score if we start from the i'th pile and it's Bob's turn

Now, transitions are kind of easy, we just have to make sure that alice tries to maximize the score and bob tries to minimize it.

You can view my Submission for details.

the smallest bit which is set > 1 times in the elements of the array(let's say m) can be set in all the subarrays in the following division of the array into subarrays: just take exactly 1 occurrence of an element with that the m'th bit set in each subarray. this ensures that the sum of each subarray has the m'th bit set. reason: since for all bits j <= m, we have at most 1 occurrence of j in the subarray, there will be no "carry over" when we do the addition.

also, if there is no such bit, then obviously the answer will not exist since we can't get >=2 subarrays that have the same bit set.

For E: "and we do not care about any element >= m." Don't we also need to make sure that m should not be present for mex to be m? edit: is the reason that we can ignore this, the fact that, let's say when we fix mex = m, the actual mex was m+5, then we will get a strictly better answer when we fix the actual mex to be m+5?

I made Video Solutions for all problems in case someone is interested.

Here you go : Link

He has explained it in a really elegant manner:)

I made a Screencast + Solutions video in case someone is interested.

I'm a bit surprised since my n^2logn solution using only upper_bounds(which are probably faster than/ not much slower than BIT) got TLE.

In case someone is interested, I made video Solutions for D-F

Here are video solutions (for D-F)

Here are video Solutions to all problems in case people are interested.

for problem F, Test 32 had a situation where the entire grid was filled with '*' for sure.

Here are the video Solutions for A-D in case someone is interested.

I Made Video Solutions for div2 A-D in Case someone is Interested.

Sucks to solve more problems but still have a performance difference of +350 with someone solving less :/

I have a rather complicated idea:

1)compute 2 arrays, nsl[i] = closest position j to the left of i such that a[j]<=a[i] , and nsr[i] = closest position j to the right of i such that a[j] < a[i]. Both of them can be easily computed in o(n) using stack.

2)Now, if we consider a[i] is the minimum element, obviously, any subarray should be completely in the range [nsl[i] + 1, nsr[i]-1]. 3)find out the index, r of the leftmost element in the range [i+1,nsr[i]-1] such that a[r]<=a[i] + D, and the index l, of the rightmost element in the range [nsl[i]+1,i-1] such that a[l]<=a[i]+D. Both l,r can be found using binary search + sparse table.

4)Now, we can easily compute the number of good subarrays such that the minimum element is a[i]. if the subarray begins in the range [nsl[i]+1,l], then it can end anywhere in [i,nsr[i]-1]. Similarly, if it begins in the range [l+1,i], it can end anywhere in [r,nsr[i]-1].

I made video Solutions, for Div2 A-E

I made video Solutions for A-D in case someone is interested.

Not sure here, but according to me, these should be the conditions(assuming we have a 0 at x) : let's denote by i and j the leftmost and rightmost occurrences of 0

1)if L = x, and all elements in [L,R] are same

2)if i = x, then there should be at least one '1' in [L,j], otherwise there should be at least one '1' in [i,j]

I made video Solutions (for A-E) in case someone is interested.

I made video Solutions for A-E in Case someone is interested.

Thanks. I missed the special case for |R| = n.

For count arrays, is it possible to find out the answer for the cycle using inclusion-exculsion? I tried but kept on getting WA.

In case someone is interested, Video Solutions for A-D

Us Moment

In case someone is interested, I made video Solutions for A-D(div-2)

Almost similar problem to E: https://mirror.codeforces.com/contest/1486/problem/D

If you were stuck at a problem <=C, Here are the video solutions,

If you are looking for video solutions, you can find them Here (All Problems)

You can just keep an assert statement which will give you a runtime error if you exceed the query limit.

If you are looking for video solutions, HERE they are(for A-D)

The simplest way to prove this is the fact that we will never swap 2 same characters, so, the relative order of all the same characters(all a's for example) remains the same.

Video Solutions for A,B,C in case you are interested.

If anyone is looking for video Solutions,Here they are(for A-D)

In case you are looking for Video solutions.(for A-E only)

My approach for E is different from the editorial, and I'm getting wrong answer on a few test cases. Any help would be much appreciated. Submission: Link

Approach: We are at (x1,y1) and want to reach (x2,y2) after exactly k operations. in one operation we can change either x or y. Let's say that we change x in p operations and y in k-p operations, and let dp1[p] be the number of ways to start from x1 and end at x2 after exactly p operations and dp2[k-p] be the number of ways to reach from y1 to y2 after exactly p-k operations, then I will add C(k,p)*dp1[p]*dp2[k-p] to my answer. (C(k,p) is the number of ways to select p operations that will change x out of the k operations)

Now as far as dp1 and dp2 are concerned. We can precalculate both of then as follows: dp1[i] = (w-1)^(i-1) — dp1[i-1]

dp1[0] is 1 if x1 = x2 and 0 otherwise

dp2[i] = (h-1)^(i-1) — dp2[i-1]

dp2[0] is 1 if y1 = y2 and 0 otherwise

Can anyone point out the flaw in this approach?

Update: nevermind I interchanged h and w.

In case you are interested in video solutions, Here they are(for A-E)

If you are interested in video solutions, here are the solutions for the first 4 problems.

Here are the video Solutions to the first 5 Problems in case you are interested.

Here are the video Solutions for problems A-D1 In case you are interested.

Here are the video Solutions to problem A-F in case you are interested.

Here are the video Solutions to the first 4 problems of the round in case you prefer that.

Here are the video Solutions to the first 5 Problems In case you are interested.

Here are the video Solutions to the first 5 problems in case you prefer that.

Here are the video Solutions to the first 4 problems of Div-2 in Case you are interested.

Thanks, missed that.

In D, I am getting WA by taking the right limit of binary search as 1e18, but AC if I take it as 1e18/k. Any ideas why? I can't see where it is overflowing. Here is my Submission for reference

In case you guys prefer video solutions, here are the solutions to the first 4 problems: Solutions

You can Have a look at my approach here :

Video Solutions to A,B,C and D (div 2)

As always, here are the video solutions for the first 6 problems(A to F1) :

solutions

This made my day :D

Thanks!

Here are the video solutions to the first 4 problems. solutions

Here are the video solutions to the first 6 problems(div-3) :

solutions

Video Solutions for all problems from A to E2 : solutions

As always, here are the video solutions to the first three problems : solutions

video solutions to A,B and C(div2) : solutions

Similar stuff in video format :

video solutions

It is actually possible to use unordered_map without worrying about collisions, here : how to avoid getting hacked using unordered_set

Solutions to all problems in video format :)
solutions

My approach (couldn't finish in time though) For each frequency, calculate the first and last discovery time of any node having that frequency and also the in_time and out_time for each node. Now for each node excluding the root, the condition for the edge between the node and it's parent to be removable is that there should be no frequency for which the interval [first_discovery,last_discovery] intersects with the interval [in_time,out_time]. This can be achieved using 2 segment trees and binary search.