PikMike's blog

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

1096A - Find Divisible

Tutorial
Solution (PikMike)

1096B - Substring Removal

Tutorial
Solution (Vovuh)

1096C - Polygon for the Angle

Tutorial
Solution (adedalic)

1096D - Easy Problem

Tutorial
Solution (PikMike)

1096E - The Top Scorer

Tutorial
Solution (PikMike)

1096F - Inversion Expectation

Tutorial
Solution (PikMike)

1096G - Lucky Tickets

Tutorial
Solution 1 (adedalic)
Solution 2 (BledDest)
 
 
 
 
  • Vote: I like it  
  • +81
  • Vote: I do not like it  

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

I solved C differently, also I don't know if it is correct.

Let three chosen points in anti-clockwise order be i_1, i_2, i_3 such that i_1 < i_2 < i_3.

Join (i_1)-(i_3) & let angle it make with (i_1)-(i_1 + 1) be theta and number of vertices between them be x.

Join (i_1)-(i_2) & let angle it make with (i_1)-(i_1 + 1) be phi and number of vertices between them be y.

Using property of polygon(not necessary regular) : sum of interior angle with n sides is (n-2)*180 we can write two equations for theta and phi.

Let alpha be given angle and omega be internal angle of n-gon = (180-360/n).

2*theta + omega*x = (x+2-2)*180 — (1)

2*phi + omega*y = (y+2-2)*180 — (2)

Subtract (2) from (1)

2(theta-phi) + omega(x-y) = 180(x-y)

2*alpha + (180-360/n)(x-y) = 180(x-y)

2*alpha = (360/n)(x-y)

alpha = (180/n)*(x-y)

alpha*n = 180(x-y)

Therefore alpha should be a divisor of 180(x-y) and for minimum n, 180(x-y) should be minimum. Note : Check that for obtained n-gon, its internal angle is greater than or equal to given alpha angle.

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

    will the following work ? internal angle of polygon =180- 360/n; so the given angle should be less than or equal to the given number . so find the min n that satisfies this .

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

Please fix B tutorial, where you say about two corner cases. They are swapped.

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

    Yes, they're swapped. I thought about it in reverse order :) Thank you, I will fix it now!

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

      Can you explain me how to do problem F? I am really confused.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Isn't it (cnt(-1))((cnt(-1)-1)/4 in tutorial of F case 1 instead of +1.

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

    Yep, thanks, should be fixed in a couple of minutes.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone properly explain task D? So that a beginner can understand you

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    Is it only me or does anyone else feel that the code of grandmasters is not at all readable?

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

    This is such a basic dp that I'm not even sure what to begin with.

    The way I thought of it was about the following.

    At first, notice that you can check if string has "hard" as subsequence with the greedy strategy. Like take the first 'h', then the first 'a' after it and so on.

    Imagine you have already processed some prefix of s (deleted some characters in it). That means that left out characters have formed some prefix of "hard". What options do you have for the next character? You can either remove it and add ai to the answer or leave it in the string. The second option implies that the current formed prefix of "hard" will be continued with this character (if it equals the next character of "hard").

    Any greedy strategy of removing letters sounds kinda weird (I don't even say that the correct doesn't exist, who knows). However, dpn, 5 is pretty straightforward. Those described transitions are easily done in this dp. And the answer will be the best of all states with n characters of s processed and string "hard" unfinished.

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

      I thought of a different approach but couldn't code it up due to time constraints. Basically, my approach was to delete all occurences of any of the 'h', 'a', 'r', 'd' characters that contribute to the 'hard' subsequence (i.e. delete one of the 4 characters fully so you can't form the subsequence).

      Notice, how I said contribute to the 'hard' subsequence. In 'hhardh' , the 'h' at index 5 does not contribute to 'hard' subsequence so it shouldn't be deleted.

      Now, how do you find the characters which contribute to 'hard' ? Maintain, an array (i.e. every index will have its own array) at every index which store previous indexes of characters which contribute to 'hard'. For eg: At index 0, 'h' does not need any previous characters (since it is start of 'hard') At index 1, array is empty as well ('h') At index 2, array will contain 2 values of previous character (0, 1 since these indices have 'h' in it and 'a' is after 'h') At index 3, array will contain 1 value (2 for previous occurence of 'a') and so on. After this, find all occurences of 'd' and go through each of its value and delete all occurences of one of 'h', 'a', 'r', 'd' . (Keep in mind for conditions like 'hardhard' where 2 mutually exclusive 'hard' are possible)

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

        But there are cases that this will not answer correctly, like:

        6 harard 10 1 10 10 1 10

        You can delete an 'a' and a 'r' with cost equal to 2, and get 'hrad'. You will get a valid solution with your greedy idea, but possibly not the best (the minimum).

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

          I would delete either the ‘h’ or the ‘d’ since their sum would be 10. As I’ve said, I delete only 1 character fully from the string so I wouldn’t ever delete 2 different characters (like ‘h’ and ‘d’ at the same time). Just the character which has minimum sum

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

      Hi PikMike,

      I'm not sure what you mean by this line:

      "Otherwise we either change the letter, or let it stay as it is (and the length of the prefix we found so far increases): "

      The corresponding line in your solution code: dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i]);

      ^^^ Can you tell me 2 things in that line of code:

      1) Why isn't it "j+1" ? Could you clarify that a bit more please ?

      2) There doesn't seem to be any check if the current character (s[i]) is one of {'h','a','r','d'}. Logically speaking, why would you want to remove/delete something that's not one of them ?

      I'm struggling to understand the solution tbh, is there any standard problem similar to this ?

      Thanks!

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

        It's the other transition in my code, not this one. And there j is increased if si = "hard"j

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

          But the other transition doesn't involve the addition of ambiguity .... how is it accounting for deletion of that character.

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

        It is simple .All you need to do is to think whether to remove character at current index or not.

        Lets say at current index charcter = 'd'.

        CASE 1 : If we remove it ,then we will add cost of removing current character (cost[i]) to cost that we have calculated till its ('d') last occurence.


        dp[i]=cost[i]+dp[last_occurence_of_current_character]

        Eg. hardhadrhard

        let say i am at last character and want to remove it, then the cost calculated after last occurence of current character(i.e 'd') should not be included in ans because that will never form any "hard" subsequence without this 'd'.Same is the case with 'h','a','r'.

        CASE 2: If i want to keep that character('d'),I need to make sure that somehow i will break that hard sequence(but this time i cannot do anything with this 'd') .so i will go to the previous charcter in "hard" sequence and will add the cost calculted till that index.

        (for eg. if my current charcter is 'd',i will go to last 'r' and compare it with my ans of CASE 1).

        NOTE: In case of 'h'.You have no previous character(since it is the first character of "hard".Then will just add cost of all 'h' that you have traversed till current index).

        My dp state is different and i have not used any 2 d dp

        Check my submission here

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

      that sounds like a 0-1knapsack approach, is it so?

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

        No, I was not maintaining cost for every prefix at every index.The length of prefix is implicit in dp.If current character is 'd' ,it means minimum cost to avoid making "hard" , if current character is 'r' it means minimum cost to avoid making "har" and so on.

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

        Not even 0-1, actually. You are kinda paying for throwing the item out of knapsack, instead of paying for including it.

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

    I have solved it with another DP solution.

    If we see a 'h' then we will remove it and go to the next character. and will also go the next character without removing it.

    If we see an 'a' then we will go to the next character without removing to and also go to the next character by removing it to if we see a 'h' before it. If there is no 'h' before 'a' then there is no meaning of removing the 'a'.

    same for 'r'.

    And last, if we see a 'd' then we will make the decision carefully. If we see a 'r' before it then it is obvious that their is atleast one 'a' before 'r' and also atleast one 'h' before 'a'. So we have to remove the 'd'. otherwise go to the next character without removing it.

    my solution: https://codeforces.com/contest/1096/submission/47805573

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

Very confused about 1096E, why g(s, p, m) = dp(s, p, m)?

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

    Try googling for "Stars and Bars" problem, it should help.

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

To problem E, it can also be shown that the complexity is O(s2).

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

    How can this be shown?

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

      After fixing Hasan's score, denoted by i, the number of top-scorers is at most (the case where i = 0 is trivial so i > 0 is assumed). And for each g(s, p, m = i), there are non-zero terms in the summation formula. Thus the total complexity is , which is also O(s2).

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

        Ah, yeah, thanks. If only I coded it in a way that the solution would have that complexity :D

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

in tutorial for problem C. whats the logic behind writing "Since GCD(180/g,ang/g)=1, then 180/g must divide n. Analogically, ang/g must divide k"

can't it be reverse, like n must devide 180/g or not devide it at all, instead k devides both n and ang/g.

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

    At first, to clear possible misunderstanding: a divides b means that b = k·a.

    At second, let's look at equality ax = by where (a, b) = 1. Then and x is integer, but b is not divisible by a, so y must be. In the same way, leads to fact, that x is divisible by b.

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

To help with some who is not able to understand the editorial for E. I'll restate it in this way. Enumerate on the score t of Hasan and the number of players cnt that share the same score with Hasan. Then the remaining problem is to count the number of solutions x1 + x2 + ... + xp - 1 - cnt = s - (cnt + 1)t, satisfying that 0 ≤ xi < t.

To make this subproblem more clear, our goal is to count the number of nonegative solutions to x1 + x2 + ... + xn = m, satisfying xi < s. If we can solve this subproblem in O(n) time, then the original problem can be solved in O(sp2) time.

So basically, how can we solve this subproblem? If without the xi < s constraint, then the number of solutions is . This is derived by a multiset counting formula. To let it make sense, the number of positive solutions to x1 + x2 + ... + xn = m is , which is equal to the number of ways of inserting n - 1 bars between m objects. And the number of nonnegative solutions to x1 + x2 + ... + xn = m is equal to the number of positive solutions to x1 + x2 + ... + xn = m + n, which is

And when we have the constraints that xi < s, we need to use inclusion-exclusion principle. Say if there are i variables that exceeds the limit, i.e., with value  ≥ s, then the equation would become x1 + x2 + ... + xn = m - si, and the number of nonnegative solutions to that equation is . So, with the help of inclusion-exclusion principle, the answer to that subproblem is

.

Hope that is clear to you enough. If you want to solve that subproblem, here's a link: Character Encoding

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

    How to solve these equations when variables have coefficient?

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

      That greatly increases the difficulty, which makes the problem generally much harder to solve, if without small constraints and some other special properties.

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

    I didn't get the last paragraph. Can you please explain how you got the above above by using inclusion exclusion principle?

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

Need help in understanding 1096G, I'm only able to understand the first para properly

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

This tutorial is awesome.

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

In problem G why is this true?:

"So, if we exponentiate these values, we get a set of values of exponentiated polynomial in the same points."

I mean if you have point-value representation of a polynomial P(x), eg: (x1, P(x1)), (x2, P(x2)), ..., (xn, P(xn)) why point value representation of P(x)k is (x1, P(x1)k), (x2, P(x2k)), ..., (xn, P(xn)k), note that degree of P(x)k is k * deg(P).

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

    Shortly, it's math induction.

    For the basic case (number of digits is 1) it's kinda obvious.

    Then, suppose it's true for z digits. Let's prove it for z + 1 digits.

    . Let's rewrite it as follows: , where ci = 1 if i is allowed, or 0 if i is not allowed. But that's the same as if we multiplied two polynomials: one being f(x), and the other being the polynomial having values of dpz as coefficients. But we already assumed that this polynomial is (f(x))z, so the result is (f(x))z + 1.

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

      That is not what I'm asking, I'm talking about why doing NTT then exponentiating each image of polynomial in point-value form and doing Inverse NTT works, check my edited comment below.

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

        Okay. Recall that Discrete Fourier Transformation gives us a set of polynomial values in some points. We don't actually care which are these points, but if the number of points is greater than the degree of polynomial, then we may restore it back.

        How do we multiply two polynomials f(x) and g(x)? We apply transformation to them, getting a set of values of the first polynomial in some points, and a set for the second polynomial. Then we multiply these values, obtaining the values of polynomial f(x)g(x) in the same set of points. And then we apply inverse transformation.

        Exponentiation is kinda the same. Apply the transformation, get a set of values in some points. Then raise these values to the desired power. And then apply inverse transform. But to be able to get the result, we have to apply transformation on d + 1 points, where d is the degree of resulting polynomial, not the one we exponentiate.

        I am not sure if it works with complex FFT since there may be precision errors, but with NTT it is perfectly fine.

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

      Also why in editorial are saying that NTT with binary exponentiation is , shouldnt this be ?

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

        if implemented correctly. The last iteration multiplies two polynomials of size , second to last — two polynomials of size , and so on.

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

Can we solve 1096D using max flow-min cut? We will make a graph where h->a, a->r, r->d for all the index such that index of h < index of a. (and for others as well) Now for each such vertex h,a,r,d we will split the vertex into two (say H_begin and H_end) and add an edge with capacity = ambiguity of that index. For example, h->a->r would turn to H_beg->H_end->A_begin->A_end->R_begin->R_end.

We will define a start node st pointing to H_begin vertices with inf capacity and sink vertex si with all D_end pointing to si with inf capacity. All the other vertices will have inf capacity.

Now the question reduces to finding min cut of the constructed graph. Could someone tell me if my approach would work?

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

Hello, E is solvable in O(p)!!! (wow, very short complexity!!!)

Here is my code: https://codeforces.com/contest/1096/submission/47655644 Here is my solution:

We want the number of ways that the first person wins, when he gets  ≥ r

if u consider the number of ways where at least one person gets  ≥ r, then some guy must win, and the first guy will be that person with probability

so the number of ways that the first guy wins (and therefore has  ≥ r since at least one person has  ≥ r) is

so answer is divided by total possibilities which is (# of ways first dude gets  ≥ r)

The number of ways someone gets  ≥ r can be calculated in O(p) with Principle Inclusion Exclusion!

The number of ways first dude gets  ≥ r can be calculated in O(1) with Stars and Bars

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

    Good catch! That's absolutely a better way to interpret the problem. Thanks!
    But currently with these constraints only 26 contestants came up to a solution! Imagine if we had set constraints for a linear time solution! :)))
    Btw, I think you'd better say it's O(s+p) because you had a factorial pre-computation which is done in O(s).

»
3 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Please, could someone explain solution to problem G in linear time with no Fourier.
I see, at least four users (mitterr1999 indiewar FizzyDavid Emma194) got OK using this approach.

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

    We need to calculate the nth power of a low-degree polynomial P.

    A(x) = Pn(x)

    A'(x) = nPn - 1(x)P'(x)

    A'(x)P(x) = nPn(x)P'(x)

    A'(x)P(x) = nA(x)P'(x)

    Thus we get the recurrence relation of the array.

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

      This solution is amazing. The code is very short and it runs fast. But indiewar just copied FizzyDavid's code.

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

        I'm sorry...I just want to find a good template of NTT.Then I saw this amazing solution,and I copied it.It's an evil thing to just copy others' code.I'm very sorry.

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

        Can you explain how to solve F?

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

Huh,

I didn't realized that using fast multiplication algorithms within fast exponentaion algorithm mitigates log(N) from fast exponentation under proper analysis and proper implemenation. So I've though Schonhage–Strassen would give O(N·log2(N)) instead of O(N·log(N)) and Karatsuba will give O(Nlog23·log(N)) instead of O(Nlog23).

And O(Nlog23·log(N)) is worse than that is pretty desperate to fit in TL. But now I think that O(Nlog23) might be good enough. So, is there anyone who solved G with Karatsuba?

By the way, second solution from editorial is really cool!

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

i don't understand the solution for the C problem can some one explain it better or in some understandable way (another solution easy to understand) please thanks in advance

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

Div 2 c , i am not able to understand the last line where it says if k = n-1 , we have to take x = 2 , but why ? if x = 1 and ang/g = n-1, then k = n-1 but that is incorrect as 1<=k<=n-2 , if we take x=2 then k = 2*(n-1),which i think should also be wrong as it does not come in range of k, i am bit confused about this, could anyone please clear it.

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

    If x = 2 then k' = 2(n - 1) = 2n - 2 and n' = 2n, so k' = n' - 2 and it's okay.

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

      Correct me if i am wrong but i think the code provided in the editorial for Div2 c is wrong as for the input

      2 180 0

      it prints the answer as 1 and 2 but in the question it is given that answer can range from [3 , 998244353]. Also, value of k can be equal to n if we put ang = 180 and editorial doesn't mention anything about that.

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

        If you'd read problem statement, you'd see that 1 ≤ ang < 180.

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

          Oh sorry my bad , btw thanks for clearing my doubts

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

my solution for D is exactly similar like editorial but still getting WA can someone help 47725623

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

Can anyone please Explain last part of the B Tutorial "And the bonus (this case is not belong to the given problem): if all letters in the string are equal then then answer is n(n−1)2+n because we can choose any substring of s of length at least 2 and any substring of length 1. " with example.

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

I'm a newbie can someone please explain how can we approach to the problem C like initially, I was very well aware that it is a basic formula of calculating sides i.e. if any interior angle is given i.e. x=((n-2)*180)/n but I got no idea how GCD plays a crucial role here please someone explain in detail. I repeat I'm a noob. Thank's in advance.

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

My solution for C is slightly different from the editorial.

Before answering the T queries, I first declare an array ans[180] and let all a[i] = -1.

Next, I iterate i from 1000 to 3,

for each i, iterate j from 1 to (i-2), which means finding all the possible angles for the i-gon.

Check if the degree of that angle is an integer by if( 180*j%(i-2) ) continue;

180*j / (i-2) is simply from cutting any of the angles of a regular polygon 180*(n-2)/2

if 180*j / (i-2) is an integer, update ans[180*j/(i-2)] = i

After that, for each query, output ans[ang]

You can see my code for further details: 47791128

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

    You said "finding all the possible angles for the i-gon." But, how do you know that value of i will be b/w 3 and 1000, when it's written that there can be a maximum of 998244353 sided polygon.

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

      We know that angle<=180 if you take n as 1000

      the result will be ans=180*(1000-2)/1000 equals to 179.8(satisfied above condition<=180).if you take 1001 then angle will go beyond 180.so it doesnot satisfy the above condition.
      
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

" because we can remain from 1 to l letters on the prefix, from 1 to r on the suffix or empty string).

In the second case we can remain from 0 to l letters on the prefix and from 0 to r letters on the suffix. But now because s1=sn we can combine these ways, so the answer is (l+1)⋅(r+1). "

someone explain 0 to l letters and 1 to l letters , what is the difference?

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

In problem F, couldn't get the meaning of P.Q^-1 (mod 998244353). Can anyone please explain. For the first sample testcase answer is 2.5. So P=5 and Q=2, then how come we get 499122179 .

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

    For Q = 2, Q - 1mod 998244353 is 499122177. So (5 × 499122177) mod 998244353 is 499122179. I hope you understand what Q - 1mod 998244353 means. If not, look for "modular inverse".

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

Can anyone please explain what the following function does in problem F??

int f[N];

void upd(int x){ for (int i = x; i < N; i |= i + 1) ++f[i]; }

int get(int x){ int sum = 0; for (int i = x; i >= 0; i = (i & (i + 1)) — 1) sum += f[i]; return sum; }

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

Can anyone give an more INTUITIVE explanation for problem F?

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

I'm not understand why test #44 (problem B) has anwser 1. Because l>=1 and r >=1. So: l+r+1 >= 3 and (l+1)(r+1)>=4

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

Not particularly proud of it, but it's possible to squease an O(s*r*p) solution past the time requirements.