awoo's blog

Educational Codeforces Round 173 Editorial
By awoo, history, 23 hours ago, translation, In English

2043A - Coin Transformation

Idea: BledDest

Tutorial
Solution (BledDest)

2043B - Digits

Idea: AcidWrongGod

Tutorial
Solution (BledDest)

2043C - Sums on Segments

Idea: Ferume

Tutorial
Solution (awoo)

2043D - Problem about GCD

Idea: Ferume

Tutorial
Solution (BledDest)

2043E - Matrix Transformation

Idea: Ferume

Tutorial
Solution (BledDest)

2043F - Nim

Idea: Ferume

Tutorial
Solution (awoo)

2043G - Problem with Queries

Idea: Ferume

Tutorial
  • Vote: I like it
  • +48
  • Vote: I do not like it

»
23 hours ago, # |
  Vote: I like it -25 Vote: I do not like it

first

→ Reply
»
23 hours ago, # |
  Vote: I like it -14 Vote: I do not like it

second

→ Reply
»
23 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    very educational solution. thank you my bro

    → Reply
  • »
    »
    51 minute(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    could you explain me sum of segments

    → Reply
    • »
      »
      »
      11 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    23 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    13 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

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

      → Reply
  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    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)
    → Reply
»
23 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
23 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    20 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$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

    → Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

11?

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 hour(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    20 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    → Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      19 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
19 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

F is a cool problem

→ Reply
»
18 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
18 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.me/contest/2043/submission/298343933

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

→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      18 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Thx for the hack :)

      → Reply
»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/2043/submission/298482881

→ Reply
»
13 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I am facing a lot difficulty in understanding problem D.

can someone explain it to me.

→ Reply
»
12 hours ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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]

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/2043/submission/298498396 what is wrong in this thinking?

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Floating point values are imprecise (especially if they are big). You can easily experiment that

    (int)log2((1LL << 60) - 1)

    returns 60, while $$$\lfloor \log_2(2^{60} - 1) \rfloor = 59$$$.

    The takeaway is: don't use floating points, and stick to integers (unless floating point values are really necessary).

    → Reply
»
6 hours ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like 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?

→ Reply
»
93 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply