Разбор Educational Codeforces Round 173

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

2043A - Преобразование монет

Разбор

Решение (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    ans = 1
    while n > 3:
        n //= 4
        ans *= 2
    print(ans)

2043B - Цифры

Идея: AcidWrongGod

Разбор

Решение (BledDest)

import sys
 
sys.set_int_max_str_digits(6000)
 
def fact(x):
    if x == 0:
        return 1
    return x * fact(x - 1)
 
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    n = min(n, 7)
    s = int(str(k) * fact(n))
    for i in range(1, 10, 2):
        if s % i == 0:
            print(i, end = ' ')
    print()

2043C - Суммы на отрезках

Идея: Ferume

Разбор

Решение (awoo)

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l1, r1 = 0, 0
	l2, r2 = 2*10**9, -2*10**9
	
	pr = 0
	mnl, mxl = 0, 0
	mnr, mxr = 2*10**9, -2*10**9
	for i in range(n):
		pr += a[i]
		if a[i] != -1 and a[i] != 1:
			mnr, mxr = mnl, mxl
			mnl, mxl = pr, pr
		l1 = min(l1, pr - mxl)
		r1 = max(r1, pr - mnl)
		l2 = min(l2, pr - mxr)
		r2 = max(r2, pr - mnr)
		mnl = min(mnl, pr)
		mxl = max(mxl, pr)
	res = []
	if l2 > r1:
		res = list(range(l1, r1 + 1)) + list(range(l2, r2 + 1))
	elif r2 < l1:
	    res = list(range(l2, r2 + 1)) + list(range(l1, r1 + 1))
	else:
		res = list(range(min(l1, l2), max(r1, r2) + 1))
	print(len(res))
	print(*res)

2043D - Задача про НОД

Идея: Ferume

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
long long gcd(long long x, long long y)
{
    if(x == 0) return y;
    else return gcd(y % x, x);
}
 
void solve()
{
    long long l, r, g;
    scanf("%lld %lld %lld", &l, &r, &g);
    long long L = l + (l % g == 0 ? 0 : g - (l % g));
    long long R = r - r % g;
    for(int i = 0; i <= (R - L) / g; i++)
        for(int j = 0; j <= i; j++)
            if(gcd(L + j * g, R - (i - j) * g) == g)
            {
                printf("%lld %lld\n", L + j * g, R - (i - j) * g);
                return;
            }   
    puts("-1 -1");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

2043E - Преобразование матриц

Идея: Ferume

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
struct graph
{
    int V;
    vector<vector<int>> g;
    vector<int> color;
 
    bool dfs(int v)
    {
        if(color[v] != 0) return false;
        color[v] = 1;
        bool res = false;
        for(auto y : g[v])
        {
            if(color[y] == 2) continue;
            else if(color[y] == 0)
                res |= dfs(y);
            else res = true;
        }
        color[v] = 2;
        return res;
    }
 
    void add_edge(int x, int y)
    {
        g[x].push_back(y);
    }
 
    graph(int V)
    {
        this->V = V;
        this->g.resize(V);
        this->color.resize(V);
    };
};
 
int get_bit(int x, int y)
{
    return (x >> y) & 1;
}
 
bool check(const vector<vector<int>>& a, const vector<vector<int>>& b, int k)
{
    int n = a.size();
    int m = a[0].size();
    vector<bool> must_row(n);
    vector<bool> must_col(m);
    auto G = graph(n + m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(get_bit(a[i][j], k) != get_bit(b[i][j], k))
            {
                if(get_bit(b[i][j], k) == 0) must_row[i] = true;
                else must_col[j] = true;
            }
            if(get_bit(b[i][j], k) == 0) G.add_edge(j + n, i);
            else G.add_edge(i, j + n);
        }                 
    for(int i = 0; i < n; i++)
        if(must_row[i] && G.dfs(i))
            return false;
    for(int j = 0; j < m; j++)
        if(must_col[j] && G.dfs(j + n))
            return false;
    return true;
}
 
void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    auto b = a;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &b[i][j]);
    for(int i = 0; i < 30; i++)
    {
        if(!check(a, b, i))
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

2043F - Ним

Идея: Ferume

Разбор

Решение (awoo)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
const int MOD = 998244353;
 
int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
struct state{
	int mx, cnt;
};
 
void merge(state &a, int mx, int cnt){
	if (a.mx > mx) return;
	if (a.mx < mx) a.mx = mx, a.cnt = 0;
	a.cnt = add(a.cnt, cnt);
}
 
state dp[52][64][2];
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	int mx = *max_element(a.begin(), a.end());
	vector<vector<int>> cnt(n + 1, vector<int>(mx + 1));
	forn(i, n){
		cnt[i + 1] = cnt[i];
		++cnt[i + 1][a[i]];
	}
	forn(_, q){
		int l, r;
		cin >> l >> r;
		--l;
		memset(dp, -1, sizeof(dp));
		dp[0][0][0] = {0, 1};
		forn(i, mx + 1){
			int c = cnt[r][i] - cnt[l][i];
			int c2 = c * 1ll * (c - 1) / 2 % MOD;
			forn(val, 64) forn(fl, 2) if (dp[i][val][fl].cnt >= 0){
				if (c > 0)
					merge(dp[i + 1][val ^ i][true], dp[i][val][fl].mx + c - 1, mul(dp[i][val][fl].cnt, c));
				if (c > 1)
					merge(dp[i + 1][val][true], dp[i][val][fl].mx + c - 2, mul(dp[i][val][fl].cnt, c2));
				merge(dp[i + 1][val][fl], dp[i][val][fl].mx + c, dp[i][val][fl].cnt);
			}
		}
		auto ans = dp[mx + 1][0][1];
		if (ans.cnt == -1)
			cout << -1 << '\n';
		else
			cout << ans.mx << ' ' << ans.cnt << '\n';
	}
}

2043G - Задача на запросы

Идея: Ferume

Разбор

odd = int(input()) for n in range(1, 8 + 1): # factorial(8)=40320, if not found until 8, then forget it times = math.factorial(n) for d in range(1, 9 + 1): # Check every possible number if int(str(d) * times) % odd != 0: break else: print(n) # If n is greater than or equal to this value, it must be divisible by odd break else: print(None)

Комментарии (58)

Написать комментарий?

pohovanasalama

23 часа назад, # |

-25

first

→ Ответить

123gjweq2

-14

second

VMaksimoski008

+12

F can also be solved using divide & conquer.

If the recursion is at range [L, R], choose mid = (L + R) / 2 and answer all queries [ql, qr] such that ql <= tm and qr > tm.

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

Time complexity: O(NlogN * 63)

Submission link: 298444046

+18

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

Iingfunny

11 часов назад, # ^ |

very educational solution. thank you my bro

00xcvb

58 минут назад, # ^ |

could you explain me sum of segments

17 минут назад, # ^ |

Of course.

First of all, notice that the number that is not -1 or 1 is there to make the problem harder, so let's think how would we solve the problem if all numbers were 1 or -1.

I claim that if the minimum subarray sum is L, and the maximum subarray sum is R, than all sums in range [L, R] can be formed. The proof is in 2 parts:

Sums [0, R] can be made

Let the shortest segment with the maximum sum be [x, y]. If you remove the first or last element of the segment while you can in any order(example below), you will get to an empty segment with sum 0. Because the elemets are 1 or -1, to get to the empty segment, we have to pass a segment with sum 1. The same argument can be made for all sums up to R.

Example: 1 1 -1 1 1

Here the subarray with maximum sum is [1, 1, -1, 1, 1] and the sum is 3. If we remove the first element the segment will be [1, -1, 1, 1] with sum 2. Now if we remove the last 1, the segment will be [1, -1, 1] with sum 1. Let's remove the first 1 again, we will have [-1, 1] sum 0. Remove the 1 to have [-1] with sum -1. And finally remove the -1.

Notice that we saw every possible sum from 0 to 3, and consider the -1 we saw simply as a bonus. Any order of operations will lead to all sums in [0, R] to be seen.

The proof for [L, 0] is similar.

Now we will consider the acutal problem. The biggest bottleneck is the number that is not 1 or -1. We need to find a way to find the possible sums of subarrays that pass through that element.

Consider the example [1, -1, 10, 1, 1]. Let's break the array in 2 parts, one with all elements before the 10, one with elements after it. For example, [1, -1] and [1, 1]. Now choosing a subarray with tha 10 in it is simply choosing some suffix(empty allowed) from the first array , some prefix(empty allowed) from the second and appending the 10 between them. So, all sums will be in the form $$$suf + 10 + pref$$$. Since 10 is constant, we want to maximize and minimize $$$suf + pref$$$. To maximize, simply take the bigeest suffix and prefix, and to minimize take the minimums.

tkumar2602

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

anand_2703

23 часа назад, # ^ |

You can find it here https://en.wikipedia.org/wiki/Divisibility_rule

Thanks

adarshraj150820063108

22 часа назад, # ^ |

as d can be taken common everytime so you can just write as d*(1111.....) now if d is 7. It is always true that given number is divisible by 7 if not than you can check what is the minimum number of one is required to make it divisible by 7. I got that minimum 6 1's should be present so if n>=3 it is divisible by 7 regardless the value of d

Serioton_codes

13 часов назад, # ^ |

there are a lot of different rules out there the one you need here is that: if the alternating sum and difference of 3 digits from left to right is divisible by 7 then the number will be divisible by 7 for example: 12,332,455 :- value = (4+5+5)-(3+3+2)+(1+2) = 9 ; which is not divisible by 7 hence number is not divisible by 7.

for n!>=6 (i.e. n>=3, n!=6*k) number of digits will be multiple of 3 and 2, hence you always have even pair of alternating sum of 3 digits hence above value will always be 0 hence divisible by 7.

adedalic

2 часа назад, # ^ |

Using your "rule", $$$1022$$$ is not divisible by $$$7$$$, but $$$1022 = 146 \cdot 7$$$.

Typed_SIGTERM

kr25161

← Rev. 2 →

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

kingsmaker

read your solution, can you tell me a proof for why it was enough to check for only 10 numbers left and right?

21 час назад, # ^ |

i guessed it honestly. i dont have a good proof for that. i statistically thought a prime number would occur once every 10 numbers and applied that. but max difference between primes <= 1e9 is ~200 so l + 200 and r — 200 would be good bound to find a prime number.

gaspar.kristijan

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.

ibrm

I solved exactly like this, would be very nice if someone prove or hack it

_Crimson_

20 часов назад, # ^ |

I know right? I just solved it performing necessary operations on each row and column once, and i repeat it 100 times. It passes all the tests.

vstiff

18 часов назад, # ^ |

$$$min(n,m)$$$ seems logical, because you need space for a cycle. Let $$$min(m,n)=n$$$. Proof may be something like when $$$n=1$$$ it's obviously correct. For 2, maximum cycle is when setting some bits in one row breaks in another, and vice versa. For 3 same thing is for triangle, and so on.

When in doubt detect cycle using hash: 298400755

Uniqueone69

22 часа назад, # |

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

HoangMC2009

11?

_shriom_

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})$$$.

2077devwave

21 час назад, # |

In 2043B - Digits 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

JackOfMostTrades

The original number is 1234569, we take blocks of 3 digits from right to left.

569 - 234 + 1 = 366 ≡ 0 (mod 7).

BledDest

Yeah, this was an error, thank you. Will be fixed in a couple of minutes

17 часов назад, # ^ |

Thx for following up

MAKMED1337

2043F - Nim. 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

risingStark

can you explain this one bro? How did you arrive at this "because we can remove all the elements except for 7"?

19 часов назад, # ^ |

Because the size of the vector basis can't be more than 6 because $$$a_i \le 50$$$.

Shoeib

19 часов назад, # |

F is a cool problem

Mtaylor

18 часов назад, # |

For problem F, we can divide it into some easy sub-problems, We will calculate the minimum number of elements to get 0 xor from the subarray:

If we have 0 in the range, the answer always r-1, freq(0)
If we have an element with frequency >=2, the answer always r-l-1, sum of freq(i) *freq(i-1)/2
Now the size of the subarray <=50 because no element exist 2 times and more ( piegonhole principle), Now we can prove that at most we will select 8 elements from the range ( using the xor bases), we can find the answer using 2d dp with state (Number of taken elements, current xor) which is very similar to knpasack.

The solution is a bit slow but I think there are some nice obeservations here , Nice problem !

solution: 298471356

mathworker21

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.

If a prime is greater than the length of the segment (for example, $$$30$$$), there is at most one number in the segment that is divisible by it. So, if a number appears in $$$15$$$ or more pairs that are not fixed by primes less than $$$30$$$, every such pair should be "fixed" by a separate prime.

Oh, cause it's greater than the length. I see. Thanks.

Kareem_Elgoker

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.

sammyuri

Hacked

I guess it's quite difficult to make a set of test data that TLEs all possible choices of $$$B$$$, so $$$O((n + q) n^{\frac{2}{3}})$$$ solutions can get accepted, although they can then be hacked (including all but one of the in-contest submissions lol)

The lucky man who chooses 1300 in the in-contest :))

Thx for the hack :)

copyPasteCoder

16 часов назад, # |

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

djm03178

14 часов назад, # ^ |

Iirc https://codeforces.net/blog/entry/137682?#comment-1232017 is currently the strongest hack, not sure if anyone has managed to find something stronger than this yet.

aknov

14 часов назад, # |

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

RandomKami

13 часов назад, # |

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.

ODT

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]

deadlycoder82

12 часов назад, # |

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

om.nom

10 часов назад, # ^ |

For an array of only 1 and -1, the range of subarray sums is simply from the minimum sum to the maximum sum, as the sum changes incrementally by +1 or -1.

When the array contains x, the subarrays to the left and right of x consist only of 1 and -1. We calculate the range of sums for these subarrays independently. Since both ranges intersect at 0, the combined range will span from the minimum of the minimum sums to the maximum of the maximum sums.

To determine the range for segments that include x, start from x and move outward to the left and right, summing the values as you go. As you move, x will increment or decrement by 1 at each step, eventually reaching its maximum and minimum contributions.

So range is : Minimum Sum: min_prefix + min_suffix + x, Maximum Sum: max_suffix + max_prefix + x.

9 часов назад, # ^ |

Thank you so much!!

IceSerpent

10 часов назад, # |

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?