ExplodingFreeze's blog

By ExplodingFreeze, 8 months ago, In English

Thank you for participating! We hope you enjoyed the contest.

1605A - A.M. Deviation

Authored and prepared by JeevanJyot

Hint 1
Hint 2
Hint 3
Solution
Solution [c++] (JeevanJyot)
Solution [Kotlin] (ExplodingFreeze)
Solution [Python] (AshishGup)

1605B - Reverse Sort

Authored by Ashishgup and prepared by JeevanJyot.

Hint 1
Hint 2
Solution
Solution [c++] (JeevanJyot)
Solution [Kotlin] (ExplodingFreeze)
Solution [Python] (AshishGup)

1605C - Dominant Character

Authored by Ashishgup and prepared by JeevanJyot.

Hint 1
Hint 2
Hint 3
Solution
Solution [c++] (AshishGup)
Solution [Kotlin] (ExplodingFreeze)

1605D - Treelabeling

Authored and prepared by the_hyp0cr1t3.

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Solution [c++] (the_hyp0cr1t3)
Solution [c++] (AshishGup)
Solution [Kotlin] (ExplodingFreeze)

1605E - Array Equalizer

Authored and prepared by JeevanJyot.

Hint 1
Hint 2
Hint 3
Solution
Solution [c++] (JeevanJyot)

1605F - PalindORme

Authored by ExplodingFreeze and antontrygubO_o and prepared by ExplodingFreeze.

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Solution [c++] (ExplodingFreeze)
Solution [c++] (antontrygubO_o)
Solution [Kotlin] (ExplodingFreeze)
 
 
 
 
  • Vote: I like it
  • +202
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by ExplodingFreeze (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

In order to solve problems like this problem C, can anyone suggest me anything ? I have solved a lot of 'C' of div2(from another acc 'The_mysterio') , doesn't feel like it helped in this problem. It is observation I understand but may be something else in also needed????

»
8 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Thanks for giving hints before the exact solution . It improves the thinking process .

»
8 months ago, # |
  Vote: I like it +18 Vote: I do not like it

For me, D was a really great problem.

I was able to find out Starting at any node should guarantee a win for her. And I can solve this by implementing bipartite concept. But could not implement in time :(

And yay, I won't be able to participate in Div 3 anymore. I am a blue now :)

»
8 months ago, # |
Rev. 3   Vote: I like it +116 Vote: I do not like it

Also my apologies for F being too tough for a Div2 round. While I expected it would be tougher than an average Div2F I didn't expect it to go unsolved during the round.

Additionally, congratulations to maspy for managing to solve it (135175668) shortly after system testing concluded, before the editorial was posted.

»
8 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Bitterly missed the 'traditional' questions today (DP, Seg-Tree based, Bin-Search, etc.) that would otherwise cushion the fall. Great contest though, ig.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the quick Editorial.

»
8 months ago, # |
  Vote: I like it +30 Vote: I do not like it

7 length substring!!!!!!!!!!

I will kill ya!!

»
8 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

i like editorial with hints

but not this one

for E

<<Assume the value of b1 to be some variable, say x>> or << solve for one query>> i think if i could solve for one query, i could solve the main problem

joking? do you think this helps? really fun man

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +54 Vote: I do not like it

    Just anecdotal evidence: I solved this task in the contest, and my first attempt solved the problem for 1 query (giving me $$$O(n \cdot q)$$$ complexity, which is not enough). Having implemented that, I was able to find the the optimisation needed afterwards. So I'd say, that one is a valid hint. :)

    I guess the problem with hints for E is, that it is a pretty technical task. Like, you use the linearity between input and output to do some linear algebra magic and then you have to work with cases with absolute values. Hard to pinpoint the thing to a "central idea".

    Edit: I think a two very good tips would've been:

    Solve this by going from left to right and changing each $$$a_i$$$ to $$$b_i$$$. Notice, later operations on $$$i$$$ don't change numbers on positions smaller $$$i$$$.

    Look at $$$a=(1,0,0,...)$$$ and $$$b=(0,0,0,...)$$$ and for each position $$$i$$$ count which operations were perfomed. Notice, that at each position either the first operation is performed exactly once, or the second operation is performed exactly once or no operation is performed.

»
8 months ago, # |
  Vote: I like it +55 Vote: I do not like it

In Problem A you can also get the same result, by noticing, that the sum $$$S=a_1+a_2+a_3$$$ is invariant under the operations. With $$$a_1+a_3=S-a_2$$$ we obtain $$$d(a_1,a_2,a_3)=a_1+a_3-2\cdot a_2=S-3\cdot a_2$$$. So it's enough to check $$$d(a_1,a_2,a_3)\mod3=S\mod3$$$.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you for great contest! B and C were amazing :)

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

really helpful hints for E :|

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    In this test your code gives 2 expect 3
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Try

    1
    2
    ba
    

    Should give $$$-1$$$, gives $$$2$$$. Your code "finds" and accepts the substring a as a valid string for check(2)

»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I lost 50 rating, but I thought the contest was really cool, and I'm really happy about the hint-based editorial :)

»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Super nice and enjoyable problems, I really liked problem D. The cool thing about this problem was how some observations could lead to a neat and easy to code solution, I really loved it.

hope to see more similar problems in the future. And thanks a lot for the round.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In case you guys prefer video solutions, here are the solutions to the first 4 problems: Solutions

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we do problem C using sliding window ?How?

»
8 months ago, # |
  Vote: I like it -52 Vote: I do not like it

include

include<math.h>

include

include

using namespace std; int min(int a,int b){if(a>b)return b; else return a;} void swap(long long int &a,long long int &b) { int temp=a; a=b; b=temp; } int main() { int t; cin>>t;

while(t--)
{
    int n;
    cin>>n;
    string s;
    cin>>s;

    int m=2e8;


    int i=0,j=0,a=0,b=0,c=0;
    for(int i=0;i<n;i++)
    {if(s[i]=='a' &&  s[i+1]=='a')
       {m=2;
       break;}
    }

    while(j<n)
    {
        if(s[j]=='a')
         {a++;
         j++;}
        else if(s[j]=='b')
         {b++;
         j++;}
        else
        {c++;
        j++;}



        if(j-i+1>2)
        {
            if(a>b && a>c)
             { 
                  m=min(m,(j-i));
            }
            else
            {  while(s[i]!='a')
                {
                 if(s[i]=='b')
                  {b--;}
                 else
                  {c--;}


                i++;
                }
               if(i>j)
               j=i; 





            } 


        }

    }
    if(m==2e8)
     cout<<-1<<endl;
    else 
    cout<<m<<endl;


} 

return 0;

}

why am i getting RUNTIME ERROR and on which testcase it is giving WA?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C: I know "the string must look like "a??a??a??a??a" " is correct instinctively. But I could not prove it. Can anyone give me a provement of why the smallest substring should never contain something like "a _ _ _ a"?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Because you have 3 spaces between the 2 a's

    If the 3 spaces does not contain any more $$$a$$$, then "one" of the following 2 conditions are always true -

    $$$count(a) = count(b)$$$
    $$$or$$$
    $$$ count(a) = count(c) $$$

    And we don't want that.

    And if it does contain at least one more a, then you can always form an answer with at most length=3 (And this will be a better answer)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    First of all a___a alone is not sufficient to a be a valid string because 3 elements in middle and atleast two would be same. so you need more characters to build a valid string. Now think of something like you could not make up a valid string here, so if a valid string were to exist, then you would have to make up for the fact you left spaces in between, and add some extra a's, then again as you are having two a's at a distance of atleast 4, so adding a's in this way...then the same problem comes. So to have those extra a's you would need to have those a's with dist < 4.Hope this helps. This was my logic behind it. But proving mathematically.. :((

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

$$$x\oplus y\nleq\min(x,y)$$$ for D is a typo right? $$$\nleq$$$ should be $$$\leq$$$

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think there is a typo: (Thus, if MSBx=MSBy then x⊕y≰min(x,y).), is not the xor will be always less than min(x,y). correct me if i am wrong.ExplodingFreeze

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are correct, it should be $$$\leq$$$, the typo will be fixed in a bit

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

LOL

Solved A using ternary search xD

»
8 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I've got a little confusion according to tutorial of problem E.

$$$ |cx + d| $$$ = $$$ cx + d $$$ exist when $$$ cx + d \geq 0 $$$

which is $$$ cx \geq -d $$$.

When $$$ c > 0 $$$, the range of x will be $$$ x \geq -\frac{d}{c} $$$

When $$$ c < 0 $$$, the range of x will be $$$ x \leq -\frac{d}{c} $$$

But in the tutorial, it says $$$ |cx + d| = cx + d $$$ $$$ x \geq -\frac{d}{c}$$$

Could anyone explain it to me?

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    JeevanJyot I think this might be a mistake in your tutorial. I see that you change $$$ |cx + d| $$$ into $$$ |-cx - d| $$$ if c is negative in your code, you should write it in your tutorial.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Apologies for that. I will correct that in a while.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me what is the meaning of this statement?

if a1+a3−2⋅a2≡2 mod3, then the minimum value of d(a1,a2,a3)=|2−3|=|−1|=1

like how tj=his is coming |2−3|=|−1|=1

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, how I thought about it is

    a1 + a3 — 2*a2 = k

    now if we add 1 to either a1 or a3 and subtract 1 from a2

    a1 + a3 + 1 — 2 * (a2 — 1) = a1 + a3 + 1 — 2 * a2 + 2 = k + 3

    Similarly when be subtract 1 from wither a1 or a3 and add 1 to a2

    a1 + a3 — 1 + 2*(a2 + 1) = a1 + a3 — 1 + 2*a2 — 2 = k — 3

    We can perform these operation any number of times so we can minimize our k

    So, if we are given some k and we can add or subtract 3 from it any number of times.

    If k mod 3 = 2 Then we can simply subtract three again to make it -1 Thus (2-3) ≡-1 ≡ 2 mod 3

    And we are taking absolute so min( |-1|, |2| ) = 1

    Might not be entirely correct, but worked for me

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      ahhhh got it got it thanks for the help and for the reply!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the hints,it can help a lot in solving such interesting problems.

"Programming is not just to write a code, it is to understand and proof your solution".

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

C->D(1400->2100) shouldn't there be a problem of 1700 in between(considering div2)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast edutorial and giving hints before the actual solution...it has helped me in thinking more

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Excuse me! But,I think that your solution of E has a mistake. Maybe your theory of sort is not right. Because "c" can be negative.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can change c into positive because $$$ |cx + d| $$$ = $$$ |-cx - d| $$$. Although he didn't write it in the tutorial, you can see it in his code

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,I get it. Thanks a lot!

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hello,wxy2005 I did not understood the concept of the problem E last lines of editorial This opening of |cx+d| thing .Like why we took into consideration the value of c because as it is a variable it can be positive or negative. Why the sign of c matters?Can you explain it fully ?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        The sign of c does not matters. The only thing that matters is the sign of $$$(cx + d)$$$ because what we want to know is $$$\sum |c_ix + d_i|$$$.

        We know that $$$|c_ix + d_i| = c_ix + d_i$$$ when $$$c_ix + d_i \geq 0$$$ are hold, and $$$|c_ix + d_i| = -c_ix -d_i $$$ when $$$c_ix + d_i < 0$$$ are hold.

        If $$$c_i$$$ is positive, the inequality $$$c_ix + d_i \geq 0$$$ holds when $$$x \geq -\frac{d_i}{c_i}$$$, but if $$$c_i$$$ is negative, it will holds when $$$x \leq -\frac{d_i}{c_i}$$$

        To avoid this, we found that $$$|c_ix + d_i| == |-c_ix - d_i|$$$, so we can change $$$|c_ix + d_i|$$$ into $$$|-c_ix - d_i|$$$ if $$$c_i$$$ is negative.

        After doing this, we can sort all $$$c_i, d_i$$$ in the order of $$$\frac{d_i}{c_i}$$$. After doing this, we can used binary search to find a position that for all $$$c_i, d_i$$$ before it $$$c_ix + d_i \geq 0$$$ and for all $$$c_i, d_i$$$ after it $$$c_ix + d_i < 0$$$

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, |cx+d| = opening of this modulus operator as c can be negative then you told the new condition of x above in the comments. So , basically the range of x in the editorial where binary search is applied.So what exactly range of x binary search is applied upon? wxy2005

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Now, i understood.You devoted your time to my question and replied it. Heartily thanks to you bro. wxy2005

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

JeevanJyot can you please explain " \n"[i+1 == ans.size()]?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Basically i+1 == ans.size() will be false (i.e. $$$0$$$) for all values of $$$i$$$ except its last value. So it will print the $$$0$$$-th character of the string " \n" which is ' '.

    For the last $$$i$$$, the condition will be true (i.e. $$$1$$$). So it will print the $$$1$$$-st character of that string which is '\n'.

    In a nutshell, it's just a one-liner way of printing some space-separated integers with a '\n' in the end.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the amazing contest! There´s a typo in the editorial of problem E, it says "B4−2" and it should be "B4-b2".

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Which approach is better for practicing problems in problemset: topic-wise or difficulty-wise?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Time Limit is too strict for C. I used a map to keep a count on the frequency of a, b and c and it resulted in TLE :(

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Regarding problem C, I found 13 minimal length substring "abbabbaccacca" which satisfies the properties mentioned in the problem.

But in the tutorial it is said that there can be atmost 7 length substring which can satisfy the property.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If you take characters [3, 9] of this string of length 13 you end up with “abbacca”, which is a string of length 7 satisfying the properties.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E with complexity $$$O(nlogn+q+2*A_{max})$$$ breaking the sum of $$$|c*x+d|$$$ into the difference between $$$|c*x+d|-|c*(x-1)+d|$$$ and using two prefix arrays but I really liked the editorial approach as it doesn't depend the value of $$$A_{max}$$$. :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem c : what is wrong in my code?

https://codeforces.com/contest/1605/submission/135505427

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really like the problem F and thank you for the hints! ^ω^

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We can assign all integers from 1 to n having the i-th bit as MSB to a white node if the i-th bit is set in w, and assign all the remaining integers to black nodes.

I am not able to prove that no matter what the value of n, we can use w to assign nodes to white or black.

I understand it works, but I am not able to get how it works? Any hints :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve problem D (Treelabeling) via centroid decomposition?

Motivation on why I believe it is possible: when you divide the tree into at least 2 components and label the centroid with number whose MSB is k, then you can label the centroids of the remaining components with some numbers whose MSB is greater than k.

What have I tried: let's call the depth of centroid as the depth of the recursion when we found it (for example first centroid has depth 0, centroids of the remaining components have depth 1, after that decomposition centroids of those remaining components have depth 2, and so on...). Let's keep nodes in lists according to their depth sorted by the number of nodes in their components (when they become centroid). In the k-th list, we will pick first 2^k nodes and label them with numbers with MSB k. If there are more than 2^k such nodes, the rest we shall move to tier (list) k+1. Unfortunately this doesn't work, but I can't find the counter example :(

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

can anyone help to understand problem C's hint 3 ? Why not the substring is more than 7 lengths?

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

yayayay I upsolved F with no hints after 3 days, fantastic problem!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C:Why is 'acab' not a solution? In example 3, I think 4 is completely feasible.

_<

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

Under problem D, its written that MSBw < MSBn

But this looks wrong. MSBw can be equal to MSBn (eg MSBw = 4, MSBn = 4 where n = 6 and white nodes are 4). This actually caused problem for me to think where to ideally place fragmented last disjoint set of n. For example if n is 1, 3, 7, or 15, it has perfect disjoint sets of sizes 1, 2, 4, 8 etc. But if n is equal to say 6 then the disjoint sets will be 1, 2, 3 where set of size 3 is not full and will cause problem.

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

    In the line just before $$$MSB_w \lt MSB_n$$$, it is mentioned that "WLOG let $$$w \leq b$$$ (we can swap the colours otherwise)" where WLOG is a common abbreviation of without loss of generality.

    We are basically saying that since white and black nodes are just arbitrary labels, lets assume $$$w \leq b$$$ and prove that case. If this does not hold, we can just use the same proof after swapping their labelling (black <---> white).