PikMike's blog

By PikMike, history, 2 weeks ago, translation, In English,

1217A - Creating a Character

Tutorial
Solution (adedalic)

1217B - Zmei Gorynich

Idea: Roms

Tutorial
Solution (Roms)

1217C - The Number Of Good Substrings

Idea: Roms

Tutorial
Solution (Roms)

1217D - Coloring Edges

Idea: BledDest

Tutorial
Solution (Roms)

1217E - Sum Queries?

Idea: BledDest

Tutorial
Solution (PikMike)

1217F - Forced Online Queries Problem

Idea: BledDest

Tutorial
Solution (PikMike)
 
 
 
 
  • Vote: I like it
  • +99
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Thank you very much for the round!

In E, it's said:

The problem now got reduced to: find a pair of numbers $$$a_i$$$ and $$$a_j$$$ such that $$$l$$$ $$$<=$$$ $$$i$$$ $$$<=$$$ $$$j$$$ $$$<=$$$ $$$r$$$, there is at least one position such that both $$$a_i$$$ and $$$a_j$$$ have non-zero digits on it and $$$a_i$$$ $$$+$$$ $$$a_j$$$ is minimal possible.

Shouldn't $$$i$$$ and $$$j$$$ imply $$$i$$$ $$$!=$$$ $$$j$$$?

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

why is the bound from problem D so low? the solution should be in $$$O(n)$$$?

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

    i'm not sure, but the checker may have a higher asymptotic time complexity, $$$O(n^2)$$$, for example

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

      the checker will create a graph with edges of a single color (at most two graphs) and do a toposort on each of them to detect cycles. Therefore the checker is in $$$O(n+m)$$$ and can also handle much larger inputs

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

    I think in general when you're setting problems, you should strive to exclude all the naive solutions, but let certain solutions pass. However, if possible, you should try not to give away desired complexity with the bounds, because that makes the problem easier. Usually, this second part is not possible because CF has a lot of problems where O(n^2) is naive and O(n) or O(n log n) is optimal, so any MAXN less than 10^5 will let O(n^2) solutions pass.

    However, here, the naive solutions are in the exponential range, and there aren't really any "bad" quadratic solutions, so I think it's okay to leave the bounds there so that it doesn't give anything away about the solution.

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

      well the idea may sound good but by setting the limit like this you risk that weird stuff gets AC... for example those:

      randomized (which seems to be correct even without randomisation the author just did not realized that it would always work...): 60128957

      slow solutions in $$$O(n^2)$$$: 60121420 60123728

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

        IMO, this problem $$$O(n^2)$$$ solution isn't really bad. Checking cycles in $$$O(n)$$$ is important, but that's not the main idea and it leaves more freedom to slow languages and implementations.

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

here is written if r-l>18 then f(l,r)>2*10^5.and why? example: 00000000000000000000000000001. it's obvious that that binary number is 1.

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

    also here is written — "lets iterate over the right boundary of substring and high 1-bit position (denote it as r and l respectively)", which means that we consider only the cases when a[l] == '1'

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

      Can you share more questions like this?

      Use of nxt array was something extraordinary... is it a general technique like building prefix sum array?

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

    if f(l,r) > 2*10^5 then the binary number can't fit in the string

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

      i still couldn't understand why, when the string can store any length of the binary number

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

While solving A by fixing the condition on minAddI, I get WA.

minAddI = ceil((str+exp-int-1)/2)
ans = max(0, max(minAddI+1))

What's the mistake here? Can't we look at the various ways of points to be added for Intelligence?

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

can somebody explain me problem c? you can write short answer, but bigger is better :D

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    My solution is like this: Iterate through the string (i), then if encounter a '1', start another loop from the i position (j), this time calculating the decimal expansion of binary from i to j, then checking if number of previous consecutive zeros + (j — i + 1) is larger than or equal to the decimal expansion (cuz the length is equal to the decimal expansion).

    for example,

    s = 00001010
    
    1. iterate until encounter 1
    
        00001010
            ^
    2. iterate until not enough zeros behind the 1
    
        number of previous consecutive zeros = 4
        00001010
            ^
        4 + 1 >= 1 (binary "1")
    
        00001010
            ^^
        4 + 2 >= 2 (binary "10")
    
        00001010
            ^ ^
        4 + 3 >= 5 (binary "101")
    
        00001010
            ^  ^
        4 + 3 not>= 10 (binary "1010")
    
        so break and iterate i again
    
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, but i get idea after 5 minutes of that comment, thanks anyways.

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

      Thanks a lot much clearer and simpler solution!!!

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

      What will be the time complexity ?

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

      Hello, could you elaborate more on why do I have to keep track of consecutive zeroes? and why comparison between consecutive zeros + (j — i + 1) is larger than or equal to the decimal expansion is made? Thank you

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

        consied the case for s = 0110. here the count of zeros preceeding the 1 is 1. so when you start the j loop the first value you get "11" is 3. the lenght of this string is 2 and the decimal value for 11 is three and hence doesnt satisfy the questions "f(011)=3,f(00101)=5,f(00001)=1,f(10)=2,f(000)=0 and f(000100)=4.". However, If we were to include one of zeroes we encountered before find '1' in string at i = 1, the newly formed string would become 011 which in length of size 3 and the decimal value of this is also 3, thus a goodstring. we continue by increasing the j counter and encounter string 110 which has length = 3 but a decimal value = 6, so for this string to become a good string we obviously need "110" but we also need three zeroes "000" preceeding the string "110", but since we already know the count of preceeding zeroes, ie 1, we know we cant find any bigger number in the given seeuqnce so we can just break and look for the next "1" in loop i;

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      wow so op

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

      I have written the same algorithm still I am getting wrong answer on one test case. Can you please check it?


      include<bits/stdc++.h> using namespace std; define ll long long int main() { ll t; cin >> t; while(t--) { string s; cin >> s; ll len = s.length(); ll count = 0; ll prevZero = 0; for(ll l=0;l<len;l++) { if(s[l]=='0') { prevZero++; continue; } ll num = 1; count++; for(ll r=l+1;r<len;r++) { num *= 2; num += (s[r] == '0') ? 0LL : 1LL; int right = (r-l+1); if(right+prevZero>=num && num>=right) { count++; continue; } else { prevZero = 0; break; } } } cout << count << endl; } }
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think it should be (right + prevZero >= num)

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

          yes, thank you. But still, it is giving wrong answer on test case:2.

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

Can somebody explain B? How does the formula come? I think sorting on the basis of difference is enough. After sorting we just have to see the first element, isn't?

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

    if max damage >= head, you only need 1 hit if it's not and max ratio pair of damage and regen <= 0, you wont be able to win

    lastly, you know you need to deal x times max ratio pair of damage and regen + 1 times using max damage to finish, so the answer will be x + 1 ( 1 times using max damage).

    • (x * ratio) + max damage >= head
    • x >= (head — max damage) / ratio
    • remembers, x can be floating number here, and we need to round it up
    • so, you can add 1 to x if (head — max damage) % ratio > 0
    • or you add the divisor — 1
    • x >= (head — max damage + ratio — 1) / ratio
    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Then why did you write "x >= ((head — max damage + ratio — 1) / ratio)+1"(adding an extra one) in your code
      instead of x >= (head — max damage + ratio — 1) / ratio

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

      Why did you delete your reply lol But it helped me clarify the doubt nonetheless. So, Thankyou!

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Thnx man you helped me clarify my doubt.

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

Can anybody explain problem-C .I am not able to understand the problem.

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

Another way to color edges in problem D. Neither simpler nor harder but just another XD.

Let's iterate over all vertices and color all "$$$in$$$" edges in color $$$1$$$ and "$$$out$$$" edges in color $$$2$$$. For every cycle, there will be the vertex which was considered last in it (let's call it $$$u$$$). It implies that color from the previous vertex in the cycle to $$$u$$$ and color from $$$u$$$ to the next vertex in the cycle are different.

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

Does anyone know how to solve F in LCT implementation?

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

can you explain c? such algorithm does not support substrings like 00000000000001, because there hightest position is 13 and lowest 0, i don't understand please explain to me

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

I have a doubt in E, in the proof that an unbalanced set can never be made balanced again. Where are you using the assumption that $$$a\subset b$$$ ?.

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

    We've made some set unbalanced by having two numbers with non-zero digits at some position — that's the set $$$a$$$. So now we can always find such a position in the set $$$b$$$.

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

      could you please elaborate about "implementing multiple segtrees" ? i dont get it

      edit: i mean, we build 10 segment tree bcs the max value is 10^9, but i dont know how to get the answer from this segment trees

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

For B, I am giving you a simple hint without confusing you. Just try to find the maximum damage in the query(d) and the maximum difference(d-h) in all query. If you find the maximum difference is below zero, you are never going to make it. so output zero.After you once decrease the number of heads of the monster using maximum damage and after you can continuously use the maximum difference to decrease number of heads to make the number of heads below or equal to zero. Output the number of blow where you will make his head equal to or below zero.

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

Another easier approach to problem D:

Suppose a graph $$$ G = (V, E) $$$. Partition $$$ E $$$ to one group contains $$$ in > out $$$ only, and one group contain $$$ out > in $$$ only. Clearly no cycle in two sets. So the maximum number of colour is 2. One can just check if 1 colour is OK.

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

    Can you explain your solution in detail? Thanks.

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

      The lower bound is trivially 1.

      Construction of the upper bound:

      Consider two sets

      $$$ \{ (i, j) : 1 \leq i < j \leq |V| \} \bigcap E $$$

      and

      $$$ \{ (i, j) : 1 \leq j < i \leq |V| \} \bigcap E $$$

      Note that they are disjoint and their union is $$$E$$$. Also note that no cycle exist in both two sets. So there always exist one valid coloring method when number of colour is 2, i.e. the upper bound of the answer is 2.

      Check if answer is 1 by cycle detection.

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

    thank u very much............

    u saved my time ....

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

    Hey. Can you please tell me why two coloring the edges when the graph has cycle doesn't work? Here's my code: https://codeforces.com/contest/1217/submission/60264580

»
2 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Can someone explain me why my code to F with block = 500 gets AC, but with block = sqrt(n) + 10 gets WA? https://codeforces.com/contest/1217/submission/60218374, https://codeforces.com/contest/1217/submission/60218188.

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

.

»
2 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

You missed a trivial solution to D: If there's a cycle, paint each edge $$$(u,v)$$$ such that $$$u>v$$$ black and all others white.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I got TLE in E,my solution is only O((n+m)⋅logn⋅log10MAXN).link

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one explain why 2addS>exp+int−str goes to 2addS≥exp+int−str+1

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

    In simple x>3 means x starts from 4 and goes to infinity. Also, x>=4 has the same meaning. So x>3 is the same as x>=3+1.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C why we are doing precalculation of nxt array?? can someone elaborate this?

  • »
    »
    11 days ago, # ^ |
    Rev. 12   Vote: I like it 0 Vote: I do not like it

    I'm not sure I understand the editorial solution either, but I coded up a simple brute-force / two pointer solution with a pruning heuristic: 60334519

    To summarize, we iterate through the string from left to right. If $$$s[i] = 0$$$, we increment a $$$len$$$ accumulator and move on. If $$$s[i] = 1$$$, we start a secondary loop, where we keep track of the potential values of $$$f(z,j)$$$ (where $$$z$$$ is an imaginary pointer $$$\leq i$$$ that includes the "streak" of $$$0$$$s just before this $$$1$$$ if it exists). $$$ans$$$ is incremented whenever $$$f(z,j) \leq len(z,j)$$$ since it means we have found a good substring (you can "cut" a substring of the right length), but as soon as $$$f(z,j) > len(z,j)$$$ no more good substrings can be found from this position as $$$f$$$ grows faster than $$$len$$$, so we cut off the search and reset $$$len$$$ before moving on. Since the inner loop will never iterate more than $$$\lfloor \log_2 n \rfloor + 1$$$ times before being cut off, the algorithm runs in $$$O(n \log n)$$$ time.

    Edit: Actually it might be in $$$O(n)$$$ time, because an adversarial input can only force more inner loop iterations by including zeros before the one, but zeros don't trigger the inner loop, and increasing the number of zeros has rapidly diminishing returns

    Edit 2: Just noticed that toshinaritong explained a similar solution

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

      Can you please elaborate how can we cut a substring of right length if f(z,j)<=len(z,j)

      • »
        »
        »
        »
        9 days ago, # ^ |
        Rev. 10   Vote: I like it 0 Vote: I do not like it

        $$$f(z,j) \leq len(z,j) \Rightarrow \exists! x : z \leq x \leq i \land f(x,j) = len(x,j)$$$, i.e. substring $$$x..j$$$ is "good".

        In less formal terms, the indices between $$$z$$$ and $$$i$$$ indicate the "pool" of zeros we can use to manipulate the length of the substring; as long as $$$f(z,j) \leq len(z,j)$$$ we can always choose to include the exact number of zeros required for the substring to be good. When $$$f(z,j) > len(z,j)$$$, we don't have enough zeros, so we break the inner loop and move on.

        Or in more concrete terms, take the example $$$s = 00001010$$$

        When $$$i = 5$$$ (one-indexed), $$$z = 1$$$. Since $$$s_5 = 1$$$, we start the inner loop.

        When $$$j = 5$$$, $$$f(z, j) = 1 \leq len(z, j) = 5$$$. Pick $$$x = 5$$$. Note that substring $$$5..5$$$ is good cause $$$f(5, 5) = 1 = len(5, 5)$$$

        When $$$j = 6$$$, $$$f(z, j) = 2 \leq len(z, j) = 6$$$. Pick $$$x = 5$$$. Note that substring $$$5..6$$$ is good cause $$$f(5, 6) = 2 = len(5, 6)$$$

        When $$$j = 7$$$, $$$f(z, j) = 5 \leq len(z, j) = 7$$$. Pick $$$x = 3$$$. Note that substring $$$3..7$$$ is good cause $$$f(3, 7) = 5 = len(3, 7)$$$

        When $$$j = 8$$$, $$$f(z, j) = 10 > len(z, j) = 8$$$, so we break the loop and continue iterating $$$i$$$.

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

Can anyone help me understanding the Tutorial for Coloring Edges with an example. I am having trouble getting the logic they are using. Please help. It would really be appreciated!

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

Problem E. While updating, why don't we consider the case when a[pos] was the minimal number with non-zero j-th digit in the interval [l,r), and x > a[pos]?

For instance we have the array [1,2] and we're getting the update query with pos = 1, x = 5. When updating, t[v] for [1,2), min_digit[0] still will be 1, but it should be 5.

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

Can someone please help in problem D.

I am using the concept of back-edge only, If I found a back edge, color it with '2', else 1.

My solution: https://codeforces.com/contest/1217/submission/60415966 Its based on this article: https://cp-algorithms.com/graph/bridge-searching.html

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

    The article you are referring to is for undirected graphs, not directed ones.

    DFS on digraphs induces more types of edges, you can read it here.

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

There's something weird with problem F. I got accepted with 748ms by setting P=5*10^4. If I use P=sqrt(m), my submission receives TLE verdict. What is going on?

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

Can anyone explain to me why there is 1 added in the inequalities equation

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

can anyone explain the formula written in B question editorial how it came?

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

Hi, i'm really new to programming and I can't understand the first problem solution. Can anyone tell me how to do it using c++? Edit: nvm. found a way to do it myself