I was trying Binary Search but it was very difficult to implement.

Oh damn I missed this detail. Thanks for pointing it out.

If we are iteratively decreasing k, then won't the time complexity be O(T * K) where T is the number of test cases.

Let's take this test case:

200000
1 100000
1000000000
1
The above test case repeated a lot of times

Won't this give a TLE?

You wanted an explanation of the case when frequency of values equal to $$$\lceil\frac{n}{k}\rceil$$$ exceeds the remainder. I gave an explanation for that.

Why are you giving a rebuttal with an invalid test case?

Actually placing the first $$$K'$$$ elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$ in the $$$last$$$ segment and then cyclically placing them in the next segments is the only way.

Proof: Note that right now we are only dealing with those elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$.

Let's increase the distance between any two same elements (Let's call them $$$A$$$) in any consecutive segment by $$$x$$$. The new distance is $$$k+x$$$. Then the distance between the element $$$A$$$ in the next segment and the current segment decreases by $$$x$$$ making it $$$k-x$$$. To accommodate this change, the $$$A$$$ in the next segment will have to be moved by at least $$$x$$$. This creates a chain reaction that will reach the last segment. Since the size of the last segment is less than or equal to $$$k$$$, then $$$A$$$ in the last segment will have nowhere to move. So we can say that placing the element in the last segment decides the order in the next subsequent segments.

First of all, notice that your second arrangement is wrong since you won't be able to place $$$a_2$$$.

Hmmm, okay let me phrase it like this:

Let $$$K'$$$ $$$=$$$ $$$(n \% k \equiv 0$$$ $$$?$$$ $$$k : n \% k)$$$ --> The size of the last segment.

Let the suitable indexes in the $$$last$$$ segment be $$$[1, K']$$$

The only way to place first $$$K'$$$ elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$ in the $$$last$$$ segment is to place them in the suitable indexe of the $$$last$$$ segment. After you have placed them in the $$$last$$$ segment, one sure way to place them in the remaining segments without violating any condition is to place them cyclically at distance $$$k$$$. Now we have $$$\lceil\frac{n}{k}\rceil - 1$$$ segments remaining. If there is one more element having value equal to $$$\lceil\frac{n}{k}\rceil$$$, we won't be able to place that element without violating the condition. There are less segments and more values, then by the Pigeon-Hole principle, there will be two values in the same segment(box). The distance between these two same values will be less than $$$k$$$.

How is the first arrangement of $$$a_1$$$ wrong? Since $$$a_1$$$ has the maximum frequency, it makes sense to handle it first and place it at the first position of the first segment since this position will definitely provide the distance of $$$k$$$ in the next subsequent segments.

For a particular value of $$$k$$$, the number of segments $$$=$$$ $$$\lceil{\frac{n}{k}}\rceil$$$. Let's take $$$n = 12,$$$ $$$k=5$$$, then our segments will look like $$$[ __, __, __, __, __ ]$$$ $$$[ __, __, __, __, __ ]$$$ $$$[ __, __ ]$$$.

Here $$$\lceil{\frac{n}{k}}\rceil = \lceil{\frac{12}{5}}\rceil = 3$$$

Let $$$M[4] = [3, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$. Let's start filling the segment:

After filling $$$a_1$$$:

Segment $$$=$$$ $$$[ a_1, __, __, __, __ ]$$$ $$$[ a_1, __, __, __, __ ]$$$ $$$[ a_1, __ ]$$$

$$$M[4] = [0, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$.

After filling $$$a_2:$$$

Segment $$$=$$$ $$$[ a_1, a_2, __, __, __ ]$$$ $$$[ a_1, a_2, __, __, __ ]$$$ $$$[ a_1, a_2 ]$$$

$$$M[4] = [0, 0, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$.

Now you see that there is no way to fill $$$a_3$$$ such that the distance between any two $$$a_3$$$ is $$$k$$$.

Hope this answers your question

For problem D, how can we say for sure that $$$x$$$ will be of the form: $$$p11..11(30 - k \ times)00..00(k \ times)$$$

We want to find a multiple of d (lets call it k) where there is no bit i such that xi=1 and ki=0.

Why do we want to do this?

Thanks for the clarification.

For problem D, I am generating the prime factors of all the numbers but it is not giving me a TLE.

Example:

$$$n = 2$$$x$$$10^{5}$$$

$$$arr = [10^9, 1, 10^9, 1, 10^9,....]$$$

Then isn't the time complexity $$$O(10^5$$$ x $$$\sqrt{10^9})$$$ and won't this give TLE?

179686581

How were you able to think of this construction?

Thanks understood.

Why increasing order of end point and not increasing order of starting point?

True, the code will become much simpler.

Given string $$$S$$$ of length $$$n$$$. First trim all the left zeros from $$$S$$$ and call this $$$S1$$$. We are trimming the left zeros because they can never be flipped to 1.

Example: $$$S = 00110010110$$$
Then $$$\hspace{0.5cm} S1 = 110010110$$$

Next we will try to flip the remaining 0s in $$$S1$$$ from left most zero to right most zero and we will do this greedily since we need to maximize the binary value of $$$S1$$$.

Let $$$S2 = 0010110$$$, that is we trim all the $$$1's$$$ before the first $$$0$$$ in $$$S1$$$. If we maximize $$$S2$$$, it would the same as maximizing $$$S1$$$.

We use 2 pointer approach. Let $$$itr1$$$ be the iterator for $$$S1$$$ and $$$itr2$$$ be the iterator for $$$S2$$$.

$$$if(S2[itr2] == 1)$$$ then we can't make it $$$0$$$ as we are performing BITWISE OR operator. And this works to our advantage as we want to maximize $$$S2$$$.

$$$if(S2[itr2] == 0)$$$, then $$$S2[itr2] \hspace{1mm} | \hspace{1mm} (Bitwise OR) \hspace{1mm} S1[itr1] = 0 \hspace{1mm} | \hspace{1mm} S1[itr1] = S1[itr1]$$$. So we set $$$S2[itr2] = S1[itr1]$$$.

Question: What will be the starting index of $$$itr1?$$$

Answer: Let $$$idx_0$$$ be the first occurrence of $$$0$$$ in S1. If we take $$$itr1 \gt = idx_0$$$, then $$$S1[idx_0]$$$ will never become $$$1$$$. So $$$itr1 \hspace{1mm} \epsilon \hspace{1mm} [0, idx_0 - 1]$$$.

vector<string> ans; // To store the lexicographically largest S2
    string S2 = "";
    for(int i = idx_0; i < n; i++)
        S2.push_back(S1[i]);
    int m = S2.size();

    for(int i = 0; i < idx_0; i++){
        int itr1 = i, itr2 = 0;
        string temp = S2;   // We will make temp lexicographically largest
        while(itr2 < m){
            if(S2[itr2] == '1'){
                temp[itr2] = '1';
            }
            else{
                temp[itr2] = S1[itr1];
            }
            itr2++;
            itr1++;
        }
        ans.push_back(temp);
    }

    sort(ans.begin(), ans.end());

Code: 176851036

Educational rounds follow extended ICPC rules. Here you won't get a penalty for WA on test 1. You can read about it here: https://codeforces.me/blog/entry/105575?#comment-939387

What is your approach for problem F?

Understood

Oh I understand my mistake. Can you please explain why going from the deepest node towards the root node will always give the optimal answer?

Why can't we use a greedy approach from the root node? Let x be the current node. If $$$depth[x] \gt mid$$$, then we have to make a cut. By doing so, the height of x becomes 1 and the heights of the child nodes are then adjusted accordingly.

174079619

Writing eloquently is an art and you sir are very good at it. I was thinking the same during contest but was not properly able to separate the cases.

Thanks for explaining.

What is your logic?

Thanks for the visualization. I understood it now.

Shouldn't it be $$$a[i_1] == b[i_1], a[i_2] == b[i_2]$$$ or $$$a[i_1] == a[i_2], b[i_1] == b[i_2]$$$?

Understood. I was not updating the set.

Can anyone please tell me why my solution for B is failing? I am using the same logic as the editorial but the implementation is different. For each parity, I am checking if the current element is the greatest element of the current parity or not. If it is not, then the answer is NO, else the answer is YES. 172802388

For Problem A, if I try using long double, I get a wrong answer, but if I use long long, then I get correct answer. Why does this happen? My logic is the same as the editorial.

Using long long.

Using long double.

Will the AI spam wrong solutions until it gets a correct solution? lol it will be fun to see.

Thanks!

For Problem D, I referred this link.

So, the equation changed to $$$s - 2 * a = x \oplus y$$$. Then we can find non-negative integers $$$x, y$$$ as long as $$$s - 2 * a \gt = 0$$$.
(We can say $$$x = s - 2 * a,$$$ $$$y = 0$$$)

But this is giving me a wrong answer. Why is this condition not enough to find $$$x$$$ and $$$y$$$?

Got it, thank you so much!

Why are we able to add a direct edge between nodes $$$a$$$ and $$$b$$$? Or more precisely, how is a path relationship converted into a parent-child relationship?

Also if we add direct edges, won't we be creating a graph rather than a tree? PurpleCrayon

Please upload the codes also.

Right the logic is somewhat similar.

Was problem G taken from somehwere? It has way too many submissions.

Is the dynamic programming approach used in D1 a known concept?

Can you please explain your logic?

When will the editorial be released?

$$$0$$$ $$$ \lt =$$$ $$$k$$$ $$$ \lt $$$ $$$b$$$ (By Euclid's Division Lemma)

Multiply both sides by $$$k$$$.

$$$k*k$$$ $$$ \lt $$$ $$$k*b$$$

$$$= \gt $$$ $$$k^2$$$ $$$ \lt $$$ $$$k*b + k$$$ (Since $$$k$$$ is non — negative, the RHS sum can remain same or increase but never decrease)

But $$$k*b + k$$$ $$$=$$$ $$$a$$$ $$$ \lt =$$$ $$$x$$$ (Given in the question).

Hence $$$k^2$$$ $$$ \lt $$$ $$$x$$$ or $$$k$$$ $$$ \lt $$$ $$$\sqrt{x}$$$.

Now here we need to take equality in case $$$x$$$ is not a perfect square else you can drop the equality. This is because in case of non square number, we will be missing 1 number.

Thanks, I will try to implement it with this thing in mind.

No, I meant what happens if the current node (v) is an ancestor of some node in the data structure according to Keshi's tree?

Wait, so if the current node is itself an ancestor of some of the previous nodes in the path, then does that mean it is the current node that will be removed?

Won't there be a situation when it is better to remove the current node instead of the ancestor?

fore (j, 0, m) {    // We are looking at all the "points" one by one.
		vector<int> cnt(n + 1, 0);    // Notice here that cnt vector is intialized to 0
                                              // every time for all 0 <= j < m (0 based indexing)

                // For the point j to NOT be captured by city i, the monument should be built on 
                // step >= n + 1 - x (These variables are introduced in the editorial.)
                // Here x = d[i][j]
		fore (i, 0, n)
			cnt[n + 1 - d[i][j]]++;
		
		vector<int> d(n + 1, 0);
		d[0] = 1;
		int rem = 0;
		fore (i, 0, n) {
			rem += cnt[i];
			d[i + 1] = norm(d[i + 1] + mul(d[i], rem));
			rem = max(0, rem - 1);
		}
//		cerr << d[n] << " - " << norm(1 - mul(d[n], invFact)) << endl;
		E = norm(E + 1 - mul(d[n], invFact));
	}

I have added few comments in the code snippet which is necessary to understand the explanation further.

For each point $$$j, 0 \lt = j \lt m$$$ (0 based indexing), $$$cnt[i]=$$$ number of cities in which we can build a monument on the $$$i^{th}$$$ day, such that the $$$j^{th}$$$ point won't be captured by any of the cities $$$\epsilon$$$ $$$cnt[i]$$$.

Thanks, I was writing $$$a_i = k*m + a_{i-1} + c$$$.

Takeaway: $$$ a_i = (a_{i-1} + c)$$$ $$$mod$$$ $$$m$$$ is not the same as $$$a_i \equiv (a_{i-1} + c)$$$ $$$mod$$$ $$$m$$$

How did you arrive at : If $$$a_{i-1}$$$ $$$ \gt $$$ $$$a_i$$$ then $$$a_i - a_{i-1}$$$ = $$$c - m$$$ $$$?$$$

You have assumed that movements in the x and y-axis are independent but it is not true. Let's say that we have segments s1, s2, s3, s4, s5, s6, s7. What your code does is it solves independently for s1, s3, s5, s7, and s2, s4, s6 and gives the minimum for each axis (Here odd index segments refer to one axis and the even index segment axis refers to another axis). But what the question says is; say you are using segment s5, then it is necessary that you have used segment s1, and s3 as well as s2 and s4. But your code does not consider this.

Question requirement: For using Si, the coefficients of segments 1 <= j < i must be at least 1 and the sum of coefficients at odd index must be N and at even indices must also be N.

Your code: For using Si, the coefficients of segments 1 <= j < i must be at least 0.

Sample Test Case:

1

6

100 1 100 100 1 100

Expected Output: 309

Your Output: 210

For 1478D - Nezzar and Board, suppose we have the numbers 0, a, b, c. Then how can we generate 3a — b + 5c? Since we are using Bezout's Identity, then ax + by + cz = d must exist $$${\forall}$$$ x,y,z $$${\epsilon}$$$ $$$\mathbb{Z}$$$

a mod b = k, that is, k is the remainder when we divide a by b.

Now applying Euclid's Division Lemma we can write

a = bq + k, where q = $$$\lfloor{\frac{a}{b}} \rfloor$$$ = a mod b = k (Given in question)

Since k is the remainder, we 0 <= k < b by Euclid's Division Lemma or b > k.

Let's look at the four inequalities required for solving this question:

1. b > k (derived in the editorial)

2. 1 <= b <= y (given in the question)

3. 1 <= k(b + 1) <= x (derived in the editorial)
   Modifying equation 3, we get

4. 1/k — 1 <= b <= x/k — 1

5. 1 <= k < b (derived in the editorial)

(Why k != 0? If k = 0, then a = k*(b + 1) = 0 but a >= 1, so the minimum value of k is 1)

Now from equation 1, we know that the minimum value of b is greater than k and from equation 2 we know that the upper limit of b is y.

So we get the following inequality if we merge equation 1, 2 and 4

k < b <= min(y, x/k — 1)

Now we got an open interval at the lower limit and closed interval at the upper limit, so the number of elements in the interval is Upper Limit — Lower Limt = min(y, x/k — 1) — k.

Now the value of k can exceed the value of min(y, x/k — 1) since 1 <= k <= sqrt(x) and in this case, we will get negative number of elements in our interval which is not possible. So if we get negative number of elements, in such cases it means we have 0 elements. That is why we must take max(0, upper limit — lower limit).

Example: If y = 2, x = 36, k = 6

min(2, 36/6 — 1) — 6 = min(2, 5) — 6 = 2 — 6 = —4.

Why does greedy work?

You are using a Greedy Approach for this problem which is wrong.

Try this test case:

4 4

1 5 6 9

Rate of change in g′(x) is greater than rate of change of h′(x)

How can we say this?

You can use 'Graph Editor' by csacademy: https://csacademy.com/app/graph_editor/. It is similar to the one above.

See Mashup F: https://www.youtube.com/watch?v=mw2J6lvZZJ4&t=9712s. The explanations are really nice.

Why does this work?

If we are (i,j) then why are we taking the state dp[i][j+1]? Shouldn't we take dp[i][j]?

dp[x][y+1][cnt+1][(rem+ax,y)%k]=max(dp[x][y+1][cnt+1][(rem+ax,y)%k],dp[x][y][cnt][rem]+axy)

I am not able to understand this transition. What does dp[x][y][cnt][rem]+axy exactly mean?

UPD : Understood. We are looking whether or not it is beneficial to take the current element or not.

while(a*x <= x+b && a*x < y)

This condition was giving me TLE in one case but when I did this

while(a*x <= x+b && a*x < y && a <y/x)

This small change gave me AC Why?

For problem C This is a classical dynamic-programming task with a twist. Which task does this refer to?

https://codeforces.me/contest/1371/submission/85805079

https://codeforces.me/contest/1371/submission/85805620

The test case 2 is failing in both the solutions because the "jury" is changing it's answer in the second answer. In the first approach, it says that the answer for testcase 14 is 4 but in the second solution, it says that the answer is 0.

Why is this happening?

Basically 'k' is a restriction on the current digit right? if k = 0, then we can fill the current digit from 0 to 9 if k = 1, then we can fill the current digit from 0 to digit[digit.length() — j] where digit is an array containing the individual digits of "R"

It's a very good solution, a lot better than the editorial!