first

second

Problem F can also be solved using divide and conquer.

If we are at range [L, R] with the recursion, let mid = (L + R) / 2. We will answer all queries [ql, qr] where ql <= mid < qr.

This can be easily done using 2 knapsacks, one from mid to L and one from mid+1 to R.

Submission link

I didn't found divisibility rule for 7 anywhere how it was figured out in problem B??

i want to explain easier approach of E but bad englis, you can check my sub tho

There is still a greedy way to pass tests in E by applying an operation when needed and running it min(n,m) times. Meaning complexity would be $$$O(tnm*min(n,m))$$$

Submission

I would like to either see it hacked or disproven. Unless that is correct which i highly doubt as I wasn't able to prove it.

C was really interesting! Hopefully will be able to solve C in div 2 next time.

11?

For the problem E tutorial, can anyone help me with the bound on the number of edges in the operation graph?

I wrote a brute-force solution that passed with complexity $$$O(tnm*min(n,m)*\log{A})$$$.

In 2043B - Цифры definition of first way, I think there is a mistake.

(123 − 456 + 9) is -324, and it's not divisible by 7 because -324 % 7 is 5.

I think it must be (569 − 234 + 1). {(569−234+1) = 336 % 7 = 0}

awoo

2043F - Ним. Nah, I've forgotten the dp way for finding xor = 0, and I wrote meet in the middle, because we can remove all the elements except for 7. So I can test if I can leave exactly 1 element, 2 elements, ..., 6 elements. And to check if I can leave 6 elements, I can check a pair of (3, 3) elements. 298456482

F is a cool problem

For problem D: "This should mean that it is divisible by at least 15 primes which are greater than 37" Why? This one number can fix many pairs, by it, and the numbers it pairs with, all having 41 (say) as a prime divisor. The argument can be made to work, but what is written is I think wrong. Please clarify.

awoo Ferume BledDest

In problem G you said that : Unfortunately, it is practically impossible to fit this within time limits, so let's try to improve the solution.

But when I submit this solution with B=1300, it has got an accepted with time 7700ms

https://codeforces.net/contest/2043/submission/298343933

If it should get a TLE, try to add some big tests that makes B=1300 worst.

For problem $$$D$$$, I miscalculated that if we consider all possible pairs of integers from intervals $$$[l,l+10)$$$ and $$$(r−10,r]$$$, we will find at least one coprime pair. But, the problem passed the system tests. Can anyone prove it or uphack the solution?
Submission — 298478051

can someone please explain why it is giving tle[submission:https://codeforces.net/contest/2043/submission/298310318]

Nobody has mentioned the following method for Problem E, which was much more intuitive than the graph method for me:

For each binary matrix B, the final move must result in a column of all 1s or a row of all 0s. Therefore, we can go backwards from B to A and ignore all rows and columns once we know there is a later operation that can set it to be accurate in B. This can be done simply by keeping a counter and sum for each row/column.

Submission here: https://codeforces.net/contest/2043/submission/298482881

I am facing a lot difficulty in understanding problem D.

can someone explain it to me.

Problem G appeared in a contest on Luogu 5 years ago, here is the link: P6019 [Ynoi2010] Brodal queue

The problem statement on Luogu is:

1 l r x: for( i = l ; i <= r ; i++ ) a[i] = x;

2 l r: count the number of (i,j) that l<=i<j<=r and a[i]==a[j]

Can someone explain C a little better to me please. I solved D but just cannot understand C.

I noticed that in test case 2 of Problem C that the test case

2

-5 -1

is repeated many, many times. It seems there is an error in the test case, as I would assume it was meant to iterate through several cases. Most notably the tests during the contest miss a notable class of test cases such as 1 -1, -1 1, 1 1 -1, -1 -1 1, 1 -1 1, -1 1 -1, etc., and I am aware that test 2 is meant to iterate through such small cases, not repeat the same case repeatedly.

Specifically, this is the class of test cases of 1s and -1s whose prefix sums are always >= or <= 0. This mistake cost me and other contestants since our incorrect solutions passed during contest. Can a writer please address this?

Problem with a similar approach to the C problem: 1695C. Zero Path

Can someone please give me a hint for Problem C: Sums on Segments?

I just need a hint to start thinking in the right direction. I tried solving it before. but it giving TLE.

https://codeforces.net/contest/2043/submission/298498396 what is wrong in this thinking?

In A.

Why this doesn't work. (ll)pow(2LL,(ll)(floor)(0.5*log2(n)))

It is also doing 2 to the power of floor of log4(n)

In solution for f, shouldn't the condition

$$$if (dp[i][val][fl].cnt > 0)$$$

instead be $$$if(dp[i][val][fl].cnt >= 0)$$$??

As we are modding and that may cause cnt to be zero.

Edit : Now they fixed it

For problem G, the input format requires us to solve the query in an online way. May I know how to solve it in an offline way?

In problem F, I use long long to store the number of ways, and get a TLE.

Can somebody explain why this fails? 298283845

Adding even digits (except 0 ) to B would have made the problem much more elegant.

BTW for people who don't know, a number is divisible by 2 if the last digit is divisible by 2

a number is divisible by 4 if the concatenation of the last two digits ( with leading zeros if less than two digits) is divisible by 4

a number is divisible by 8 if the concatenation of the last three digits ( with leading zeros if less than three digits) is divisible by 8

a number is divisible by 6 if it is divisible by 2 and 3 ( sum of digits is divisible by three and the last digit is even).

Can someone give me advice to solve problem G in $$$O((n+q)\sqrt n\log(\sqrt n))$$$ or it is impossible, thanks.

298614069

If you do block decomposition of size $$$O(n^{1/4})$$$ on the $$$blocks$$$ array, you could also attain $$$O(1)$$$ update and $$$O(sqrt(n))$$$ query complexity. I think it's more intuitive, but it seems a bit slower.

Hello everyone. I am not able to fully understand solution for problem E (Matrix Transformation). In the binary matrix of A and B, if a bit is not matched then operations must be performed on A(Row or column) to get the matrix equal to B and if it changes anything else then an operation must also be performed to change it back. But how that results in a directed graph of operations which results the answer?

One way I thought was to perform operation for every row or column in place and take the operation and then when I go ahead(left top corner to right bottom simple matrix travel) if I find any unequal again, then again make the operation but here the previous values may also change then how we think from here?

After the graph is constructed, I am fine with topological part, that is simple.

for 2043E - Matrix Transformation can anyone explain why a solution like 298348918 works?

I mean why doing the operation 30 times is enough? my submission was the same but the loop runs min(n,m)+1 times

2043D — Problem about GCD

Upon request, I wrote a proof for the following fact.

Given $$$R - L \geq 21$$$ and $$$1 \leq L \leq R \leq 10^{18}$$$, there exists $$$(x, y)$$$ such that $$$L \leq x, y \leq R$$$, $$$\gcd(x, y) = 1$$$, and $$$R - L - 21 \leq y - x \leq R - L$$$.

https://atcoder.jp/contests/arc137/editorial/11700

Can someone figure out what error I'm making over here for C problem Here is the submission link https://codeforces.net/contest/2043/submission/298358310

Why is problem F so easy :( :( :(, I just spent about 5 minutes to think, but in the original contest, I did not read this :(

Resuming Codeforces after a couple of years,

my python solution for 2043E — Matrix Transformation is giving TLE in test case 2 and time limit is just 1 second for pypy and python. Should I shift to C++ for codeforces?

Can anyone debug my code on problem E? I kept TLE on test 3 and I discovered that a lot of people TLE3 changed their solution at last but I don't want to change my solution

E has a (in my opinion) simpler solution.

As mentioned in the editorial, consider the case when $$$A_{i,j}, B_{i,j} \in \{0, 1\}$$$.

Observation 1: If a row of $$$B$$$ is all 0s, then we can disregard that row (and the corresponding row in $$$A$$$) and solve the problem for the remaining sub-matrix. This is because we can reserve the last operation in our final sequence of operations to update that row, after we have dealt with the rest of the matrix. Same observation holds if a column of $$$B$$$ is all 1s.

Observation 2: Suppose no row of $$$B$$$ is all 0s, and no column of $$$B$$$ is all 1s. Then, the answer is true if an only if $$$A=B$$$. This is because any non-empty sequence of operations will end up with a matrix that either has at least one row of all 0s (if the last operation was a row update) or at least one column of all 1s (if the last operation was a column update)

With these two observations in mind, we have the following pseudo-code

while(true){
  // delete a row of all 0s from B if it exists
  // delete a column of all 1s from B if it exists 
  // if nothing was delete, break  
}
// check if the A=B for the surviving rows and columns

To actually implement it, you can just maintain two sets/priority queues — one for rows (sorted by the number of 0s in the row) and one for columns (sorted by the number of 1s in the column). Also maintain rows_deleted and columns_deleted. Then, in the loop, you just need to check if the top member of the set/priority queue for rows has m-columns_deleted elements (and if the top member of the set/priority queue for columns has n-rows_deleted elements). The complexity is O(log(A)(nm + (n+m)log(n+m)))

Here is my submission: 299025009

In problem E, I mistakenly reversed the edges of graph(kind of a transpose of graph). Then the test case failed. But, for a directed graph, even if the edges are reversed, it should not affect cyclicality of the graph. ~~~~~ Your code here... bool check(int idx){

int sz=n+m+1;
 Graph G(sz);
 vector<bool>rows(n+1,false),cols(m+1,false);
 for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        int a1=get_bit(a[i][j],idx);
        int b1=get_bit(b[i][j],idx);
        if(a1!=b1){
            if(b1==0){
             rows[i]=true;
            }
            else{
                cols[j]=true;

            }
        }
        if(b1==0){
            G.addEdge(i, j+n);            
        }
        else{
            G.addEdge(j+n,i);            
        }
    }
}
for(int i=1;i<=m;i++){
    if(cols[i] && G.dfs(i+n)){
        return false;
    }
}
for(int i=1;i<=n;i++){
    if(rows[i] && G.dfs(i)){
            return false;
    }
}

return true;

}

~~~~~

I even tried using cols[j]=0 instead of rows[i]=0 and the vice-versa. Can you give a test case? I had thoughts on the lines like n!=m. Please help

https://codeforces.net/contest/2043/submission/299169457
My solution for 2043F — Nim:
- 'The maximum number of piles that can remove' means 'The minimum number of piles that can keep'
- Due to 0<=a[i]<=50, we can use prefix sum to count the elements between l and r
- If there is 0 in the elements, there are count[0] number of ways
- If there is any elements that occurs at least twice, the minimum number of piles that can keep are 2
- Else now each elements occurs at most 1, count the minimum number of piles to reach 0 and the number of ways for that:

		ca, cb := Counter(Repeat(10, 64)), Counter{}
		for i := range count {
			if count[i] == 0 {
				continue
			}
			for i2 := range ca {
				if ca[i^i2] < ca[i2]+1 {
					continue
				} else if ca[i^i2] == ca[i2]+1 {
					cb[i^i2] += cb[i2]
				} else {
					ca[i^i2] = ca[i2] + 1
					cb[i^i2] = cb[i2]
				}
			}
			ca[i] = 1
			cb[i] = 1
		}

can someone explain the solution of E more intuitively the graph idea

For problem D, it is mentioned that the problem for each testcase can be solved in K^2*log(A), where K is the number of numbers we check from L and R, and A is the bound on the numbers(for gcd). It has also been shown that the bounds for K are <=40. But then number of operations per testcase is 40*40*log(1e18) = 95671.52913 operations. Multiplying by the maximum number of testcases(1000) the overall number of operations should be 95671.52913*1000 = approximately 9.6*1e7 operations. The rule of thumb I know is that 1e8 operations take 1s, and we are not doing simple operations in the code since we use modulo(%), which takes more time, to compute gcd. So, even after the rigorous proof, it seems that the solution will barely pass the 1s time limit. This does not seem like a good solution and that the only reason solutions of this form passed was because the testcases were not that stringent.

for problem 2043D - Problem about GCD

The idea mentioned in this problem , is it really common ?

any source from where I can learn more of these Number theory facts with some proofs?