awoo's blog

Educational Codeforces Round 163 Editorial
By awoo, history, 6 weeks ago, translation, In English

1948A - Special Characters

Idea: BledDest

Tutorial
Solution (Neon)

1948B - Array Fix

Idea: BledDest

Tutorial
Solution (Neon)

1948C - Arrow Path

Idea: BledDest

Tutorial
Solution (Neon)

1948D - Tandem Repeats?

Idea: BledDest

Tutorial
Solution (awoo)

1948E - Clique Partition

Idea: BledDest

Tutorial
Solution (BledDest)

1948F - Rare Coins

Idea: BledDest

Tutorial
Solution (Neon)

1948G - MST with Matching

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +93
  • Vote: I do not like it

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

In problem B why do we need to iterate through array from right to left and not from left to right?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Counterexample:

    1

    3

    12 46 20

    If we will iterate from left to right we will get:

    1) 12 < 46. Don't change the array

    2) 46 > 20. Split 46 by 4 and 6

    And we got:

    12 4 6 20. Which is not a non-growth sorted array.

    If we will iterate from right to left we will get:

    1) 46 > 20. Split 46 by 4 and 6

    2) 12 > 4. Split 12 by 1 and 2

    And we got:

    1 2 4 6 20. Which is a non-growth sorted array.

    Summary, iterating from left to right will give us the wrong answer. This is because the right element can split and become smaller than the left element, but we have already checked that the left element is larger than the right element and will not go back to check it again.

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

    Suppose initially $$$a_{i-1} \le a_i$$$; but after considering $$$a_i$$$ with $$$a_{i+1}$$$, we find out that we have to split $$$a_i$$$. This might break the condition $$$a_{i-1} \le a_i$$$, so if we iterate from left to right, we sometimes have to backtrack to fix the conditions we've broken

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

    You can go from left to right also. My logic while going from left to right: https://mirror.codeforces.com/contest/1948/submission/251609551

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

    I solved the problem by iterating from left to right with following logic: you want current element (CUR which can also be last digit if we divided the number in previous step) to be as small as possible because that can only help for next numbers, so you have two cases: 1) if you CAN divide current element i into it's digits with equality holding: CUR <= dig1 <= dig2 you do so, because then CUR = dig2 which is smallest possible. If you can't, if CUR <= a[i] then CUR = a[i]. If both do not hold, return NO. This works because at any moment, last element you have in your new array will be smallest possible which can only help for both of previously mentioned checks.

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

I write a simple brute force for Problem :B. But it is failing of hidden case.I am not able guess what it lacks. Can you please help. https://ideone.com/g5da0S

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

In the place of tutorial of G ,it is showing tutorial of F.Update it please.

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

is it possible to solve Div2-D in less than O(n^2)?

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

Can someone please explain in solution of problem C. What are ok1 and ok2 actually signifying? How are we taking the indices of ok1 and ok2.

I have been trying to understand for an hour, please help.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    $$$ok1[i]$$$ and $$$ok2[i]$$$ refer to the second solution from the editorial. If $$$ok[i]$$$ is true, then the $$$i$$$-th diagonal pair of odd cells has at least one arrow to the right ($$$ok1$$$ and $$$ok2$$$ denote different diagonal directions).

    You can instead check every diagonal pair by bruteforcing all pairs of adjacent odd cells.

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

      but if n=4 and i,j=0,3.then (j-i+1)/2=2.ok2.size() is 2,so will cross the border?

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought D was hashes, wasnt able to implement it well tho... The author's solution is kinda weird

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

    Let me explain my solution of D -- I hope this might be easier to understand.

    First, let's fix the length of a tandem, and call it $$$2d$$$ ($$$d$$$ is the length of each half of the tandem). For each $$$d$$$, we try to find a tandem repeat of length $$$2d$$$, and the answer to the problem is the length of the longest one we could find. Also let's define the length of $$$s$$$ as $$$n = |s|$$$.

    A substring $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ is a tandem repeat if, for all indices $$$i \in \{ l, l+1, \ldots, l+d-1 \}$$$, $$$s_i = s_{i+d}$$$ is held. So, what matters here is the relationship between characters with distance $$$d$$$. With that in mind, let's define an array $$$\{ a_i \} \; (1 \le i \le n - d)$$$ as follows: $$$a_i = 1$$$ if $$$s_i = \text{'?'}$$$ or $$$s_{i+d} = \text{'?'}$$$ or $$$s_i = s_{i+d}$$$; $$$a_i = 0$$$ otherwise. Intuitively, $$$a_i$$$ is $$$1$$$ if $$$s_i$$$ and $$$s_{i+d}$$$ are equal or can be made equal. With this array $$$\{ a_i \}$$$, we can rephrase the condition that $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ can be a tandem repeat to: $$$a_l = a_{l+1} = \cdots = a_{l+d-1} = 1$$$ (selection of $$$\text{'?'}$$$s do not matter because each pair of letters in a tandem do not interfere with any other pairs). Thus, if there is a contiguous sequence of $$$1$$$s of length $$$d$$$ in $$$\{ a_i \}$$$, we have a tandem repeat of length $$$2d$$$; otherwise, there's no such tandem.

    Building $$$\{ a_i \}$$$ and finding contiguous $$$1$$$s can be done in $$$O(n)$$$-time, so $$$O(n^2)$$$-time overall.

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

"Kruskal's algorithm with DSU might be a bit slower, but can also get accepted"

I don't thinks so :(

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I think it's possible to optimize this, for example, by sorting all edges only once, not for every Kruskal run.

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

      Didn't think of that, thanks you!

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

Problem D (Tandem Repeat) Video Editorial : (Audio : Hindi)

Link : ---Click Here (YOUTUBE)

Problem A, B Video Editorial : --Click Here

→ Reply
»
6 weeks ago, # |
← Rev. 4   Vote: I like it +28 Vote: I do not like it

Here's a formulation of F as a probability problem (mostly because I am in a probability class right now :3).

Suppose we have $$$s$$$ silver coins in the bag, $$$g$$$ gold coins in the bag, $$$t_s$$$ total silver coins and $$$t_g$$$ total gold coins. The value of the silver coins in the bag is represented by the random variable $$$S\sim \mathrm{Binom}(s,\frac{1}{2})$$$. The value of the rest of the silver coins is represented by the random variable $$$S'\sim \mathrm{Binom}(t_s-s,\frac{1}{2})$$$.

We wish to compute

$$$ \mathbb{P}\left(S + g> S' + t_g-g\right) = \mathbb{P}\left(S - S'> t_g-2g\right). $$$

The difference between random variables isn't nice to compute, so we want to turn it into a sum. Notice that the random variable $$$S' ':= t_s-s-S'$$$ has the same $$$\mathrm{Binom}(t_s-s,\frac{1}{2})$$$ distribution as $$$S'$$$ (this only holds because our probabilities are $$$\frac{1}{2}$$$). Therefore,

$$$ \mathbb{P}\left(S - S'> t_g-2g\right) = \mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right). $$$

But the sum of binomial random variables is itself a binomial random variable: $$$S+S' '\sim \mathrm{Binom}(t_s-s+s,\frac{1}{2}) = \mathrm{Binom}(t_s,\frac{1}{2})$$$, which gives us the formula

$$$ \mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right) = \left(\frac{1}{2}\right)^{t_s}\sum_{k=t_s - s +t_g-2g + 1}^{t_s}\binom{t_s}{k}. $$$

Here is my submission implementing this: 251836049.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This n^3 method passed systest. Can anyone hack it?

code

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Editorial For Problems A,B,C,D,E,F.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G is awesome. I cannot put forward Konig's theory because I didn't realize that a tree is a bipartite graph during the contest. Sad.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please provide the solution of B using DP , I think we can use bit masking to solve this as the value of Dp[i] (whether performing operation on the i'th index will result in a sorted array or not ) depends on the pervious values too , so we can have a mask that denotes on which of the previous indexes we have performed the operation ,Thanks for the help .

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fun problems, I like this contest!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B i dont understand why when i Used a variable to iterate through the inputs of the array it and manipulate using the same algorithm it didnt work , however when i accepted all inputs in a vector , and started iterating and using my algorithm it worked out ? (check my accepted solution and the rejected one Using the Second Testing table) 252372121 252375040 Would be nice if someone can explain :/

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D have weak test cases

My O(N^3) solution passes : O(N^3) submission

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

I have found an alternative solution to problem C only using if condition and do while loops -(https://mirror.codeforces.com/blog/entry/127853)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, for Problem D, when I run my code locally with the provided testcases I get the correct answer. However, when I submit, I get a different output. Any ideas what's going on? link to submission

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

Hi, can anyone explain for me why the example answer of F — rare coins is that long line of integer?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it 
1948C - Arrow Path
The key observation for this problem that works for all these approaches is that, since we never skip a move and never try to move outside the grid, we can split the cells into two groups:

if the sum of coordinates of the cell is even (we will call it "even cell"), we can end up in such a cell only after moving along the arrow (only after the second action during each second);
otherwise, if the sum of coordinates of the cell is odd (we will call it "odd cell"), we can end up in such a cell only after making a move on our own (only after the first action during each second).

I am not able to understand how the parity of coordinates sum will decide the category of a cell?

→ Reply