AVdovin's blog

Разбор Codeforces Round 991 (Div. 3)
By AVdovin, history, 12 days ago, In Russian

2050A - Переносы строк

Идея: kbats183

Решение
Код

2050B - Переливайка

Идея: AVdovin

Решение
Код

2050C - Неинтересное число

Идея: DanGolov

Решение
Код

2050D - Максимизация цифровой строки

Идея: AVdovin

Решение
Код

2050E - Три строки

Идея: pskobx, Vladosiya

Решение
Код

2050F - Максимальное модульное равенство

Идея: AVdovin

Решение
Код

2050G - Развал дерева

Идея: AVdovin

Решение
Код
  • Vote: I like it
  • +41
  • Vote: I do not like it

»
12 days ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Task G is almost identical to a task from the Polish Olympiad in Informatics called Parade. The only difference is in the POI task, you can not choose $$$a = b$$$.

→ Reply
»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it 
evc = n / 2;
if (n & 1) evc++;

is the same as 

evc = (n + 1) / 2 ;
→ Reply
  • »
    »
    12 days ago, # ^ |
    ← Rev. 3   Vote: I like it -10 Vote: I do not like it

    No. For example, $$$n = 6$$$. In the first case 6 / 2 = 3, then 3 & 1 is true and evc = 6 / 2 + 1 = 4. But in the second evc = (6 + 1) / 2 = 3.

    → Reply
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      I think you are incorrect, because if $$$n = 6$$$, then it is be 6 & 1 not 3 & 1, so for $$$n = 6$$$ it should give $$$3$$$, so Karim__2 formula is indeed correct.

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

        Oh, ok. Idk, I saw $$$n / 2$$$ instead of $$$n$$$

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

      oh sorry , stupid mistake

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

for C I'm getting different outputs on my system than the codeforces judge?

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

    for C output is either "YES" or "NO", if you are getting different means there is something wrong in you solution.

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

      in codeforces judge its outputting YES for cases where its outputting NO on my system and that is messing the ans up. U can view the code on ky latest submissions ig.

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

        The $$$|n|$$$ is atmost $$$10^5$$$. Please do not use an integer or, a long to store it, as it will round off to undesired values, due to cyclic nature of these data types in C++. Use a string to take the input instead.

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

          damn I mistook the range for the length of the number for the actual value of the number lol. You confused me a second time by typing |n| but yea I checked it, thx.

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

      https://mirror.codeforces.com/contest/2050/submission/295396526 why is this wrong for problem C?

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

    For C, will not be time complexity O(x*x) in the worst-case scenario where x is the length of the number? When the count of both 2s and 3s becomes equal to x/2. How is it getting accepted for a constraint of 10^5 on number length? Can you please clarify?

    → Reply
»
11 days ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Where is the formal proof of correctness to the editorial solution of D?

I was hoping to see the cleanest solution and proof to the problem, now the editorial for this problem is very unhelpful.

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

    Maximum digit can be 9. After each operation digit will decrease by 1, so we can do at most 9 operations. What is unclear?

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

    Why isn't the editorial's solution clean?

    My understanding of the editorial’s argument is as follows:

    First, we aim to maximize the digit at index $$$0$$$, and it’s clear that we need to choose a digit from the first 10 indices. The goal is to find the maximum value of $$$S_i−(i−j)​$$$, where $$$j$$$ is the index we are currently maximizing (starting with zero). In case of ties, we select the smallest $$$i$$$. We swap $$$i$$$ and $$$j$$$, and then repeat from the next index. This ensures that $$$s$$$ is maximized.

    Is this reasoning incorrect, or is it just informal?

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

      this is incorrect

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

      The editorial solution is clean. However, I cannot see a potential clean proof.

      Baiscally, the first step is defintiely correct, but the tie breaking is hard. You must show that among all future paths, you can select one to commit to, and it gives the best result (due to one reason or another).

      This cannot be done without any statements about the future situations, what you can do/comparing future situations.

      That said, the proof given by _Kee below is correct and clean enough. Thanks.

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

    I think the hard part is how to handle tiebreaking.

    Let's say we have an array $$$[a, b, 6, c, d, 9, \ldots]$$$ where $$$a < 4$$$, $$$b < 5$$$, $$$c < 7$$$ and $$$d < 8$$$, that is, $$$6$$$ and $$$9$$$ are the only digits that we can bring to the front. If we bring $$$6$$$ to the front, we get $$$A = [4, a, b, c, d, 9, \ldots]$$$. If we move $$$9$$$, we have $$$B = [4, a, b, 6, c, d, \ldots]$$$. So the problem here is: which is better?

    Let's think about the selection of later digits. First of all, the parts $$$[a, b]$$$ and $$$[\ldots]$$$ are shared in the same place between $$$A$$$ and $$$B$$$, so they equally affect the final result. Next, regarding the part $$$[c, d]$$$, $$$A$$$ has that part earlier than $$$B$$$, so $$$A$$$ will give a better result. Finally, about the parts $$$[9]$$$ and $$$[6]$$$, if we move $$$9$$$ back to the digit where $$$6$$$ resides, it will become $$$7$$$, so $$$A$$$ will give a better result, too. Therefore, taking $$$A$$$ is always advantageous for us overall.

    I think we can get a general proof out of this sketch, though it can be very tedious to do.

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

I have a question about how to arrive at the correct conclusion for a problem, for example, Problem B. That is, how to reach that solution—what was the clue in the problem that led to solving it in that way? I find it difficult to arrive at such a conclusion.

What I mean is, how should I study to improve this? Is it just about practicing problems, or does it require a more mathematical way of thinking? If anyone reads this, I would appreciate it if they could recommend a book or any resource. :(

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

    Well, when I first came up with this problem, I thought about what will happen, if I will aim to make all the elements = 0, then I found out, that we can transfuse all the values to the first and the second elements, so after that we need to transfuse from these two elements back to othe elements and also now aim to make them all equal. Maybe it was a little bit messy idea, but it helped to solve this one out

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

I am unable to understand the language of E and cant think of any approach i thought may be 3 loops as time is 2.5S but still dont understood minimum number of characters of C w.r.t to all strings we can make ? how can i know there can be many string can be formed. Anyone pls just point me in right direction. thanks

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

    I feel that his code is totally messy, and this code could help you understand that. 295017055

    A fact we know is that $$$\vert C \vert = \vert A \vert + \vert B \vert$$$, so for every character of $$$C$$$, you can know it must come from $$$A$$$ or $$$B$$$. Then we only need to use state $$$A$$$ and $$$B$$$ to calculate the answer.

    Let $$$dp[i][j]$$$ denote the minimum times of transforming with used first $$$i$$$ characters of $$$A$$$ and first $$$j$$$ characters of $$$B$$$. If $$$C[i + j]$$$ could be $$$A[i]$$$ or $$$B[j]$$$, we don't need to transform. Otherwise, raise $$$1$$$ by transforming a letter.

    So the main idea is to represent more states with fewer state measures. Hope this will help.

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

Who can help me why I had a WA2, problem E? https://mirror.codeforces.com/contest/2050/submission/295355937

→ Reply
  • »
    »
    11 days ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    why did you do dp[0][1] = 0;

    I think that means that a[0] = c[0] in your code which is not true.

    At the start we don't know what to choose so " i " needs to start from 0 and in each cell we need to choose between c[i+j] = a[i] and c[i+j] = b[j].

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

For problem D, I used insert() and erase() functions to modify the string and it gave me TLE on testcase 7, later, I changed my solution to keep track of what characters from the original string are moved to their left using an array and kept adding such characters to an empty string. I think my current solution is O(n) but it got a TLE on testcase 8. Can someone tell why I got TLE? Submission link

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

    You have to stop checking next element if current element checked is 9 as it would be max value possible

    like you did for mp[i]==1 continue

    Also you don't need vector it can be done by manipulating string taken as an input only

    My Code

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

    We can use __gnu_cxx::rope<char> instead of std::string and it passes: 295422598. Rope is a non-standart string implementation based on the treap with implicit keys. For std::string, insert() and erase() work in $$$O(n)$$$ in the worst case, where $$$n$$$ is a length of string. For __gnu_cxx::rope<char>, insert() and erase() work in $$$O(\log n)$$$ in the worst case, where $$$n$$$ is a length of string.

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

Can I please get some help in G? Wrong answer on test 2 — 295368314

My approach:

Navigate all the possible paths from the root node (0) to all the leaf nodes using DFS. For each such path, store the values of their degrees in an array $$$a$$$. If we consider some subarray [L, R] of $$$a$$$ (basically, a path) and remove all the nodes in this subarray then the number of components = $$$(\sum_{i=L}^R a_i) - 2 \cdot (R - L)$$$

The above equation can be rewritten in terms of prefix sum as:

$$$p[r + 1] - p[l] - 2 \cdot (r - l)$$$
$$$p[r + 1] - p[l] - 2 \cdot (r + 1) + 2l + 2$$$
$$$(p[r + 1] - 2 \cdot (r + 1)) - (p[l] - 2l) + 2$$$

Compute the array p using the equation above. Iterate from the left, maintain a current minimum variable, compute the value for $$$R + 1 = i$$$ and update result. The final answer will be maximum of such results in all possible paths from root node to leaf node.

Note: I am computing the prefix sum array in a different way. To get the sum of subarray [L, R] I would have to query $$$p[R + 1] - p[L]$$$

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

For C, will not be time complexity O(x*x) in the worst-case scenario where x is the length of the number? When the count of both 2s and 3s becomes equal to x/2. How is it getting accepted for a constraint of 10^5 on number length?

Can anyone clarify?

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

    You don't have to consider nine or more $$$2$$$s or $$$3$$$s because the effect of those digits loop after the ninth one (because we calculate numbers modulo $$$9$$$). So you only need to consider $$$9^2 = 81$$$ cases at most.

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

      Thanks a lot that clarifies my doubt.

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

      I understood this approach, but I have tried another approach as well. Please look into it-

      Here is the approach used in the else part of the code-

      1. As I have count for both 2s and 3s, I will use these 2s and 3s to adjust the sum to check whether it becomes divisible by 9 at any point.

      2. A single 2 will contribute 2 and a single 3 will contribute 6 to the initial sum.

      3. So, I am basically starting from the minimum sum we can form using these available 2s and 3s. ~~~~~

      void solve() {

      string n;
cin>>n;

ll sum=0, twos=0, threes=0;
for0(i,n.size()){
    sum+=(n[i]-'0');

    if(n[i] == '2') twos++;
    if(n[i] == '3') threes++;
}

if(sum%9==0) {
    cout<<"YES"<<endl;
} else {
    ll count = twos*2 + threes*6;

    for(ll curr=2;curr<=count;curr+=2) {
        ll rem = sum+curr;

        if(rem%9!=0) continue;

        if(threes>0) {
            ll req = curr/6LL;
            curr -= (min(threes, req)*6LL);
        }

        ll twos_req = curr/2LL;
        if(twos_req<=twos) {
            cout<<"YES"<<endl;
            return;
        }
    }

    cout<<"NO"<<endl;
}

      } ~~~~~

      It is giving me TLE. Can you please check this? Your insights will be helpful.

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

Task G solution 295409653

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

Could you guys help me with question G? I got the wrong answer for test case 17. https://mirror.codeforces.com/contest/2050/submission/295318789

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

2050C — Uninteresting Number he said" We can choose how many of the available digits 2and 3we will transform. Transforming more than 8 twos and more than 8 threes is pointless because remainders modulo 9 their transformation adds to the sum will repeat." in fact Transforming more than 8 twos and more than 3 threes is pointless
because 3*3=9,than their transformation adds to the sum will repeat.

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

Can anyone please tell me the recursive approach of solving problem E, as directly telling the dp approach doesn't takes the intuition under consideration and writing correct recurrence relation makes it very easy to optimise from memoisation to space optimisation.

Below is my incorrect and complex solution with too much of if and else condition.

Idea: Take three pointers i,j,k pointing to a,b,c respectively, if a[i] matches c[k] then increment i and k, if b[i] matches with c[k] then increment j and k, if none of them matches with c[k] then check by incrementing i first then k and vice versa and then increment j and k and viceversa 

int recur(string &a, string &b, string &c, int i,int j, int k) {
    if(k >= c.length()) return maxm(0,a.length()-i,b.length()-j);
    if(i >= a.length() && j >= b.length()) return c.length() - k;
    if (i < a.length() && a[i] == c[k]) {
        return recur(a,b,c,i+1,j,k+1);
    } else if (j < b.length() && b[j] == c[k]) {
        return recur(a,b,c,i,j+1,k+1);
    } else if(i < a.length() && j < b.length()) {
        return 1+min(recur(a,b,c,i+1,j,k+1), recur(a,b,c,i,j+1,k+1));
    } else if(i < a.length()) {
        return min(recur(a,b,c,i+1,j,k), 1+recur(a,b,c,i,j,k+1));
    } else if(j < b.length()) {
        return min(recur(a,b,c,i,j+1,k), 1+recur(a,b,c,i,j,k+1));
    } else return 0;
}
int main() {
	// your code goes here
    int t;
    cin>>t;
    while(t--) {
        string a, b, c;
        cin>>a>>b>>c;
        cout<<recur(a, b, c, 0, 0, 0)<<endl;
    }
}
→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're mistake is assuming that you take the one that matches c[k].You can take the one that doesn't match too.

    Also what if both match c[k] you need to check both cases but you are only taking from " a " in your code

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

Hi, I have a doubt in a different approach of problem G (may be wrong)

This approach involves getting the diameter, removing the vertices along the diameter and then calculating the number of component (nc)

The final answer will be nc+2.

I wan't to know if it is a right approach and if it is possible to implement it in the time limit.

Thanks

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

    i have a counter testcase image

    your algorithm will return 1 component but the answer is 6 by removing the path from 1 to 5

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

template contest.

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

In C, I am getting error in test case 3 in 401th case which is 9223372036854775807. It is showing that expected "NO" but got "YES" instead. But this number can be converted to 9's multiple if one of the 2 is changed. Can someone pls explain ?

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

nvm

→ Reply
»
5 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem C: The only extra piece of proof that I wish should be added is that, after calculating the num2s and num3s in the string. We can loop at most 9 times for each of twos, threes. As anything after this would be rudimentary as it would be divisible by 9 directly, so the loop should run from i = [1 to min(num2, 10LL)), j = [1 to min(num3, 10LL)). As, someone might think why running loop (num2*num3) times per test case doesn't add up to TLE, this is cause we would be checking for atmost 81 different states, which is of constant time complexity, and breaking out after it.

Hence, This works!
→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone hack me please Problem G 296473359

I Solved It greedly by picking node lca(a,b) which called root which have max number of edges

After that I Picked greedly node a which the node that have max number of connected components with lca(a,b)

After that I pick node b which have max number of connected components with node b

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

    That's also one of the correct solutions. In the editorial it is said, that this problem is kinda similar to finding the diameter of the tree, so your solution is just another way to find a diameter.

    → Reply