Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

PikMike's blog

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

1082A - Vasya and Book

Tutorial
Solution (Ajosteen)

1082B - Vova and Trophies

Tutorial
Solution (Ajosteen)

1082C - Multi-Subject Competition

Tutorial
Solution (adedalic)

1082D - Maximum Diameter Graph

Tutorial
Solution (PikMike)

1082E - Increasing Frequency

Tutorial
Solution (adedalic)

1082F - Speed Dial

Tutorial
Solution (PikMike)

1082G - Petya and Graph

Tutorial
Solution (Ajosteen)
 
 
 
 
  • Vote: I like it  
  • +55
  • Vote: I do not like it  

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

python 6-lines AC solution to problem B

_, string = raw_input(), raw_input()
start, end, res = 0, 0, 0
for char in string:
    if char == "G": start += 1
    else: end, start = start, 0
    res = max(res, start + end + 1)
print min(res, string.count("G"))

https://codeforces.com/blog/entry/60059 for more

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

How to solve E

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

For problem E, I came up with an elegant (at least I thought during contest) O(nlogn) divide-and-conquer solution. I am just surprised to see the so easy linear solution after contest...

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

In problem D, why do we have to loop from the end of the array at the end of algorithm?

I tried forward loop but gives WA on test 18... it seems that it doesn't construct tree well.

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

    +1. having the same issue

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

    So I just thought about it. The reason why the for loop needs to be done in reverse is because there is a chance that the very last node in the bamboo tree needs a "one" node to satisfy the diameter requirement that was previously calculated.

    Consider this test case

    5
    1 3 2 2 1
    

    If you have both the bamboo construction for loop and the "ones add-on" for loop both go forwards, we'll add both one nodes to vertex 2 and never get the chance to append a one node to vertex 4 -- this would be required to make the diameter of the constructed graph 4, which would be the max.

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

      Now I got it, for the construction of the bamboo we go forward and but then we must go backward to use all the remaining edges.

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

Hello friends,

Here is my solution to problem E. The pedagogy is quite different from the one in the editorial and it might be helpful. :)

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

My problem E solution is super simple.

It might me helpful for you.

https://codeforces.com/contest/1082/submission/46421135

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

    Can you explain it?

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

      In one word, It is like a parallel two pointer for every number.

      For every 'i', you need to change left of some numbers that count(left, i, X) < count(left, i, C), to 'i'. But you don't need to immediately calculate it for every number. Because count(i, i, vec[i]) is always 1.

      Sorry for my bad English.

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

        No issues with your english but I couldn't get you

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

        Neighter do I. And it's really simple.

      • »
        »
        »
        »
        9 hours ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Especially this part. Can elaborate more?

        Because count(i, i, vec[i]) is always 1.
        
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain why we need this line in problem B, res = min(res, cntG); Thanks.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int nres = 1;
    

    we considered 'S' as 'G' to combine 'G' in the two sides, trying to get the longest subsegment.

    For examble:

    input

    4 SGGG

    Before res = min(res, cntG);, res = 4. It's an wrong answer.

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

Update :- Got it :)

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

In the first case, Vasya can go directly to the y page from the x page if |x−y| is divided by d.

In the second case, Vasya can get to page y through page 1, if y−1 is divided by d. The required number of actions will be equal to ⌈x−1d⌉+y−1d.

Similarly, in the third case, Vasya can go to the page y through the page n if n−y is divided by d. The required number of actions will be equal to ⌈n−xd⌉+n−yd.

Why this? Please anyone explain.

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

In problem D, I was wrong in test 18. The vecdict is "Given diameter is incorrect 388 389", but in my output the diameter is 389? Anyone tell me why? Thanks so muck

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

    The checker checks the diameter of your graph using your adjacency list, not just the diameter your output after "YES".

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is my idea of E:

We have a naive solution: consider each segment [l, r], get the maximum appearance of a number in the segment, assume it is x, then update result with cnt(1, l - 1, c) + x + cnt(r + 1, n, c), where cnt(l, r, j) is number of apperance of j in segment [l, r].

In the solution above, for each segment [l, r], we choose the number with highest appearance and then change to c. But in fact, we can greedy change all the elements equal ar in segment [l, r]. Proof: If we choose the number with highest appearance, assume it is y, and y ≠ ar, then we can get better result if we choose segment [l, r'], where r' < r, cnt(r' + 1, r, y) = 0, y = ar', because cnt(r' + 1, n, c) ≥ cnt(r + 1, n, c) and cnt(l, r', y) = cnt(l, r, y), so cnt(1, l - 1, c) + cnt(l, r, y) + cnt(r + 1, n, c) ≤ cnt(1, l - 1, c) + cnt(l, r', y) + cnt(r + 1, n, c).

So at the position i, let fai be the most number of c in segment [1, i] if you change all the elements equal ai to c in some segment [l, i]. Then: fai = max(fai + 1, cnt(1, i - 1, c) + 1). We update result with fai + cnt(i + 1, n, c).

My submission: 46365450

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

    I like this one. GJ

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

    You saved my day

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

    I understand that all a[i] in (l,r) can change to a[r] but : why calculate cnt( 1,i ,d ) only not cnt(1,l-1,c) and cnt(l,r,d)

    sorry for my poor English....

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

      At position i, fai is the maximum c we can get if we change all number equal ai in some segment [l,  i] to c. That means there is a segment [l,  i] which the sum cnt(1,  l  -  1,  c)  +  cnt(l,  i,  ai) is maximum and we suppose this sum equal fai. So we update result with cnt(1,  l  -  1,  c)  +  cnt(l,  i,  ai)  +  cnt(i  +  1,  n,  c)  =  fai  +  cnt(i  +  1,  n,  c).

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

    What a wonderful solution!!!!

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

    Why you can prove that it's optimal to change the elements equal ar in [l, r]? The proof seems to have only proved that changing ar' is better than changing ar. Could you please explain it in more detail?

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

      I mean that changing all numbers equal ar' = y to c in segment [l, r'] is better than changing all number equals y (which have the most apperance) in segment [l, r].

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

i used binary search for problem B

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

Can anybody tell me why my code for problem C is giving WA?

The link to my code : https://codeforces.com/contest/1082/submission/46672149

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

Someone please help me with problem C. I couldn't understand the problem.

»
5 days ago, # |
  Vote: I like it -6 Vote: I do not like it

What is the time complexity of problem C?