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

PikMike's blog

By PikMike, history, 2 months ago, In English,

1065A - Vasya and Chocolate

Tutorial
Solution (Ajosteen)

1065B - Vasya and Isolated Vertices

Tutorial
Solution (Ajosteen)

1065C - Make It Equal

Tutorial
Solution (Ajosteen)

1065D - Three Pieces

Tutorial
Solution (PikMike)

1065E - Side Transmutations

Tutorial
Solution (PikMike)

1065F - Up and Down the Tree

Tutorial
Solution (adedalic)

1065G - Fibonacci Suffix

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

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

44220948

Why does my D WA on test 25? I had a similar solution, except I bruteforced the shortestdistance instead of using bds/djikstras, and used a bunch of selections for the dp instead of a pair.

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

    You probably didnt consider that in the optimal solution you need to change the chess piece on the way between position a and b and not only change pieces on position a or b?

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

      but a rook can always reach your desired position in 2 moves, so even if you switch to a rook at the beginning your total cost will be 3

      Now if you're using a bishop and move to a position which isn't your destination, and switch to another counter and then move to your desired position, your total cost would still be 3

      The same goes for switching between other counters. Your maximum cost will always be 3 (which is the same as switching to a rook at the beginning and then reaching your desired position)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        4
        14	10	3	7
        4	15	11	13
        12	1	16	9
        2	5	6	8
        

        Consider, when you are in number 2 with a bishop.

        • You can go to number 3 with a rook in 3 steps: replace bishop with rook, goto 14, goto number 3.

        • You can go to number 3 with a knight in 3 steps: go back to 1 with bishop, replace bishop with knight, goto number 3. (Note that, you cannot replace bishop with knight in number 2 because, in that case, you need 4 steps to go to number 3)

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

O((N + M) * M) or O(M * (M + log(N))) solution for G:

Same solution but changing 1 part, the part of counting the number of occurences. Instead of using an automaton, keep pref[i] ans suf[i] as the M first characters of the prefix/suffix of the i-th string. Using this, freq[i] = freq[i-2] + freq[i-1] + occurences that use the suf[i-2] + pref[i-1]. This gives us an O(N * M^2) solution like in the editorial. But you can note that starting from one point (the position where |F[i]| >= M), pref[i] == pref[i + 2] and suf[i] == suf[i + 1]. This means that the "occurences that use the suf[i-2] + pref[i-1]" will actually repeat with period 2. So you can calculate it in one phase until that point, the cost of this is O(F[0] + F[1] + F[2] + ... + F[i]) = O(F[i + 1]) = O(M) and from that point on, you can reuse the number of occurences that happened in the previous calculations (or do 4 more just to be safe and use from that point on, doesn't change the complexity). Total complexity: O((N * M) * M) with one phase (additional character) happening in O(M + N) because you need to calculate the borders for KMP. You can actually use this fact to create a linear recurrence relation for freq[i] and use matrix exponentiation (the column matrix keeps freq[i], freq[i-1], the transitions and keep swapping them) starting from the point that it repeats, this would result in a O(log(M) + M + log(N) * 4^3) phase per character in the answer. The log(M) comes from the fact that fib is exponential, so the point that it starts repeating is O(log(M)). This would result in a O(M * (M + log(N))) solution.

Code for O((N + M) * M) solution: http://codeforces.com/contest/1065/submission/44225229

Edit: If there's an occurence in the transition, you can also keep calculating until it breaks K. It will break K in O(logK) steps and if there's no occurence, you just break. So I guess the second part wouldn't be necessary for the O(M^2) complexity.

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

https://codeforces.com/contest/1065/submission/44147964

For C,my approach is a bit similar can anyone help me,where i am wrong?

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

Can someone explain d.

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

Can anyone please suggest what is wrong with my approach? Submission

I am first sorting the input array in descending order followed by storing a vector of blocks sliced to reach the subsequent lower level. For instance, if the input array is

4 3 2 2 1

my vector is

1 2 4 5

Finally, I am traversing to find out if a single or combination of blocks is less than or equal to k or not and incrementing the counter as a result.

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

Hi! I have a problem can anybody help? if u submit this solution for problem D with MS C++ u get accept! Link to code! but gnu++ gives WA! do u know why?

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

Can E solve by polya?

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

This for problem D, can anyone tell me why my solution times out (http://codeforces.com/contest/1065/submission/44417842)

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

In the tutorial of Problem E: cnt function : why is there *(mod+1)/2 instead of /2 directly in the return. I am getting wrong answer with /2 but I am not able to understand why.

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

Why this this solution for problem 1065C is not correct ?

Since the attainable equal height is the Smallest number.

then Number of Chops can be : ceil((SumOfHeight - N * minHeight) / K)

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

Problem D can be solved with a single BFS using a state of four dimensions: current x, current y, piece type, current square we are at. The result is the minimum among final states. https://codeforces.com/contest/1065/submission/46351519