20 minutes left =.=

I used lots of if-else :v :v

You can see my solution it's easy to understand

You can make use of dynamic programming, everytime either leave a digit or add it to your total sum, if at the end the total sum is divisible by 3, then store the total no. of digits you erased from the given string of numbers. print the minimum of it. My solution : https://atcoder.jp/contests/abc182/submissions/17971476

-fsanitize=address

hint: Transform the problem to finding the number of (y — X) instead of y.

First of all notice that any number $$$X$$$ has unique minimal representation. This can be proved by greedy exchange (using the fact that each successive number is a multiple of the previous number).

Now, notice the isomorphism (structure equivalence) between the number bases and the (minimal) representation of each number in the system of Yens. There are two properties which are maintained:

1) If highest bit of $$$A$$$ is greater than $$$B$$$ in our Yen-system, then $$$A>B$$$.

2) Each number has unique representation.

So we can think of an equivalent problem: given a number $$$X$$$, how many numbers $$$b$$$ there are such that $$$X+b=a$$$ and $$$a$$$ and $$$b$$$ have no bit in common?

This can be solved, after some thinking, with DP.

Array g[] represents the representation of $$$X$$$ in Yen-system

We introduce the concept of "span". span[j] represents the number of elements after the $$$j^{th}$$$ bits of X which have maxed out values of their bit. Then if g[j]>0, we can use this bit in the number $$$b$$$ such that DUE TO the process of carry-over, we don't have this bit in $$$a$$$. You can see the details of dp transition in my Beautiful AC Code

I just came out this solution, not pretty sure that it is correct. However it does get me AC.

The problem is same as "Find the number of integer $$$r$$$ with length $$$N$$$ (leading 0 is allowed) in base $$$A$$$ that shares no common digit with $$$X + r$$$, i.e., $$$\forall_{0 \le i \lt N}, r_i = 0 \lor (X + r)_i = 0$$$".

Let $$$c$$$ be carry, $$$y = X + r$$$, we have ($$$N$$$ = 4):

In particular, all digits $$$i$$$ satisfy ($$$m_i = A_{i + 1}/A_i$$$ is the limit of digit $$$i$$$):

Let $$$dp[i, c]$$$ = the number of valid ways to fill digits $$$[0, i)$$$ while $$$c_i = c$$$. This dp is computed from lower digit to higher digit due to carry-over.

By iterating all possible values ($$$0 \le r_i \lt m_i)$$$ of $$$r_i$$$, we can get an correct state transition, but it will get TLE. Key observation is that we don't need to iterate all values of $$$r_i$$$. Since $$$r_i = 0 \lor y_i = 0$$$, there are only few valid conditions.

We decompose $$$r_i = 0 \lor y_i = 0$$$ into 3 disjoint conditions:

1. $$$r_i = 0 \land y_i = 0$$$
2. $$$r_i = 0 \land y_i \ne 0$$$
3. $$$r_i \ne 0 \land y_i = 0$$$

Let's consider when will these conditions be true?

1. By substituting $$$r_i = 0, y_i = 0$$$ into the formula of digit $$$i$$$, we find that only when $$$(c_i + x_i) = 0 \pmod {m_i}$$$, condition 1 is true. We transfer to $$$dp[i + 1, c_{i+1}]$$$.
2. Substituting $$$r_i = 0$$$ into formula, we find that only when $$$(c_i + x_i) \ne 0 \pmod {m_i}$$$ will $$$y_i \ne 0$$$ be true. We transfer to $$$dp[i + 1, c_{i+1}]$$$.
3. Substituting $$$y_i = 0$$$ into formula, we find that only when $$$(c_i + x_i) \ne 0 \pmod {m_i}$$$ will $$$r_i \ne 0$$$ be true. Notice that in this condition, there will be a carryover. We transfer to $$$dp[i + 1, 1]$$$.

That's all for the dp transition. Here is my submission.

Chinese version

Yes. link

Just try every subset with bitsets or recursion. my solution

You can think of finding the longest subsequence which has sum divisible by 3. Then you can do number of digits — longest subsequence

O(logn) Solution using DP. My Code : Link

No, just annoying implementation.
I used prefix and suffix sums on the rows and the columns.

No, just optimize the brute force solution a little bit.

The brute force solution is, for each bulb, and for each direction, start from the bulb, and go along with this direction until you meet a block, set each grid passed illuminated by the bulbs. And then, iterate all grids, count the number of grids illuminated by the bulbs. The time complexity is $$$O((H + W)N + HW)$$$.

The brute force solution might get TLE, although I think it's time complexity is good enough to pass.

While going along with one direction, you can stop not only when you meet a block, but also when you meet a bulb. If you do so, the time complexity will be $$$O(HW)$$$ cause you will pass a grid at most 4 times.

Using this matrix struct with already clock_rotate, you only need to repeat 4 times rotating the matrix every rotation.

Submission

Calculate prefix sums on the input. Also calculate the maximum sum you achieve on the input for every $$$0$$$ to $$$i$$$, where i is from 0 to N — 1 (0-based indexing). Then, you can find the maximum coordinate by iterating from 0 to n and adding the maximum sum in range(0, i) to your current coordinate.

auto solve () -> void {
    int n;
    std::cin >> n;
    std::vector <int64_t> a (n), pref (n + 1), best (n + 1);
    for (int i = 0; i < n; ++i) {
        std::cin >> a [i];
        pref [i + 1] = pref [i] + a [i];
        best [i + 1] = std::max({best [i], pref [i], pref [i] + a [i]});
    }

    int64_t max = 0, x = 0;
    for (int i = 0; i < n; ++i) {
        max = std::max(max, x + best [i + 1]);
        x += pref [i + 1];
    }

    std::cout << max << '\n';
}

Let us define end[i] as coordinate after the end of ith round (let us assume 0-based index) then, end[i] = end[i-1] + prefix[i]
Now, if your answer is after round i, and before round i+1

ans = max(end[i], end[i]+prefix[0] , end[i]+prefix[1] , end[i]+prefix[2] ,..)

ans = max(end[i], end[i]+max(prefix[0],prefix[1],..,prefix[i]))

sudo code :

prefix[0] = a[0]
for i = 1 to n-1
   prefix[i] = prefix[i-1]+a[i]
end[0] = prefix[0]
for i = 1 to n-1
   end[i] = end[i-1]+prefix[i]

max_so_far = prefix[0];
ans = max(0,prefix[0]);
for i = 1 to n-1
   max_so_far = max(max_so_far , prefix[i]);
   ans = max(ans, end[i-1] + max_so_far);

There are a lot of ways. Shortest would be: assume light doesn't pass through a square with another light bulb, which doesn't affect the answer, and then for each light bulb iterate through all squares it illuminates and mark them (with the modified rules each square will be touched at most $$$4$$$ times, so it's $$$O(HW)$$$).

am I the only one who solved it with Binary Search ?

The positions after each step are:

Therefore, the greatest coordinate occupied is $$$2$$$.

You can just brute force for the possible value of the answer from 2 to 1000. Whichever value gives maximum count of divisions is the answer.

Brute force numbers from 2 to 1000 and calculate how many numbers in A are divisible by them. The one with the maximum count of numbers divisible is the answer.

https://mirror.codeforces.com/blog/entry/84405?#comment-719394

It's a standard knapsack problem. For every digit you either use it in the answer or you don't.

u can use recursive, it will be O(2^digit)

It can be solved using greedy approach as well. As for N to be divisible by 3, sum of its digit must be divisible by 3. And sum%3 can be either 0, 1 or 2.
If its 0 than we have to do nothing.
If it's 1 then we remove one digit (which is 1 mod 3 i.e. d%3=1) or 2 digits (which are 2 mod 3 .i.e, d%3=2).
Similarity for the case where sum%3 = 2.

If we aren't able to remove the digits in such a way then answer is -1.

I think the solution with bitmasks is pretty nice

My submission

Yes, for example, see my submission in my comment here.

Your solution for solving F is fantastic.

Thanks for sharing that.

Can we use line sweep for E to solve for any H,W.

https://atcoder.jp/contests/abc182/submissions/17972323 hope this helps!