tianbu's blog

By tianbu, history, 4 weeks ago, In English
A Tutorial
A Code
B Hint 1
B Hint 2
B Hint 3
B Tutorial
B Code (Python)
C Hint 1
C Hint 2
C Tutorial
C Code
D Hint
D Tutorial
D Code (Python)
E1 Hint
E1 Tutorial
E1 Code
E2 Hint
E2 Tutorial
E2 Code
 
 
 
 
  • Vote: I like it
  • +184
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Great problems

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

Good stuff, I liked C a lot, it made me think of LCM in a new way

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

    can you please elaborate your thought about LCM..

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

      yes plz how u thought of lcm i thought of 3 first then thought for 6 then 12 and come up with factorial approach but it hasn't worked.

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

        I'll try to explain.

        $$$n \leq 1e16$$$, so just starting a loop and trying to find an answer for each $$$i (1 \leq i \leq n)$$$ is a bad idea. This is why we need to "group" the answers. It is important to understand that the answers cannot be great. Because if $$$f(i) = x$$$, it means that i has divisors $$$2, 3, 4 \dots x - 1$$$, so $$$i \geq lcm (2, 3, 4 \dots x - 1)$$$

        Let's try to figure out what $$$⌊n / lcm (1,2, \dots, i) ⌋$$$ means. This is the number of elements that are divisible by $$$2, 3, 4 \dots i$$$, so we have not counted the answer for them yet. Thus, based on the editiorial "The number of ks such that $$$f (k) = i$$$ is $$$⌊n / lcm (1,2, \dots, i — 1) ⌋ — ⌊n / lcm (1,2, \dots, i)⌋$$$" It means that $$$⌊n / lcm (1,2, ..., i — 1) ⌋$$$ is the number of elements that have "reached" us. And $$$⌊n / lcm (1,2, ..., i) ⌋$$$ is the number of elements for which the answer is greater than $$$i$$$. Thus, subtracting one from the other, we get the number of elements for which the answer is equal to $$$i$$$. And of course, sorry for my bad English, I tried my best.

        My C++ solution:

        121264752

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

          Thanks for the clear explanation. Just one small correction, instead of

          Because if f(i)=x, it means that i has divisors 2,3,4…i−1, so i≥lcm(2,3,4…i−1)

          it probably should be

          Because if f(i)=x, it means that i has divisors 2,3,4… x −1, so i≥lcm(2,3,4… x −1)

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

            Oh, my fault. I will edit it immediately.

            Thank you!

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

          thanks man, after reading it looks simple logic but why i can't think of these logics in contest :(

          noob me :{

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

            I'm really happy that my comment was useful for somebody.

            You are not noob) In my opinion it's absolutely normal, when you can't solve the problem during the contest.

            P.S. I couldn't solve C too))

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

          Clear explanation.

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

          Do you think f(k) = i = 6, is possible ??

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

            f(k) always takes the value which are perfect power of primes. Like 2^1,2^2,2^3, 3^1, 3^2, 3^3. Let's say if f(k)=p*q. Where p and q both are primes. Here p<pq and q<pq so both of them must divide k. And also gcd(p,q)=1 which implies pq must divide k. Which is contradiction. Pardon if anything is not clear since this is my first comment :)

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

          I was trying to solve this question,everything seems fair to me in my code.But It was giving WA, so I removed only floor and it has passed all TCs. Can you tell me,why?

          123126566

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

        it didn't work because

        lcm of 1,2,3,4 is 12

        while the factorial is 24

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

      to know how many numbers in range 1 to n are divisable by all numbers from 1 to i it equals to n / lcm(1,2,3,..,i) for example :- if n = 15 and you want to know how many number divisable by 1, 2, 3 and 4 floor(15 / lcm(1,2,3,4)) = 1 there is just one number divisable by 1, 2, 3, and 4 and this number is 12.

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

Thanks for the editorial

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

Mathforces!

»
4 weeks ago, # |
  Vote: I like it -73 Vote: I do not like it

This one requires a lot more math, but it's not friendly to younger participants. And, this is an algorithm competition, not a math competition.

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

    why is it not friendly? i think everybody should know smth about LCM. Also B was not hard at all. I am a young participant (i'm 13) and ABC weren't hard at all

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

      smart russians.

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

      Saying ABC weren't "hard at all" won't cut it mate. They were hard, for the average folks. I've been coding for almost 1.5+ years now, and could only solve A. I found a research paper on OEIS which was directly related to C, still couldn't code it up in time. Thank your stars (or rather your smart ass genes lol) that you're able to do such good level math problems at such a tender age. You probably are meant for this, keep solving!

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

        Nobody is meant for anything, it's just the timing when they started. And btw you are comparing your present with his, he also learned to check prime from O(n) to O(sqrt(n)) at some point in time.

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

          i also started about 1.5 years ago)

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

            I guess he is just frustrated by the fact that the contest was just Math+ DP, out of which people struggle at both a bit... ig..

            PS. like, i like geometry and DS based problems, but it has been a long time i haven't seen such problems in recent contests....

            Anyhow its pretty Subjective, i felt yesterday's contest was pretty doable at least till C.

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

      Hard is a relative subject, some topics can be hard for someone, and easier for others. Age doesn't matter at all. This was a more math-focused contest (ABC all have math tag), and a mathematical approach is often harder for some.

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

      Everyone plays games , and only some reach the top but all other plays because they enjoy playing it .

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

    Beacuse your ability is weak but not the round is not friendly.And I think problem D is easier than B and C.So why this contest unfriendly?

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

      Hello, Magic_Moon can you explain D. maybe using dry run or any way you are comfortable with. I am having a tough time understanding it.

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

Great Round, Great problems. Statements were short and crisp problem "C" is my personal favourite. Looking forward to see more such rounds. Thank you!!!

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

Although I didn't participate, I also think the problems especially C and D are wonderful!

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

When I was solving B, for some reason I typed "a^x" as "a*x" and spent almost all round to understand why extended euclidian algorithm doesn't work. Moral of the story: Don't tunnel vision, do your math.

Great round!

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

I spent over an hour on b since I put (n % (a ^ k))%b == 0 instead of (n — (a ^ k))%b == 0.

Nonetheless the problems were good, and I enjoyed the round

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

    I did the same mistake and after seeing other people's code I was like when will these silly mistakes would leave me :(

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

I think B is harder to think than D.

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

Imagine C is harder to think than D...

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

Can someone explain the second paragraph of $$$B$$$ tutorial?

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

    Let us assume n is present in the set. n can be represented as x*a^k + y*b, where x,k,y are whole numbers. Now n%b = (x*a^k + y*b)%b = (x*a^k)%b = x%b * (a^k)%b. x can be any of the previous values in the set, used to generate n. Thus we can assume x = (x')*(a^k') + y*b and x%b = (x')%b * (a^k')%b. Eventually we can see that x%b will be of type a^k where k will be a whole number. Hence we can write n%b = (a^k)%b, given n is present in the set.

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

      thanks! your explanation is so easy to understand.

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

      I have an easier explanation. All numbers in the set can be represented as a^x + b*y. Thus, if we subtract a^k from n and it gives a multiple of b, then n belongs to the set. You can iterate over k to check if the number belongs to the set.

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

        This explanation is so far the easiest one I have found for this problem, I have been trying to understand the other solution for some time now, glad I stumbled upon yours.

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

I had a slightly different approach for problem C. So I will explain my solution and thinking process.

Initially I was not able to solve the problem. Then I remembered one thing that factorial of even small numbers is very large (like $$$50!$$$). So, this gave me direction to think that $$$f(n)$$$ cannot be very large. So I ran a test to see that when we multiply prime numbers up to $$$50$$$, it will exceed $$$10^{16}$$$.

I still had no clue how to solve this problem. Then I randomly wrote a number in prime factorization form. I saw that $$$f(n)$$$ can only be some power of only a single prime i.e. $$$f(n) = p^k$$$ where $$$p$$$ is some prime and $$$k$$$ is its power. I was able to prove this.

Now, I knew that $$$f(n)$$$ can only be some power of prime up to $$$50$$$. So, now if $$$f(n)=p^k$$$, then $$$n$$$ must have exactly $$$p^{k-1}$$$ in its prime factorization form because otherwise $$$p^{k-1}$$$ will be $$$f(n)$$$. Now, I had to think what else should $$$n$$$ must have in its prime factorization form. I observed that for some other prime $$$q$$$ its power $$$m$$$ must be such that $$$q^{m+1} > p^k$$$ because otherwise $$$q^{m+1}$$$ can be answer. Then I found a number $$$D$$$ satisfying the above requirements. Now, the number of multiples of $$$D$$$ minus the number of multiples of $$$D*p$$$ would give the numbers for which $$$f(n) = p^k$$$. Then I would just add contribution to answer. Note that we have to handle a corner case i.e. when $$$D$$$ exceeds $$$n$$$, then we don't take any contribution from $$$p^k$$$.

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

    I massively overcomplicated my solution (originally in Rust, translated to C++) and reading it again now I realize that it basically amounts to Um_nik's solution except mine is slightly faster because it only evaluates the numbers that change the lcm. Of course, it's nowhere near the TL so that doesn't even matter.

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

    can someone tell me what's wrong with this approach? if(i==1)sum+=2; else if(i%2)sum+=2; else if(i%2==0 && i%4==0)sum+=3; else if(i%2==0 && i%6==0)sum+=5; feel free to correct me,

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

Any idea why this solution to B gives TLE? Is it some silly mistake? Cause I've pretty much followed the editorial.

void solve(int testcase) {
    int n, a, b; cin >> n >> a >> b;
 
    if (a == 1) {
        cout << ((n - 1) % b == 0 ? "Yes\n": "No\n");
        return;
    }
 
    int m=1;
    bool res=false;
    while (m <= n) {
        if (m % b == n % b) {
            res = true;
            break;
        }
        m *= a;
    }
 
    cout << (res ? "Yes\n": "No\n");
}
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone analysis the time complexity of problem C for me pls?

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

    Someone correct me if I'm wrong, I think it's O(nlogn) because for every i computing lcm involves computing gcd which is logn with Euclidean algorithm

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

      So you mean there are 10^16 log 10^16 operations in worst case @@?

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

        no, max(N) is about 40-50

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

        Sorry that was a horrible mistake. The loop runs while lcm <= n, and I think by lcm(1,...,40) you passed 10^16, so it should be O(40 log(something))

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

The introduction of hints was really very good. Thanks for such a great editorial.

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

Can someone please guide me through the equivalence of both formulas in C?

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

    I also want to know about this... I've got the first equation but can anyone explain how the

    SUM [ n/lcm(1,2,...,i) ] + n

    comes from SUM [ i { (n/lcm(1,2,...,i−1)−(n/lcm(1,2,...,i) } ) ?

    I figured out the front part but how the (+ n) coming out from it? tianbu

»
4 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

math math math math math maTh MaTH MATH MATH MATH MATH MATH MATH MATH AAAAAAAAAAAAAAAAAAAA!!!!1!!!11!!!

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

These format of spoilers hurt my eye really bad, can you make it like this ? It will look much better.

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

Really a great contest! Kudos!

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

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

Nice contest.
- Team Atcoder Fan, 2021

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

in the C Tutorial : "Since f(n)= i means lcm(1,2,...,i−1) ≤n " why? I don't understand this, can you explain it to me?

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

    because 'i' is the minimum number not divisor of n. and n is divisible by all number (1 to i-1). Like what is the minimum number that divisible by all number (1 to i-1) ??? it's g = Lcm(1,,,,i-1). Now, if f(n) = i, that means (n % g == 0) and g <= n.

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

    I think what they are actually trying to say is that it doesn't make sense to go to such an i where lcm(1,2,...,i-1)>n since the contribution for such an i would be zero.

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

why chinese people think,that math problems are more interesting than algorithmic or data structure?

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

Can someone help me understand how they thought of this DP (and it's states) in problem D?

The current editorial focuses more on implementation, less on the idea.

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

    watch galen colin video.

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

    When you have these expected value problems and you have to compute the total value (or expected value) of all sums, you can generally compute the total contribution of each term and add it separately.

    I think this can somewhat be seen by putting all the subsets of sums with the # of times they get counted vertically. When you add all of them up, you just get one equation in the $$$n$$$ variables (for whatever $$$n$$$ is, here it's the number of terms that start with $$$+$$$). The coefficient of each variable here is the number of times it's counted across all subsets -- which is the same as its independent contribution. Then, you can proceed as above.

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

Look at my code for B, it's very funny compared to the original solution, but still my code passed all the tests. Here is the link: https://codeforces.cc/contest/1542/submission/121210576

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

What are $$$p1$$$ and $$$q1$$$ in E1 editorial? And what do you mean by enumerating $$$p1$$$ and $$$q1$$$? tianbu

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

    $$$p_1$$$ is the first element of $$$p$$$

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

Hi, I don't understand the editorial of problem B. Can someone please explain it to me?

Thanks

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

    Here is my approach — Every element of the set can be expressed in the form $$${a^p + qb}$$$ where p and q are whole numbers. You can try writing the elements of the set in a tabular form to see it for yourself, intuitively. $$$1,1+b,1+2b,1+3b...$$$
    $$$a,a+b,a+2b,a+3b...$$$ $$$a^2,a^2+b,a^2+2b,a^2+3b...$$$

    We want to check if n is expressible in this form. To do this, iterate through p from 0 to any large enough value. For each value of p, check if $$$n = a^p + qb$$$, that is, ($$$n - a^p$$$)%b == 0. If this is true, the answer is YES. The loop terminates when $$$a^p$$$ becomes greater than n itself.

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

Does anyone have a different solution for E1?

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

froggyzhang had given a solution for e2 by using generating functions which i think is much easier than the official tutorial(which is also great!). Unluckily, it's in Chinese. And if anyone want to read it you can find it here.

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

.

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

Is there any recursive approach to solve D

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

In B, is it true that if $$$n$$$ is equal to some power of $$$a$$$ then $$$n$$$ belongs to the set?

I had the following condition in my code:

if( n % a == 0) {
    cout << "Yes\n";
    continue;
}

and for some reason this gives a wrong answer. My reasoning was the following. If $$$1$$$ and $$$1 \cdot a$$$ are in the set then $$$1 \cdot a \cdot a$$$ must also be in the set and other powers e.g. $$$1 \cdot a \cdot a \cdot a$$$ as well. So if $$$a$$$ divides $$$n$$$ i.e. $$$n \pmod a == 0$$$ then $$$n$$$ should be in the set. Am I missing something trivial ????

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

Can someone explain in better/different words what the states in the DP for D actually represent? The editorial is not at all clear to me.

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

    For each number x, to determine whether it's in the final set or not, we only need to consider those numbers that are smaller than x. Because those larger ones will always be popped after x is popped. If there are more than one x, we assume the one that appears first is smaller.

    So, for each number x, define f[i][j] represent: after considering the ith operation, how many subsequences are there satisfies that there are j numbers in the set are smaller than x. (Remember to ignore the operation for the number x).

    Then do the dynamic programming as the tutorial shows.

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

      "If there are more than one x, we assume the one that appears first is smaller." Can you explain why so?

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

        Actually, this is just an assumption to prevent some number being counted twice.

        For example, the whole sequence is +1 +1 -.

        After processing the whole sequence +1 +1 -, the final set is 1.

        When we count the first +1, we will not count the sequence +1 +1 -, cause the first +1 is smaller, according to the assumption. The 1 in the final set is the second +1, we'll count this one when processing the second +1.

        If you don't set the rule for equal elements, +1 +1 — will be counted for both +1, which is not what we want.

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

          Now I got the intution behind it! Thnx!

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

      Thanks got it!

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

    You can have a look here and the parent comment, I tried to explain it with a picture:

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

What a nice math contest!(C is really nice)

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

Brilliant Problems!! Thanks for such a nice contest.

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

Could anyone explain why I got a time limit exceed in problem B test 2?

Thank you so much.

#include <iostream>
using namespace std;

int main() {
    int tcs, tc, n, a, b, i;
    bool f;
    cin >> tcs;
    for (tc = 0; tc < tcs; tc++) {
        cin >> n >> a >> b; 
        if (a == 1) cout << (n % b == 1 ? "Yes" : "No") << endl;
        else {
            i = 1; f = false;
            while (i <= n) {
                if ((n - i) % b == 0) {f = true; break;}
                i *= a;
            }
            cout << (f ? "Yes" : "No") << endl;
        }
    }
    return 0;
}
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Someone please explain solution of D. I am unable to comprehend the tutorial solution.

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

Can anyone explain me div 2 D solution

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

when coming up with dp solutions of taskE1 would you write the initial statements first(for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;) or figure it out after the recursive statements? Because I had a hard time writing the initial statements,not knowing how many elements in the array should I initialize(Like why is s[0][0]=1 not needed). Please share some tips! and sorry for my bad English

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

I'M THE ONLY ONE FST ON D!!!!!!!!!!!!! :(

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

Let me introduce froggyzhang's idea of problem E in English. You can find the original edition here(in Chinese).

I recommend you read the first and second paragraph of the official tutorial of E2 and the official tutorial of E1 before reading the following part of this article.

Assume $$$p_{i+1}=a$$$ and $$$q_{i+1}=b$$$, $$$a,b$$$ are their rank in their permutations.

So $$$inv(p)> inv(q)\Leftrightarrow inv(p[i+2,\dots n])-inv(q[i+2\dots n]\ge b-a+1$$$. So we just want to find the number of the pairs of permutations $$$p,q$$$ of length $$$n-i-1$$$ and $$$inv(p)-inv(q)\ge b-a$$$.

Precalculate $$$f(i,j)$$$ the number of the pairs of permutations $$$p,q$$$ and $$$inv(p)-inv(q)=j$$$. You can insert the numbers to the permutation from small to big and you can do it in $$$O(n^4)$$$ or $$$O(n^5)$$$ by using brute force(which is also mentioned in the official tutorial of E2).

You will find inserting number $$$i$$$'s generating function is as follow:

$$$ \sum_{j=0}^{i-1}x^j\sum_{j=0}^{i-1}x^{-j}=\frac{x^i-1}{x-1}\cdot\frac{x^{-i}-1}{x^{-1}-1}=\frac{x^{i+1}+x^{-i+1}-2x}{(x-1)^2} $$$

About the above part we can write it in to DP functions($$$a\to b$$$ means we add the value of $$$a$$$ to $$$b$$$).

$$$ f[i-1][j]\to f[i][j+i+1]\\ f[i-1][j]\to f[i][j-i+1]\\ -2f[i-1][j]\to f[i][j+1]\\ $$$

And $$$\frac{1}{(x-1)^2}$$$ means we want to roll back twice. Just think what do you do when you $$$\times (x-1)^2$$$. So we can calculate $$$f$$$ in $$$O(n^3)$$$(both time and memory). We can only keep two layers of transition to optimize the memory to $$$O(n^2)$$$. And we can calculate suffix sum and the answer of the same prefix in $$$O(n^2)$$$.

You can read froggyzhang's code in his blog. You can find other details of coding in his code if you need.

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

In the implementation of problem D, why is the additional if (i!=t) : f[i][j]=(f[i][j]+f[i-1][j])%mod there at the end of innermost for loop? Isn't the case where we skip the ith element already considered in each case?

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

    Please read the definition of the dp statement again. It means the number of sequences for $$$x$$$ exit at last if we add option $$$t$$$ to the sequences. So that we needn't consider option $$$t$$$.

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

Can someone explain to me how the formula $$$f(n,k)=\sum_{|i|<n} f(n-1,k-i)\times (n-|i|)$$$ (from the editorial for E2) works? I don't get which "first and second permutation" is the author talking about. Thanks.

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

Can anyone explain problem D. I didn't understand the solution in editorial.

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

This is my code for Div2 D

Spoiler

Someone please provide me any small testcase for debugging.

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

Thank you! This is very helpful!

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

In Question B it is clear that every number x which is in the set is of the form 'x mod b = a^k mod b' where k is a non negative integer but how have we proven that every number of such form will be in the set?

That is how we know that the condition 'x mod b = a^k mod' is necessary and sufficient and not just necessary?

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

Hey I don't know why I am wrong answer on test 2 of Problem B. This is my submission: https://codeforces.cc/contest/1542/submission/121246560 Can you tell me what I am wrong. Thanks you

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

the D is pretty good

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

the solution of D:

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 505;
int dp[maxn][maxn];
int num[maxn];

void ini()
{
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
}
int main()
{
	int n;
	char ope;
	ll ans = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf(" %c", &ope);
		if(ope == '-') num[i] = -1;
		else  scanf("%d", &num[i]);
	}
	for(int i = 1; i <= n; i++)
	{
		if(num[i] == -1) continue;
		ini();
		for(int z = 1; z <= n; z++)
		{
			if(i == z)
			{
				for(int g = 0; g <= z; g++)
					dp[z][g] = dp[z-1][g];
			}
			else if(num[z] == -1) 
			{
				if(z < i) 
					dp[z][0] = (0ll + dp[z-1][0]*2 + dp[z-1][1])%mod;
				else 
					dp[z][0] = (0ll + dp[z-1][0]+dp[z-1][1])%mod;
				for(int g = 1; g <= z; g++)
				{
					dp[z][g] = (0ll + dp[z-1][g+1] + dp[z-1][g])%mod;
				}
					
			}
			else if(num[z] < num[i] || (num[z] == num[i] && z < i))
			{
				dp[z][0] = dp[z-1][0];
				for(int g = 1; g <= z; g++)
					dp[z][g] = (0ll + dp[z-1][g] + dp[z-1][g-1])%mod;
			}
			else
			{
				for(int g = 0; g <= z;g++)
					dp[z][g] = (2ll*dp[z-1][g])%mod;
			}
		}
		for(int g = 1; g <= n; g++)
			dp[n][g] = (dp[n][g] + dp[n][g-1])%mod;
		ans = (1ll*dp[n][n]*num[i] + ans)%mod;
	}
	printf("%lld", ans);
	return 0;
}
»
3 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

这代码写的好称头哦

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

In C it was possible calculate everything before sending solution as in my solution ,then only modulo by every long long int in vector :-)

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

i submitted 123918769 for problem[problem:1542A]. This submission is giving run time error. Can anyone please tell my mistake. Thanks in advance.