arvindf232's blog

By arvindf232, 2 months ago, In English

Thank you for your participation!

1734A — Select Three Sticks

We first sort the array $$$a$$$ in non-decreasing order.

Denote the indices of the elements that we choose from $$$a$$$ to be $$$x$$$, $$$y$$$, and $$$z$$$, where $$$1 \le x < y < z \le n$$$, and the final value (after performing the operations) of the concerned elements to be $$$v$$$.

The minimum required number of operations is then $$$|a_x-v|+|a_y-v|+|a_z-v|$$$. It is well-known that such expression attains its minimum value when $$$v$$$ is the median of $$$a_x$$$, $$$a_y$$$, and $$$a_z$$$. Since the array $$$a$$$ has already been sorted, it is best to assign $$$v$$$ to be $$$a_y$$$.

Our expression then becomes $$$|a_x-a_y|+|a_y-a_y|+|a_z-a_y|=(a_y-a_x)+0+(a_z-a_y)=a_z-a_x$$$. We would like to minimize the value of $$$a_z$$$, which implies $$$z$$$ should be as small as possible since $$$a$$$ is sorted. It is clear that taking $$$z=y+1$$$ would minimize the value of the expression. Similarly, we can show that we can take $$$x=y-1$$$ to minimize the value of the expression.

Therefore, the only possible values of the triplets $$$(x,y,z)$$$ are of the form $$$(t,t+1,t+2)$$$ for positive integers $$$1 \le t \le n-2$$$, and we can iterate through all such triplets and find the best one.

The time complexity is $$$\Theta(n \log n)$$$ per case due to sorting.

Code in C++

1734B — Bright, Nice, Brilliant

Note that the brightnesses of the rooms on the $$$i$$$-th floor is at most $$$i$$$. This is because in room $$$(i,1)$$$, only $$$i$$$ rooms, namely, $$$(1,1)$$$, $$$(2,1)$$$, $$$\ldots$$$, $$$(i,1)$$$ can reach to $$$(i,1)$$$ through some number of staircases.

It is also possible to find a configuration of torches in the pyramid such that the brightnesses of the rooms on the $$$i$$$-th floor is exactly $$$i$$$, i.e. it attains the upper bound.

The configuration is as follows: Room $$$(i,j)$$$ contains a torch if and only if it is the leftmost room ($$$i=1$$$) or the rightmost room ($$$i=j$$$) on the $$$i$$$-th floor.

This is valid because for all rooms $$$(i,j)$$$, it can be reached from $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,1)$$$, $$$\ldots$$$, $$$(i-j+1,1)$$$ and $$$(2,2)$$$, $$$(3,3)$$$, $$$\ldots$$$, $$$(j,j)$$$. In other words, room $$$(i,j)$$$ has brightness $$$(i-j+1)+j-1=i$$$, so the pyramid is nice.

Code in C++

1734C — Removing Smallest Multiples

One operation should be used to remove every element not belonging to $$$T$$$.

Let $$$v$$$ be an element not belonging to $$$T$$$. Suppose a $$$x$$$-cost operation removes value $$$v$$$, then $$$v$$$ must be divisible by $$$x$$$. Furthermore, the multiples $$$x,2x,\cdots (k-1)x$$$ must have been already removed from $$$S$$$, where we write $$$v = kx$$$.

Since removed elements stay removed, the above is only possible if all of $$$x,2x,\cdots (k-1)x$$$ does not belong to $$$T$$$.

For each $$$v$$$, let $$$f(v)$$$ be the smallest integer $$$x$$$ satisfying the above condition. As we can always remove $$$v$$$ using a $$$v$$$-cost operation, $$$f(v) \leq v$$$ and in particular $$$f(v)$$$ exists.

The total cost must be at least $$$\sum_{i \not \in T} f(i)$$$. We claim that this cost can be achieved.

To do so, we should remove the required elements in ascending order. When removing $$$v$$$, we assume all $$$w \not\in T$$$ with $$$w<v$$$ have already been removed. At this state, an $$$f(v)$$$-cost operation would be able to remove $$$v$$$.

It remains to find the values $$$f(v)$$$. To do so efficiently, we can perform the above process in a bottom-up manner similar to the Sieve of Eratosthenes. Please refer to the code below for implementation details. The overall complexity is $$$n (1 +\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}) = \Theta(n \log n)$$$.

Code in C++

1734D — Slime Escape

Let's call a group of slime good if their total health is at least $$$0$$$, or if defeating this group allows you to reach the exits.

We partition the slimes into good groups in a two-pointer like manner. To form the groups to the right, start from position $$$k$$$, then find the smallest position $$$r$$$ such that slimes from $$$k+1$$$ through $$$r$$$ form a good group. We do the same starting from $$$r+1$$$ again. Repeat this process until slimes to the right are partitioned into groups, which can be done by maintaining the sum of health. We partition the left slimes into groups in a similar way.

We can observe that in an optimal strategy, we may assume the player absorbs group-by-group.

Proof

For any good group, since the total health is positive, there is no drawback to absorbing a good group. In other words, whenever it is possible to absorb a good group, we will absorb it.

For each group $$$G$$$, we calculate the ``requirement'' of the group — the lowest health we can begin with, such that we can absorb the group while maintaining non-negative health at all times. The requirement of a group of slime with health $$$a_1,a_2 \cdots a_n$$$ can be expressed as

$$$ - \min_{k=0}^n (\sum_{i=1}^k a_i)$$$

Finally, we can simply simulate the process. We repeatedly attempt to absorb good groups to the left or to the right. We keep track of the current health, initially equal to $$$a_k$$$. Whenever we consider whether to absorb a group or not, we absorb it if and only if the current health is at least as high as its requirement. Otherwise, we ignore it for now and attempt to do so for the group on the other side. If it is possible to reach a state where either all left groups or all right groups are absorbed, then we can win the game. If at some point, it is not possible to absorb the left group nor the right group, then we lose.

The overall complexity is $$$\Theta(n)$$$.

It is also possible to use a range $$$\max$$$/$$$\min$$$ segment tree form the groups instead of using two-pointers, in which case its complexity would be $$$\Theta(n \log n)$$$.

Code in C++

1734E — Rectangular Congruences

We say a matrix to be good if it satisfies the congruence condition (the second condition).

When we have a good matrix, we can add any value $$$c$$$ to a whole row while maintaining the congruence relation. The same is true for adding the same value to a whole column.

Suppose we have any good matrix $$$A$$$, then by adding $$$b_i - a_{i,i}$$$ to the $$$i$$$-th row for each of $$$i=1,2,\cdots,n$$$, we obtain a good matrix that has the desired values on the diagonal.

In fact, there are a lot of possible constructions. We present a few of them here:

  • $$$a_{i,j} = i \times j \pmod n$$$

  • $$$a_{i,j} = (i + j)^2 \pmod n$$$. This needs special handling when $$$n=2$$$.

  • $$$a_{i,j} = \frac{(i+j)(i+j+1)}{2} \pmod n$$$.

  • The coolest part is that all quadratic polynomials in the form $$$ai^2 + bij + cj^2 + di + ej + f$$$ are valid for all integers $$$a,b,c,d,e,f$$$ and $$$b \not\equiv 0 \pmod n$$$

As a bonus, we prove that the general quadratic polynomial gives a good construction.

Proof

Here are some extra observations that may enable one to find a good matrix more quickly.

Some extra observations
Code in C++

1734F — Zeros and Ones

Observe that the $$$i$$$-th character is `1' if and only if $$$i$$$ has an odd number of set bits in its binary representation. Both solutions make use of this fact.

The constraints allows solutions of up to $$$\Theta(q \log^3 n)$$$. Yet, both of the model solution runs in $$$\Theta(\log n)$$$.

1. Digit DP solution

The question can be reformulated as follows: How many integers $$$x$$$ between $$$0$$$ and $$$m-1$$$ inclusive have the property that the total number of set bits of $$$x$$$ and $$$x+n$$$ is an odd number?

This can be solved with digit DP. We process the bit position from $$$\lceil \log(\max) \rceil$$$ down to $$$0$$$. We maintain three states:

  • $$$\text{ans}$$$, a boolean value;

  • $$$\text{trailzeros}$$$, an integer between $$$0$$$ and $$$\lceil \log(\max) \rceil$$$ inclusive; and

  • $$$\text{under}$$$, a boolean value.

We can thus conclude the following: the number of trailing zeros is all we need to decide the answer.

After processing each bit $$$k$$$, we should have the following: the number of integers $$$x$$$ between $$$0$$$ and $$$\lfloor \frac{m}{2^k} \rfloor$$$ inclusive which have the following property:

  • the total number of set bits of $$$x$$$ and $$$x + \lfloor \frac{n}{2^k} \rfloor$$$ is equal to $$$\text{ans} \mod 2$$$;

  • the number of trailing `1's of $$$x + \lfloor \frac{n}{2^k} \rfloor$$$ is equal to $$$\text{trailzeros}$$$;

  • the boolean value $$$[x < \lfloor \frac{m}{2^k} \rfloor]$$$ (where $$$[]$$$ is the Iverson bracket).

Now onto the transitions. Suppose we are adding the $$$(k-1)$$$-th digit, and let $$$d$$$ be the new digit of $$$x$$$, and $$$z$$$ be the $$$(k-1)$$$-th digit of $$$n$$$.

  • If $$$z+d = 0$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$(\text{ans},0)$$$ after digit $$$k-1$$$;

  • if $$$z+d = 1$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$((\text{ans} + z +d) \mod 2, \text{trailzeros}+1)$$$ after digit $$$k-1$$$;

  • if $$$z+d =2$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$((\text{ans} + z + \text{trail} + 1) \mod 2, 0)$$$ after digit $$$k-1$$$

The final answer is the total number of values for which $$$\text{ans} =1 $$$ and $$$\text{under} = 1$$$.

The above solution runs in $$$\Theta(\log^2 (\max))$$$ per query. There is a simple way to optimize this to $$$\Theta(\log(\max))$$$: note that we only need to keep parity of $$$\text{trailzero}$$$.

There are many other digit DP approaches that give similar time complexity. The constraints should allow most of them pass.

Code in Kotlin

2. Recursive Solution, by darkkcyan

Define the function $$$f(x) := $$$ the parity of bit one in the number $$$x$$$.

We have thus reworded the statement into evaluating the follow expression:

$$$ T = \sum_{i = 0}^{k - 1} \left[f(i) \ne f(i + n)\right] $$$

The formula can be further transformed as:

$$$ T = \sum_{i = 0}^{k - 1} f(i \oplus (i + n)) $$$

since $$$\left[ f(a) \ne f(b) \right] = f(a \oplus b)$$$ holds true for all non-negative integers $$$a$$$ and $$$b$$$.

Imagine we construct a grid and assign the value at row $$$r$$$ and column $$$c$$$ to be $$$f(r \oplus c)$$$. Then, $$$T$$$ is sum of a diagonal of length $$$k$$$ which starts at either $$$(0, n)$$$ or $$$(n, 0)$$$. Without loss of generality, we use $$$(0, n)$$$ in this editorial.

The grid can be constructed similarly to the way we construct the string $$$S$$$. We start with a $$$1$$$-by-$$$1$$$ matrix $$$M_0=\begin{bmatrix} 0 \end{bmatrix}$$$.

Then, the matrix $$$M_i$$$ of size $$$2^i \times 2^i$$$ can be constructed as follows:

$$$ M_i = \begin{bmatrix} M_{i - 1} & \overline {M_{i - 1}} \\ \overline{M_{i - 1}} & M_{i - 1} \end{bmatrix} $$$

where $$$\overline{M_{i - 1}}$$$ is the matrix $$$M_{i - 1}$$$ but with flipped bits.

Here is another way of constructing the grid: let $$$C_i$$$ be an infinite chess board with alternating colors, similar to a regular chess board, but with each of the cells being size $$$2^i \times 2^i$$$. For example, $$$C_0$$$, $$$C_1$$$ and $$$C_2$$$ in an $$$8$$$-by-$$$8$$$ grid is as follows:

Illustration

We claim that our grid is the $$$\text{xor}$$$ of all chess board $$$C_i$$$. The proof is easy: $$$C_i$$$ is constructed by $$$\text{xor}$$$-ing the $$$i$$$-th bit of the the row and column number.

We are therefore motivated to proceed in the following way: if we drop the least significant bit (by making it to be $$$0$$$), we are still solving a very similar problem to the original problem, because dropping the first bit is similar to removing $$$C_0$$$. And when we shift $$$C_i$$$ to $$$C_{i - 1}$$$, it is a recursion of the same problem!

Going back to the problem, where we are computing sum of a diagonal of length $$$k$$$. If $$$k$$$ is odd, we can make it odd by adding the last element to the result and decreasing $$$k$$$ by one. Now, $$$k$$$ is even, and we can utilize the recurrence as follows:

  • remove $$$C_0$$$.

  • scale the board down by 2 (including $$$n$$$ and $$$k$$$). By doing so, $$$C_i$$$ becomes $$$C_{i - 1}$$$.

  • solve the new problem.

  • scale the board up again and add $$$C_0$$$ back.

  • from the result of the scaled down problem, some how calculate the result of the original problem

The result of the scaled down problem is the number of $$$2$$$-by-$$$2$$$ cells with value $$$1$$$. From the number of $$$2$$$-by-$$$2$$$ cells with value $$$1$$$, we compute the number of cells with value $$$0$$$ as well. It is not hard to observe that it crosses the $$$2$$$-by-$$$2$$$ cells at all places. The only thing that matters is the parity of $$$n$$$.

  • If $$$n$$$ is even, then the diagonal crosses the diagonal of the $$$2$$$-by-$$$2$$$ cells. In the scaled-down version, the diagonal is still a single diagonal starting at $$$(0, \frac{n}{2})$$$; otherwise,

  • if $$$n$$$ is odd, it crosses the corner of the $$$2$$$-by-$$$2$$$ cells. In the scaled-down version, the diagonal is actually $$$2$$$ neighboring diagonals starting at $$$(0, \frac{n-1}{2})$$$ and $$$(0, \frac{n+1}{2})$$$.

Also, the $$$2$$$-by-$$$2$$$ cells with values $$$0$$$ and $$$1$$$ respectively will also have the form:

Illustration

From here we have everything we need to compute the result of the original problem.

Overall, the number of states we have to visit is $$$\Theta(\log k)$$$.

Code in Python
 
 
 
 
  • Vote: I like it
  • +169
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Quick editorial! Props to arvindf232 for the round now I am very close to orange!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

D is missing, any estimated time?

UPD: Added, ty

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can this submission for problem F be hacked?

»
2 months ago, # |
Rev. 3   Vote: I like it +165 Vote: I do not like it

Hello everyone in the CodeForces community,

We sincerely thank you all for your participation. We hope that you have enjoyed most of our problems.

There has been a bit more FSTs for problems A and C than anticipated. We have left out some of the out-of-bounds and TLE test cases in pretests. We will try to make stronger pretests in the future.

Some contestants also found problem E to be easier than usual, and demonstrated that this problem is unable to distinguish the abilities between higher-rated and lower-rated users well. We promise we will invite a more diverse variety of testers in the future, so as to ensure that our round will be more balanced, not only in terms of difficulty, but also the ranges of techniques that the whole problem set covers.

About 20 minutes into the contest, CodeForces has failed to load for the majority of users. Although it only lasted for about 3 minutes, it caused some users to have multiple repeated submissions, whose score has to be manually altered afterwards. Please allow us to sincerely apologize if this incident has negatively affected your contest experience.

Meanwhile, please enjoy the editorials to the problems. If you have any problems and opinions about the round, feel free to leave a comment below or directly message any one of arvindf232, happypotato1207, and myself.

Once again, thank you all very much for your time and effort and we look forward to seeing you next time!

»
2 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

quick and good editorial!!! As a tester, I think the problemset and solution are very very interesting

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Editorial came within 5 mins..... lightning fast editorial. Thanks a lot!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D video Editorial

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why is my submission getting WA on 3 (problem D)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Here's a nice video, by Errichto, that I find helpful in debugging. I take an AC code as a reference, generating small test cases and that does the magic. Hope it helps. :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Take a look at Ticket 16204 from CF Stress for a counter example.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why I get wrong answer in D 173227301

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

a[i] = (str[i — 1] == '1');

what does it mean? Can anyone tell me plz

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we are starting from i=1. So to match the chars inside the string str (including the very first character str[0]) we take str[i-1].

    If the character is equal to '1' then 1 (true) is stored inside a for the corresponding index.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C-solution a[i] = (str[i — 1] == '1'); what mdash means here?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for good contest and clear tutorial. I learn a lot in this contest especially problem E and F.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Has anyone tried to submit E using simulated annealing?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D suppose n <= 500 can it be solved using dp ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP(i,j,max) will represent the maximum value you can obtain at pos i, when the last move is j, and the bound of the other direction is max.

    I think you can do these states : (int current_Position,bool past_direction, max)

    • past direction will be your last move was left=0 or right=1.

    • max will be the opposite maximum element you reached( if you move to the left, it will be the rightmost not taken element).

    • max will be kept as it's if you didn't change the direction, as when you change the direction you will jump to it to skip the values that you've taken before.

    Transitions:

    • go left and your past_direction is left: dp(i,j,max) = max(dp(i,j,max), dp(i-1, 0, max) + ar[i-1].

    • go left and your past_direction is right: dp(i,j,max) = max(dp(i), dp(max, 0, i+1) + ar[max].

    • go right and your past_direction is right: dp(i,j,max) = max(dp(i,j,max), dp(i+1, 1, max) + ar[i+1].

    • go right and your past_direction is left: dp(i,j,max) = max(dp(i,j,max), dp(max, 1, i-1) + ar[max].

    O(2*N^2)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, can someone explain why the same solution got TLE at testcase 4 during contest, but wrong answer at testcase 5 after the contest. (side note: It was wrong because of overflow).

173206700: TLE at 4 during contest
173239308: Pass at 4, wrong at 5 after contest

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I liked your proof of the claim in D

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I feel like my solution for problem D can be hacked. https://codeforces.com/contest/1734/submission/173205140

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Its correct because when you are trying to go to right you will take the maximum change which you have got from left side. Similarly for left side.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone tried doing C using BFS? My submission fails 173243305, not able figure out why?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the following example

    1
    24
    111010101110111010111110
    

    Your code outputs 36 instead of 34 because in BFS 8 is inserted before 6 so cost of 24 is taken as 8 instead of 6.

    Also do look at editorial's solution. Your approach was very close to the correct apporach

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is my 173244335 getting WA on 2 (problem C)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not looked at your code, but you can do cout the input if test case number is 79 and find out the input and dry run it and find your mistake

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Take a look at Ticket 16206 from CF Stress for a counter example.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very high quality editorial. Well done.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of E, some extra observation part? How do we get the following conclusion:

Let b be the two dimensional difference array of a, that is, bi,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1. Then, the condition becomes sum of any rectangles of b must be nonzero (modn)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a much shorter and simpler solution for D. Suppose we can reach 0, then we would only go to the right if and only if there exists a position to the right such that it would increase the current health. Let i denote the current position, y denote the first position to the right such that it would increase the current health. It is easy to see that the sum of the interval [i+1,y] must be positive, and the current health plus the minimum sum of the interval starting from i+1 must be non-negative. Going to y always leads to a better result since it increases the chance of absorbing more negative slimes to the left of i. But to reach y, we must pass the requirement which is the sum must be non-negative, it is possible that the current health is not enough to absorb y. Therefore we should go to the left as far as possible to increase maximum health until no more moves can be made, then grab y if possible. This motives for a more general solution, let maintain x as the first position to the left which has the same role as y. If either position is reachable, go to any since it increases the current health and hence only leads to a better result. Code

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried that before every right step if we can go left and get some positive points for our health then we go and come back from the position of max points. Now we move one step right and again repeat the procedure but got TLE on TC8.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Why this solution does not work for problem C
  2. Anyone, please point out my mistake
  3. Thank You in Advance
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define nline "\n"

const int N = 1e6 + 69, M = 1e9 + 7;
char a[N + 1];
int l, r, mid, cand, p, u, v, wt;
int n, m, q, t, sm, x, y, k, res;
 
 
void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    bool erased_here[n + 69];
    memset(erased_here, 0, sizeof(erased_here));
    int res = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i] == '0'){
            for(int j = i; j <= n && a[j] == '0'; j += i){
                res += i;
                erased_here[j] = 1;
                a[j] = '1';
            }
        }
        else if(erased_here[i]){
            for(int j = i + i; j <= n && a[j] == '0'; j += i){
                res += i;
                erased_here[j] = 1;
                a[j] = '1';
            }
        }
    }
    cout << res << nline;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--) {
        solve();
    }
    return 0;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 9 000010110

    should be 9 but your code gives 10

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is wrong duh

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        greedy wont work with top-up approach try coming with counterexamples

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      in your first for loop, you need to include the case where erased_here[j] == 1, in the break condition of for loop( for(int j = i + i; j <= n && (a[j] == '0' || erased_here[j] == 1); j += i) ) this works, just think of it this way: you can't be blocked by something which wasn't there before you started coding (i.e. a[j] == 1 just because you have erased it, you can't end your loop here), and you can't delete something that has already been deleted, so skip all those for which you have added something in res(which again is identified by erased_here[i] == 1)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This works, just think of it this way: you can't be blocked by something which wasn't there before you started coding (i.e. a[j] == 1 just because you have erased it, you can't end your loop here), and you can't delete something that has already been deleted, so skip all those for which you have added something in res(which again is identified by erased_here[i] == 1)

        #include<bits/stdc++.h>
        using namespace std;
         
        #define int long long
        #define nline "\n"
        
        const int N = 1e6 + 69, M = 1e9 + 7;
        char a[N + 1];
        int l, r, mid, cand, p, u, v, wt;
        int n, m, q, t, sm, x, y, k, res;
         
         
        void solve(){
            cin >> n;
            for(int i = 1; i <= n; ++i)
                cin >> a[i];
            bool erased_here[n + 69];
            memset(erased_here, 0, sizeof(erased_here));
            int res = 0;
            for(int i = 1; i <= n; ++i){
                if(a[i] == '0' || erased_here[i] == 1){
                    for(int j = i; j <= n && (a[j] == '0'||erased_here[j] == 1); j += i){
                        if(erased_here[j] == 0)
                            res += i;
                        erased_here[j] = 1;
                        a[j] = '1';
                    }
                }
                else if(erased_here[i]){
                    for(int j = i + i; j <= n && a[j] == '0'; j += i){
                        res += i;
                        erased_here[j] = 1;
                        a[j] = '1';
                    }
                }
            }
            cout << res << nline;
        }
         
        signed main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            int tc = 1;
            cin>>tc;
            while(tc--) {
                solve();
            }
            return 0;
        }
        
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought D was nice, harder than it seems on the surface.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a simple solution for F by search with memorization, but I cannot tell if it's right. Can this submission 173252969 be hacked?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can this 173226289 for problem F be hacked?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please take a look at this D? I reviewed many times, pretty sure it’s O(n), but I get tle. Please tell me what I missed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh no, not again, can’t delete already. Ещё раз из-за глупости…

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A pretty optimized $$$O(N*\sqrt(N))$$$ solution will pass for problem C.

173266505

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why this solution 173214401 for problem C gives TLE. I make array of list which contain all possible k for that number initially contain one k which same as its number and i also make an min array which contain current minimum k for that number. so whenever i delete some number from the set i just add that number and its list numbers to the list of next multiple. According to me list contain factors of that number and the factors of 10^6 which is the highest number has 49 factors so acc. to me total no. of operations will be (10^6) * (49) * (10000) = 10^11 which can be done in 2 seconds. Thank you in advance.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A is so hard.

I couldn't solve it :(

I will do my best next time

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In E, why does it matter that n is prime? I don’t see the necessity.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The condition that "ab = 0 implies a = 0 or b = 0" is true only in prime rings. E.g. if $$$n=8, (r_1-r_2)(c_1-c_2)=(4)(2)=0$$$, and $$$(r_1-r_2) \neq 0, (c_1-c_2) \neq 0$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1734/submission/173218385 cannot find issue with my solution with problem D, can anyone help me out?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for F, "Observe that the i-th character is `1' if and only if i has an odd number of set bits in its binary representation"

How to prove this?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    For each bit with value 1, means the characheter has been flipped once. So if there are odd bits with value 1, the characheter has been flipped odd times, and the origin value is '0', then we can easily know the characheter is '1'.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Still a long way to go for me. :)

»
2 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Can anyone please help me with problem D.

7 4

-1 -2 -4 6 -2 -4 -1

I think answer should be YES, But it is given No(in sample test case)

my Explaination:

let say my currsum=6(as i am on 4th idx){considering 1-based indexing]

then i move right my currsum=4(my curr index=5)

then i move left my currsum=10(my curr index=4)

then i can keep moving right to index 5(currsum=8) then index 6(currsum=2) then index 7(currsum=1), hence i reached destination so answer should be yes?

correct me if i am going wrong somewhere.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please share their logic on how to use segment tree in D? I am just curious. Thank you

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    It is an alternative for the running min/max needed for this problem.

    Instead of grouping slimes with a total value 0 and above, we can pick the largest sum that we can reach with the slime's current health in each direction.

    Then, we will continually increase the slime's health, which gives us more "chances" of reaching further and further and eventually escaping (if possible).

    To do this, we build an array of cumulative sums in each direction (note that slimes to the left need to be accumulated from right to left) and construct a segment tree for Range MAX Queries on this array.

    Now, in each step we find the group with the maximum sum by querying the segment tree.

    The rest of the algorithm is pretty much the same.

    Edit: since querires are O(logn) and we may have up to n of those, the total complexity is O(nlogn).

    Hope this helps.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain to me why this submission fails the 512th test case of test 2? I can find an example where this greedy implementation of mine doesn't find the correct answer. https://codeforces.com/contest/1734/submission/173358903

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Here's my greedy solution for problem D, which is much simpler, but I can't figure out why it works..

Mark the area of slimes you have cleared out by keeping track of the left and right boundaries. You begin by expanding toward the left (you take care of expanding toward the right first separately). Either you can reach the end, or you can't. If you can, you win (and print "YES"). If you can't, you settle for going toward the left until you reach the maximum health possible, expanding your territory along the way and then try going toward the right. If you ever fail to expand your territory at all, you stop because it means you'll never reach the end.

Do this again for choosing to go right first.

Now, each step increases your existing territory. But actually, it may take $$$O(n)$$$ time to check whether you are able to reach the end or not since you keep going until you would have fallen to below zero health, which might involve experimentation significantly beyond the edges of the territory. If you only expand the territory by 1 each time but you would be able to reach almost the end if you decided to continue, it might take $$$O(n)$$$ for each expansion for an $$$O(n^2)$$$ algorithm overall. But either the test cases are too weak or there's something else limiting the time complexity I can't think of. I encourage someone to hack me or figure out why this technique works in subquadratic time.

173363257

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me on 173366132?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please provide a Python solution to Problem C

If possible, please help me with my code also. 173367115

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please tell me what's wrong with my solution to problem D? Thanks in advance. https://codeforces.com/contest/1734/submission/173373750

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am storing some set of elements in a set . i want to find the previous element of find . eg :- 2 3 4 6 are elements in set can i know the the value of 4 if i had 6 . we can find 6 using s.find() , but how to find previous element of the value we are finding . is it possible ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Find iterator (it) of the element you are searching for using find(). Do, it-- for the previous element. Handle the case separately, when the element you are seaching for is at the beginning of the set

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my answer of D is getting WA?? Link: https://codeforces.com/contest/1734/submission/173383119

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

arvindf232 In problem D, I did the same way as editorial, but mine got TLE on test 9. I have shortened my code as much as possible, kindly please look into that.

Code
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For question C, In the example n = 4 and T = 0010, why cant I use 1 to delete 1,2 and 4. Since all of them are multiples of 1. Hence, the answer could be 3.

Can someone please explain what part of question or solution I am missing?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem statement says,

    Choose a positive integer k where 1<=k<=n, such that there exists a multiple of k in S. Then, delete the smallest multiple of k from S.

    From the testcase, 
    S = {1, 2, 3, 4}, T = {3}
    // you pay cost 1 and delete 1's smallest available multiple on S (i.e. 1). 
    S = {2, 3, 4}, Total Cost = 1
    // you pay cost 1 and delete 1's smallest available multiple on S (i.e. 2).
    S = {3, 4}, Total Cost = 1 + 1 = 2
    // you try to pay cost 1 and delete 1's smallest available multiple on S (i.e. 3).
    // BUT YOU CAN NOT DELETE 3, because 3 is present in T.
    // so you pay cost 2 and delete 2's smallest available multiple on S (i.e. 4).
    S = {4}, Total Cost = 1 + 1 + 2 = 4
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C. Removing Smallest Multiples

If we consider the value of K = 1 then we can remove any number in the 1,2,3,....,n. Since every number is multiple of k and for each operation we can consider the cost remove any element as 1 Since every number is multiple of 1.

Let's consider below test case. 7 1101001 We need to consider {1,2,4,7}; Ans we need to remove {3,5,6}; So, Choose k=1, then delete 3 from S. (3 is multiple of 1) Choose k=1, then delete 6 from S. (6 is multiple of 1) Choose k=1, then delete 5 from S. (5 is multiple of 1)

The total cost is 1 + 1 + 1 = 3

But in sample test cases output is 11.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I hope you still remeber the problem.
    for test case 1101001.
    The index of 1 (in the set T) is equals to 1, that means The set T contains the number 1, so if you choose k = 1, the number 1 will be removed from set S , so The set S can never be the same as set T(which is exactly the opposite of what we want to do).
    Your only option is to choose K = "a number that is not in the set T which means that it's value (in set T) corresponds to 0 ".

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What a shitty and confusing explanation of problem D solution! Can't you explain it in simple words?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The python implementation of the solution provided here for question C is giving TLE. What a solution!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my python solution :

just mark all the multiple of the number which not belongs to the set

if any number belongs to the set then we can not remove it so break

test = int(input())
while test:
    test -= 1
    n = int(input())
    x = input()
    x = "A" + x + "B"
    cost = 0
    d=dict()
    for i in range(1,n+1,1):
        k=i
        while k<=n:
            if x[k]=='1': break
            else:
                if k  not in d:
                    d[k]=i
                    cost+=i
            k=k+i

    print(cost)
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, can I get a small wrong TC for problem D (slime escape), this is my 174674671, I've already tried all the ones in the editorial and they work against it.

Ed1: Solved it. 174904698, thanks to a beeg brain person who found me a failing tc. It might help other people so I'm posting it here. I've also collected all the other tc posted in this blog.

Aggregated TCs for problem D, Slime Escape
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tried to see whether 1734D had some easier implementation but even the top submissions are pretty complicated.

Here's my submission using Two Pointers

Submission 1734D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please tell me what's wrong with my solution to problem D? Thanks in advance. https://codeforces.com/contest/1734/submission/174838065

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I have no idea what's going on in your code but it fails against the last testcase which I've aggregated above. I hope that helps you.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F, Digit DP solution: "After processing each bit $$$k$$$, we should have the following: the number of integers $$$x$$$ between $$$0$$$ and $$$⌊\frac{m}{{2^k}}⌋$$$ inclusive which have the following property:...."

I feel difficult to understand why the range is between $$$0$$$ and $$$⌊\frac{m}{{2^k}}⌋$$$. Anybody explains to me, please. <33