MrPaul_TUser's blog

By MrPaul_TUser, history, 2 months ago, translation, In English

Ideas: MikeMirzayanov.

1551A - Polycarp and Coins

Tutorial
Solution

1551B1 - Wonderful Coloring - 1

Tutorial
Solution

1551B2 - Wonderful Coloring - 2

Tutorial
Solution

1551C - Interesting Story

Tutorial
Solution

1551D1 - Domino (easy version)

Tutorial
Solution

1551D2 - Domino (hard version)

Tutorial
Solution

1551E - Fixed Points

Tutorial
Solution

1551F - Equidistant Vertices

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

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

good contest for "try of pen",i like it,thanks.waiting soon for your div 2 and div 1 contests.

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

Even though the DIV3 was harder than the last few DIV3's, I think the problem set was way more enjoying and educational for a lot of people. I hope you set more DIV3's MrPaul_TUser

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

    But please, make it easier, as a person with <1600 rating,I can say, that at least 4-th problem was very and very hard for actual div3 participants.MrPaul_TUser Thank you anyway. ;)

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

      actually,i dont think that this contest was harder than standart div 3

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

Transposing the table in D2 was a nice idea! Saves a lot of casework.

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

    Can you explain how transposing would give the same notion as m odd and n even? why are the values swapped?

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

A slightly shorter branchless alternative implementation of A, which does the same job (adding 1 to n before division by 3 is the same as incrementing the result by 1 in the case if the remainder was 2):

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

can someone tell the error in code for problem E if I use some other method to memoize it run upto test case 4 : Problem E

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

Please help me in this code (problem B2).
I'm not able to figure out where I'm doing wrong.
This code is failing on tescase-185 of test-2.
My submission

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

    According to me you are assigning a occurrence of number same color assigned earlier.

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

    Have u got the error in ur soln as i am also facing the same issue.

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

    when ur are considering the nos having frequency less than k the order also matters suppose there are 4 colors. and 1,2,3 are having count less than 4. if the arrangement is like : 1 2 2 3 1 nos in array. 1 2 3 4 1 coloring . the no 1 is getting the same color.

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

      got it. Thanks!

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

      Weird, I think I took it into consideration. Your testcase seems to be working for me. Can you provide anything else? This is my submission: 123642660.

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

    I made the same mistake as you. For the testcase:

    1
    5 3
    1 2 3 3 1
    

    Your code outputs: 0 0 1 2 3 which is obviously wrong. The idea is that for the numbers where the number of it's occurrences < k you first color all instances of that number then move forward to the next number. Here's my solution, hopefully it's readable.

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

      This reply wasn't to me but since I didn't get any help I'm bumping this. Your sample case yields the output: 3 1 2 0 0 which seems correct if I'm not mistaking the problem statement.

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

Really enjoyed A and B! Thanks for a great contest.

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

https://codeforces.com/contest/1551/submission/123610411 This is my submission for problem F. According to me the complexity of my solution is of degree 4 so how did this not give TLE?

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

    you are lucky

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

      Yeah but still the runtime is just 62ms

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

        clear $$$n^3k$$$ time for $$$n,k<=100$$$

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

        The O(n^3k) part of your code is setting the dp table to -1, which has a small constant and runs very quickly (10^8 operations). Your recursive solve function for every root and distance runs in O(n^2k) time since every edge can only be connect to 2 vertices. Iteration to find combination over each edge happens at most twice each edge.

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

What if problem C was changed a bit and one letter should have more occurence than other letters taken individually, and not in total, how should we proceed then?

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

    I misread the problem as you described during contest and was banging my head to get a solution :(.

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

    Not sure whether this is correct, but here is what came to my mind.

    We can calculate the maximum number of words we can take considering every character as the 'dominant' character.

    Let us say we want to have 'a' as the dominant character. We iterate over all the words one by one, taking all of them in our collection (for now) and keeping track of the total frequency of every character till now. We also maintain separate sets for F(s, 'a', c2), where F(s, 'a', c2) represents this — In word s, frequency('a') — frequency(c2).

    So now, suppose we encounter a word due to which 'a' is no longer our dominant character, but instead 'b' is. We refer to our set for F(s, 'b', 'a') and remove the the word s which has the largest F(s, 'b', 'a') from our collection (and also from other sets).

    The idea is, take all words as you encounter them. But if a certain words causes 'a' to lose its dominancy to some other character (say 'b'), we will remove such a word which will reduce the total frequency of 'b' as much as possible while not hurting 'a' much, thus restoring dominancy of 'a'.

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

    bro, just realized i read the problem wrong,thnks

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

The contest was great! It would be better if the editorial for C, would be more explained!

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

It is possible to solve E with a 1D dp. Details in spoiler.

Spoiler

Submission: 123519134

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

    Well done! Nice solution.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    $$$ (i - a_i) - (j - a_j) \le i - j - 1$$$

    seems to be just

    $$$ a_i > a_j $$$

    right?

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

      Yeah...you can simplify the condition like that. I just thought it made more sense to present it the way I did.

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

Tutorial for D2 seems complecated.

We can reduce to two cases: Number of rows is odd or is even.

In case odd we need to place one row of horz dominoes, max k dominoes. In case even we do not.

Then we place allways two rows of dominoes at once, until k dominos are placed. Then fill all other fields with vert dominoes.

Finding a useable letter foreach dominoe is not hard, simply check the surrounding cells. 123518743

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

    In case odd we need to place one row of vert dominoes

    I think there should be horizontal dominoes instead of vert..as in one row only horizontal dominoes can come.

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

    Hey , I found your approach beautiful . But I know that I will never be able to find this kind of approach by myself. Can you show some lights on how you started thinking about the problem , and eventually came to this solution .

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

If anybody is interested and have enough time to help me, please do. I understand their are better approaches for B2 then this, but I am not able to understand why did this approach failed.

Approach :

  1. Find how the max number which we can allot colors by desired conditions , say this is x
  2. loop through k colors : 1.assign kth color to a number 2.Store that number in unordered_map, so that same color doesn't get assigned to same number 3.Maitian a count=x, which is basically the number of time to allot and decrease it everytime the color is alloted.

Here is the link for the submission — fails on tc 554 123566013

Also show no mercy if the code is bad, so that I get to learn how to code better than what I have done.

Peace out!

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

    use this tc 1 6 3 1 2 5 3 3 3 your solution will output 1 1 2 2 3 0 but one of the correct ans will be in the form 1 2 3 1 2 3 I think your solution will also give tle for larger value of n. if you till have any doubt feel free to ask me.

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

Is it possible to solve Equidistant Vertices in faster than O(N^2 K) (maybe with some optimization in the dp)?

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

    Here's what I think. If you fixed the root, and then you fixed the depth of the nodes from the root, you want to find the number of ways to pick $$$k$$$ nodes from them so that their pairwise LCA is the root. Naturally, this splits up our set into some $$$m$$$ groups, from which we can fix $$$k$$$ groups and then the number of ways would be the product of the sizes of those groups. Let's say the group sizes are $$$g_1, g_2,...,g_m$$$. If we consider the polynomial $$$(x+g_1)(x+g_2)...(x+g_m)$$$, then the value we want is the $$$k^{th}$$$ coefficient starting from the largest term ($$$0$$$-indexed). Now, this product can probably be computed in $$$\mathcal{O}(n {\log}^2 n)$$$ with divide-and-conquer+FFT/NTT for an overall complexity of $$$\mathcal{O}(n^2{\log}^2 n)$$$. I haven't implemented it myself, so please point out the error if you think I'm wrong.

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

      Oh that's a nice idea. How is Kth coefficient computed in O(N log^2(N)) though?

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

        Well, I think the following: If we split our product into two halves and compute each half, we'll get two polynomials of roughly equal degree, which we can then multiply with FFT/NTT. The recurrence relation would look like $$$T(n)=2T(\frac{n}{2})+ \mathcal{O}(n\log n)$$$, and we can use the master theorem for divide-and-conquer to get that this works out to $$$\mathcal{O}(n{\log}^2 n)$$$. We can simply extract the required coefficient from the final answer presented in the form of a list of coefficients.

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

          Ah I see. Nice solution! Could this be done faster with generating functions?

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

I am getting TLE for test case two for prob B2. Can someone tell me is my approach wrong as I am getting TLE even though tc is NlogN. My solution https://codeforces.com/contest/1551/submission/123636719

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

    When the number of test cases is equal to 10000 your vectors hsh[200005] and prev[200005] initializations take too much time. Try the size of vectors N like in your v[] and ans[] vectors.
    But your greedy idea to take the first vacant color is incorrect. Try test:
    1
    9 3
    1 2 3 4 5 6 6 7 7
    Your answer is:
    1 1 1 2 2 2 3 3 0
    The correct answer may be:
    1 2 3 1 2 3 1 2 3

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

**For those who are struggling with the C problem **

Approach : we have only five characters ..so we can check explicitly for each character and choose the most suitable ans. for this we will use the term advantage(+ or -ve) & this will be calculated by the formula advantage = frequency(current_char) — frequency(other chars). we will store these in the array & will sort in the descending order after that we will count the the numbers of this array while the sum remaining +ve

and finally we have to maximise this number of terms.

Hope this helps:)

**Implementation : **123638069

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

Problem B2:

let's calculate for each of k colors the number of elements painted in the color — all calculated numbers must be equal

I am not understanding how are we managing this condition in given tutorial. Please anybody explain

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

    Take k occurrences of the numbers whose frequency is greater than or equal to k. For all other numbers, take the total sum of frequencies of these numbers (let say the sum is s), and color a*k of these occurrences s.t. (a+1)*k>s .

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

does anyone know,3075 TC of 3rd test case or it will be great if someone pointout error in my code 123505740

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

    Your idea to change only one color per one value is incorrect. Try test:
    1
    24 12
    1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
    Your program gives answer
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    The correct answer may be
    1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
    You may correct your program with changing as more colors for one value as you need. It will be a loop for your w variable.

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

good game!!!

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

Another approach for B2 would be doing binary search on how many elements can be painted in one color.

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

    Can you please elaborate your idea of binary search because I was trying to do it through binary search but got tle on tc5.Although B1 passes due to low constraints . Here's my submission https://codeforces.com/contest/1551/submission/124039451 Can I improve my code or do I need to think of solving it through another approach ?

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

      You need to change your good() function. You should use something like set which will keep the pairs sorted. You can seelink my check() function

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

Hey! Guys, can you help me with problem 1551B2 - Wonderful Coloring - 2? I didn't understand the editorial :(

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

    The terms of the question are: i)each number should have different colors. i.e; a number cannot have the same color twice or more. ii)each color should occur the same number of times iii)the number of elements painted must be maximum. sol: let me explain with an example a=[3,1,1,1,1,10,3,10,10,2] and k=3.

    i)you have k colors, so for a particular number the maximum number of colors you can have is k. then a number can only be painted k number of times. in the above example since k is 3 and there are four '1's . '1' can be painted only k(3) times. remaining ones are unpainted.
    ii)for the second condition, each color should appear the same number of times. so for n numbers, each color can appear (floor(n/k))(i.e; (n-(n%k))/k). the total number of tiles that can be painted respecting the second condition is (n-(n%k)) or floor(n/k)*k. for the example above since there are 10 numbers 10-(10%3)=9 elements can be painted.
    iii) to obey both of the above conditions, first you calculate the number of elements that obey first condition i.e; if the occurrence of the number is less than or equal to k, you count it if it is higher than k you only count k occurrences. then according to the second condition you take only the (n-(n%k)) elements of the counted elements. in the above example '3': 2, '1':4, '10':3, '2':1.
    so the count is 9. then 9-(9%3)=9. so you can use these 9 elements for painting which satisfies all the three conditions. the tricky part here is the order in which you paint them, so you don't end with two numbers painted in the same color.
    iv) create an array of n numbers and initialize all the elements to 0. then take note of the indices and count of all the numbers that satisfy the first condition. then only consider the first n-(n%k). then paint each number completely then move on to the next in a loop of the k colors.
    example: a=[3,1,1,1,1,10,3,10,10,2] and k=3.
    
    number:indices number:colors
    '1':2,3,4      '1':1,2,3
    '2':10         '2':1
    '3':1,7        '3':2,3
    '10':6,8,9     '10':1,2,3
    answers may vary due to implementation!!!!
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks alot for the amazing contest it was really great solving problems in this contest ! Keep up the good work ! Cheers !

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

IN PROBLEM B2, when i use array to store the answer, code gets accepted (https://codeforces.com/contest/1551/submission/123682445) . BUT when i use vector to store the answer , it shows TLE. https://codeforces.com/contest/1551/submission/123682542 . can anyone explain ?? (i have written the same code as given in tutorial except that i have used vector to store the answer)

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

    You see your vector initialization takes more time then memset() for an array. You don't need so big vector, length of n+1 is enough.

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

      both vector and array that i have used(see both codes once) are initialised with the same size (i.e, 2*(1e5)+13).So, why does using vector gives TLE.

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

        Yes, your vector has the same size as your array has. But array occupies a continuos segment of memory, so array initialization is more faster, it works like memset() function. Vector is a more complex structure, so vector initialization takes time as a loop for().

        Your solution with vector will work with reduced size of vector.

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

          understood. thanks for explaining

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

I am getting wrong answer on test2 in problem B2, can anyone help? https://codeforces.com/contest/1551/submission/123691506 message is: wrong answer Not all colors have equal number of elements (test case 460)

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

    Your idea to start color numeration p from the same beginning color number c is incorrect. Try test
    1
    6 3
    1 1 2 2 3 3
    Your program answer is:
    2 1 2 1 0 3
    Correct answer may be:
    1 2 3 1 2 3
    Try to wrap color numeration p to 1 after color number == k and start with p for the next value. To prevent same values of one color don't push excess position numbers in your forward_list ls.

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

      Lot of Thanks for help!! I understood where I was wrong....Thanks for providing test Cases and suggestion.

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

I am getting wrong answer on test case 2. https://codeforces.com/contest/1551/submission/123520328 .It is showing wrong answer Not all colors have equal number of elements (test case 554).

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

    Try the test:
    1
    6 3
    1 1 2 2 3 3
    Your program answer is:
    3 2 3 2 1 0
    The correct answer may be:
    1 2 3 1 2 3

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

Can anyone help me with a test case for which my solution for problem E fails.

it fails on test 5 after running fine on hundreds of test cases.

https://codeforces.com/contest/1551/submission/123833545

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

Can somebody please tell the 460th test case. My solution is giving wrogn answer.I simply binary searched over the required balls. But for checking i first check the high frequency numbers . Can somebody help

https://codeforces.com/contest/1551/submission/123864598

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

submission:123674964 My submission for problem B2 is showing : For Test Case 2 : wrong answer Color #1 has at least two elements equal 4 (test case 185) Can anyone point out the error in my code?

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

    Same here, I have three comments in this thread. Hopefully, someone points out what's wrong here.

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

For the ****Problem B2 ****, I am getting runtime error on submission but working on VS CODE and not able to identify the error can someone help me to find the error, please

123985947

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

This E is a really good combination of dp and binary search!

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

Hey could someone help me in Problem B2. Im getting an wrong answer in test 2 for testcase 69. This is my submission: My submission

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

125113648 Can someone explain why I got TLE in test 6th problem E :(

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

Code is in the link. Can anyone please have a look at my submission? My code got stuck at test case 69 in the second group of test cases. Any feedback or advice will be highly appreciated!

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

Hey everyone, I'm a noobie in this community. Really enjoyed problem B2, learnt a few things along the ride. I am getting the wrong output though, if someone can point me in the right direction I'd be thankful. Here's my submission: 125525276

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

    Your code got stuck in the same test case as mine did, buddy! Let's have a look at each other's code and discuss.

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

      Hey there, Unfortunately I'm not familiar with the Go language. I found out what was happening so the code would fail in my submission. My method for coloring was fine, but in some instances, it was coloring more than it should. The way I solved it was finding out the real maximum elements we can color. I leave some test cases that helped me figure it out. Maybe it will serve you as well.

      (first one)
      1
      10 4
      1 1 1 1 1 4 1 4 2 2
      (one possible valid output : 1 2 3 4 0 3 0 4 1 2)
      
      (second one)
      1
      12 4
      1 1 1 1 1 1 1 1 1 4 2 2
      (one possible valid output: 1 2 3 4 0 0 0 0 0 0 0 0)
      
      (third one)
      1
      12 3
      1 2 3 4 1 2 3 2 1 4 3 2
      (one possible valid output: 1 1 1 0 2 2 2 3 3 0 3 0)
      

      Hope it helps :-)

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

        Thanks, buddy! I have already solved it. It turns out to be a silly bug caused by my misunderstanding on Golang syntax. :-(