chokudai's blog

By chokudai, history, 4 months ago, In English

We will hold AtCoder Beginner Contest 179.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +79
  • Vote: I do not like it

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

Front row!

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

"We are looking forward to your participation!"

We are looking for quick editorials.

P.S. I love ABC's.

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

What are the ALC contests of Atcoder?

Edit: It's is described in this blog

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

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

I tried a DP solution for D. Somehow getting TLE in 6 TCs. I tried to optimize it as much as I could. Am I missing something?

Link to Submission

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

    post qns only after contest is over.

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

    i used fenwick tree to optimize it, note that k <= 10, your solution fails because ranges can be very big, so your solution is n^2

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

      But the sum of ranges won't be more than O(n) I suppose. Because the segments are nonintersecting.

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

        Yes, the sum of ranges is $$$O(n)$$$, but you also have $$$O(n)$$$ states and for each, you iterate through all of them. In total it is $$$O(n^2)$$$.

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

      I used a presum array to find the sum of dp in previous ranges.

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

    you can try it in O(n*k). Refer to below link for reference.

    https://www.geeksforgeeks.org/constant-time-range-add-operation-array/

    My Submission

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

    your code runs in O(K*N) where K is the number of possible jumps, theoretically in worst case it would reach O(n^2) time complexity which could defenitely get TLE. In this problem i used dynamic programming with fenwick tree, you can look at my code here

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

    For d, you have to combine the dp you are talking about, with the range covering problem (it is easier than segment tree I leave you this video in which that guy explains that problem https://youtu.be/Zze-O2oxoEo?t=219 ) and then you just have to be careful about modulo operations (you might be doing them with negatives)

    I hope this was useful

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

      Thanks for this. I checked out the video. Isn't what he is talking about, called the Fenwick tree?

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

        No, Fenwick tree is a little more complex than that, it is about having sum until last significant bit and when doing a query going up from last significant bit to most significant bit (with a complexity of logn) and when updating is almost the same, but instead of getting an answer, updating; that is why it is also called Binary Indexed Tree

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

    My code is similar with yours and I wonder how to optimize it too. [submission:#17148205]

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

Loved solving E !

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

    How to solve ?

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

      Its running a while loop until you face one among three situations,

      i) when x becomes 0 (once x becomes 0, the following numbers will be 0 too)

      ii) when count==n (it means you no more needed to continue evaluation)

      and the third observation is probably the challenging one

      iii) once you see any x repeating then come out of the loop, because you know the following numbers repeat too

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

        i used the same thing can u plz tell whats wrong with my solution `string solve(){ ll n,x,m; cin>>n>>x>>m;

        vector<ll> vec;
        vec.push_back(0);
        set<ll> s;
        ll num=x;
        ll sum=0;
        ll count=0;
        while(s.count(num)==0){
            vec.push_back(num+vec.back());
            s.insert(num);
            sum+=num;
            num=(ll)power(num,2,m)%m;
            if(num==0) ret(sum);
            count++;
            if(count==n) ret(sum);
        }
        
        
        ll times=n/count;
        ll rem=n%count;
        ll ans=times*sum;
        
        ret(ans+vec[rem]);
        

        }`

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

First time in ABC I was able to solve all problems. Here are short explenations.

F
E
D
C

Funfact, I had no WA, all AC on first submission.

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

    For d instead of segment tree + dp you can use prefix array + dp.

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

      please share your code

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

          plz give a brief explanation also. thnx

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 5   Vote: I like it +3 Vote: I do not like it
            Basic
            Solution
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You don't really need a segment tree for D
    I just used prefix sums

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

    D and E should have been swapped ,I didn't even attempt E after continuous TLE's in D .

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

      D is more difficult in terms of the idea I guess

      E is heavier in terms of implementation

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

      even i think so

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

    You don't need segment tree for F either.

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

      can you explain your approach for F

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

        I'm more than a month late, you may have got the answer till now, but here is what I think the approach is:

        Here two sets are used to maintain position of lines of white stones. There are two kinds of lines length wise :

        1. Partial lines(going from one end and ending halfway)

        2. Complete lines (going from one end to other end)

        There are two kinds of lines possible orientation wise :

        a) Horizontal Line - Can be stored as $$$y$$$ co-ordinate it starts on and $$$x$$$ co-ordinate it ends on.

        b) Vertical Line - Can be stored as $$$x$$$ co-ordinate it starts on and $$$y$$$ co-ordinate it ends on.

        Now what exactly those two sets do, set[0] stores position for horizontal lines, and set[1] stores position of vertical lines.

        Formally a pair stored in respective sets looks like:

        • s[0]= (Ending abscissa, originating ordinate)
        • s[1]=(Ending ordinate, originating abscissa)

        Note that at the start we only have two complete lines, one horizontal and one vertical that's why a pair $$$(n,n)$$$ is stored in both the sets.

        • Query 1 We search for nearest horizontal line we can find that ends after $$$x$$$, and thus add remove black stones in that interval from the answer accordingly and now one vertical line is created in the process that starts at $$$x$$$ and ends just before the horizontal line we found.

        • Query 2 Search for nearest vertical line, remove black stones in that range from the answer and add a horizontal line in the corresponding set.

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

    F: you can use std::map for the same query (lower_bound to find closest) Submission

    D: you can use only partial sums of your dp and fill dp[i] with sum of previous values Submission

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

      Can you explain your approach for F?

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

    I also thought of using segtree with lazy prop on F, but I had no segment tree template with lazy propagation :P and I had only 35mins left. So I quit. Missed my chance of solving all problems in ABC for the first time.

    I'm taking your template now XD.

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

      I also got idea of two lazy segment tree immediately but I haven't implemented even a basic lazy segment tree before so I gave up. Now I am seeing there are other solutions too

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

      I had to fix a bug in that template in function rangeInc(). Not sure if everything works fine.

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

        Oh,thanks for informing. I'll test it properly after customizing it for myself. :)

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

          In AtCoders ACL library there is a segment tree, too. I would like to switch to that one, but need time to get used to it.

          ACL lib

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

      Question: I thought that we should need to be able to get the historically minimum of some certain index? Won't that be more than just a plain old segtree?

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

    I got tle in this, could you plz tell me why?

    int ans = 0;
    for(int i = 1 ; i <n; i++){
    	int x = n-i;
    	for(int j = 1; j*j<=x; j++){
    		if(x%j == 0){
    			ans++;
    		if(x/j != j){
    			ans++;
    		}
    		}
    	}
    }
    // ans += ans;
    cout << ans ;
    
    • »
      »
      »
      4 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      You have asymptotic of $$$O(n \sqrt{n})$$$ which is too big. You can enumerate only the smallest number of $$$A, B$$$ which would be $$$\sqrt{n}$$$ and calculate how many multipliers bigger than your number you can have such that $$$A \times B$$$ is smaller than $$$N$$$.

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

      n is 1e6, so the inner loop runs up to 1e3 times... that are aprox 5e8 iterations.

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

    spookywooky — Love the way you add inspiring quotes to your code.

    /**
     * Dont raise your voice, improve your argument.
     * --Desmond Tutu
     */
    

    Link : https://atcoder.jp/contests/abc179/submissions/16871292

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

    Can you please elaborate solution of D a little?

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

    Me too for the first time solved set in any contest lol

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

    every time i used to fight myself to solve at least 3. But u guys are solving all.

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

    Can you please further explain how did segment tree help with this problem? I know segment tree but I cannot utilize it to solve this problem.

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

      I assume problem D.

      If we would do standard knapsack we would need to loop over all the values in the K ranges, which is O(n).

      With the segment tree we are able to do these updates in O(log n).

      Note that the solution with the partial sums do these updates in virtually O(1). see here

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

        Thanks a lot:) you always provide useful insights

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

    correct me if I am wrong, the time complexity of your D solution is N*k*log(n) and not N*log(n) which the editorial says is the optimum

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

      Yes, you are right. Because of this my submission needs 800+ms instead of possible 10ms.

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

How to solve problem D?

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

    I solved it without segment tree

    I used difference array. Time complexity of $$$O(N*K)$$$

    basically let dp[i] be no of ways to each i.

    Then you increment, $$$i$$$+$$$L_j$$$ to $$$i$$$+$$$R_j$$$ with dp[i], increment using difference array method, and keep summing as you move toward right.

    The answer would be dp[n]

    Submission

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

      Hello , I thought D problem is same as Coin Combinations I as expected get TLE for that.Anyway to improve my solution? My submission is here

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      n, k = map(int, input().split())
      dec = {}
      mem = {0: 1}
      for i in range(k):
          l, r = map(int, input().split())
          dec[l] = 1
          dec[r] = 1
      dec = list(dec)
      for i in range(1, n):
          ans=0
          for j in dec:
              ans += mem.get(i-j, 0) % 998244353
      
          mem[i] = ans
      print(mem[n-1] % 998244353)
      

      please can you tell where am i doing wrong

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

    I solved it maintaining a prefix sum array and using dp.

    dp[i] = sum of dp[j] for all j, i is reachable. As the range was contiguous it was easy to get the sum of dp[j] using prefix sum.

    My Sumbission

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

      could u plz explain more

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

        Here dp[i] is the number of ways to reach i.

        dp[i] was calculated by the sum of dp[j] for all j from where i is reachable. Assume i = 4 and i is reachable from 2 and 3. If the number of ways to reach 2 is 1 aka dp[2] = 1 and the number of ways to reach 3 is 2, dp[3] = 2 then dp[4] = dp[2] + dp[3] which is dp[4] = 3 (rule or sum)

        And for any i corresponding js were calculated from the ranges and their sum was calculated from the the prefix sum array. For any position iand a range L, R i is reachable from all valid i-R, i-L.

        Finally the answer is dp[n].

        Complexity O(N*K)

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

I got runtime error in sometest cases in prob D with segtree can somebody help me? https://atcoder.jp/contests/abc179/submissions/16889464

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
void test_case() {
	int n , x;
	cin >> n >> x;
	for(int i = 0 ; i < 2*x ; i++){
		int p;
		cin >> p;
		c.insert(p);
	}
	dp[1] = 1;
	for(int i = 2 ; i <= n ; i++){
		for(auto j : c){
			if(j <= i){
				dp[i] = (dp[i]%M+dp[i-j]%M)%M;
			}
		}
	}
	cout<<dp[n]%M;
}
 

what WA in my D https://atcoder.jp/contests/abc179/submissions/16888327[my sol link](http://https://atcoder.jp/contests/abc179/submissions/16888327)

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

    they want you to union the segments [Li,Ri] i mean {Li,1+Li,2+Li,3+Li,....,Ri} not only values {Li,Ri}

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
string solve(){
	ll n,x,m;
	cin>>n>>x>>m;
	
	vector<ll> vec;
	vec.push_back(0);
	set<ll> s;
	ll num=x;
	ll sum=0;
	ll count=0;
	while(s.count(num)==0){
		vec.push_back(num+vec.back());
		s.insert(num);
		sum+=num;
		num=(ll)power(num,2,m)%m;
		if(num==0) ret(sum);
		count++;
		if(count==n) ret(sum);
	}
	
	
	ll times=n/count;
	ll rem=n%count;
	ll ans=times*sum;

	ret(ans+vec[rem]);
}

** what is wrong with this code for the problem E **

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

It`s the first time I AK abc! LOL

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

I tried to solve D by repeating knapsack dp approach with time complexity O(N*m).But TLE destroyed my today's contest.Can anyone help me with that?

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

    D can be done in O(n*k).

    Use range update operation on array, it will take O(n) for each range.

    My submission

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

      Can you elaborate this part?

      if(i+range[j].F<=n) temp[i+range[j].F]=(temp[i+range[j].F]+dp[i])%M; if(i+range[j].S+1<=n) temp[i+range[j].S+1]=(temp[i+range[j].S+1]-dp[i]+M)%M;

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

        Suppose you have array 1 2 3 4 5 You want to add 2 from position 2 to 4 [1 based-indexing) You can take a temp array and make temp[2]=2 and temp[5]=-2

        Now you can iterate over array and take sum+=temp[i]

        And add sum to a[i] . You can get the required array after update in O(n) this way.

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

This is for C: Here we have simply calculate number of factors of (n-c) where 1<=c<n a*b + c=n =>a*b=n-c;

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

Eagerly waiting for geothermal's editorial.

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

Hello in D no I used the similar pattern of dp like CSES-Coin Combinations I. but get TLE from that.Isn't it the similar pattern problem.

My solution is here

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

    Thats' so because the time complexity of your solution is O(n*n).

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

      I thought it's like Coin Combinations I problem.My bad.How can I solve it using dp ?

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

        Well, usually i solve 4-5 problems in ABC contest but today i was able to solve only the first three!

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

Could anyone please explain the 1 testcase this is failing on? I have tried to find a cycle and then adding to the sum the sum of that cycle and then adding the rest seperately.Submission

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
//Beginner
Problem E Runtime Error for few cases accepted for others!
please help me why?


Your code here...`` ~~~~~


~~~~~ Your code here...
include<bits/stdc++.h>
using namespace std;

unordered_map<long long, long long> mp;

long long func(long long x, long long n, long long mod) {
	if (n == 0)
		return 0;

	if (mp.find(x) != mp.end())
		return mp[x];
	// cout << x << endl;
	long long ans = x + func((x % mod * x % mod) % mod , n - 1 , mod);
	return mp[x] = ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long n;
	long long x, m;
	cin >> n >> x >> m;
	long long ans = func(x, n, m);
	cout << ans;
}

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

how to solve D? someone with good explanation?

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

    You can use this dp: dp[i] means how many ways do you have to go to the i-th cell.

    Let's get an array of long long dp[2n]. First we fill it with zeros. Denote the sums[2n] as prefix sums array of dp.

    1. dp[n] = 1, sums[n] = 1

    2. for each cell from n+1 to 2*n and each segment (l[j], r[j]) we calculate: dp[i] = (mod + dp[i] + sums[i - l[j]] - sums[i - r[j] - 1]) % mod

    You can understand that part as: to get how many ways I have to go to the i-th cell, I should sum the ways from all dp[the previous one, from which you can get into this].

    The value sums[i - l[j]] - sums[i - r[j] - 1] gets us sum: dp[i - r] + dp[i - r + 1] + ... + dp[i - l]

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

how do you solve c? I got TLE my solution is only O(n^2)

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

    $$$O(N^2)$$$ is too large for $$$N=10^6$$$.

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

      How can i know that it's large or not?

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

        You just put N into the time complexity expression and evaluate it. Generally speaking, $$$10^7$$$ is totally acceptable, while $$$10^8$$$ can be a bit dangerous (on some OJs it cannot pass), and $$$10^9$$$ is almost impossible to pass the time limits.

        However, sometimes we also need to consider the constant, which is omitted in the time complexity expression.

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

    can somebody please explain the logic for c.

    n = int(input())
    cnt = 0
    for i in range(1, n):
        cnt += (n - 1) // i
    print(cnt)
    
    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Since N is fixed, we don't need to enumerate all possible triplet of (A, B, C), we only need to enumerate (A, B) and compute C accordingly. Such method can be improved by enumerating only A and find the upperbound and lowerbound of B. All the values between lowerbound and upperbound are valid B. Note that B should be integer.

      $$$0 \lt A \cdot B = N - C \lt N \implies 0 < B < N/A$$$

      N = int(input())
      ans = 0
      for A in range(1, N):
          lb = 1
          ub = math.ceil(N / A) - 1
          ans += ub - lb + 1
      print(ans)
      
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can solve C in O(n) or O(nlogn) time complexity.Both of them will pass pretty convincingly.However the nlogn version would require a bit of precomputation You can refer to my O(nlogn) solution (I use Java)

    https://atcoder.jp/contests/abc179/submissions/16892756

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

I believe F can be solved using monotonic set

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

Can any one help me figure out how to solve D using recursive dp? I do not quite understand the iterative dp solution.

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

I have written an unofficial English editorial.you can find it here.

UPD: Added editorial for problem F.

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

    In the explanation for C : Could you please explain how the number of ways of choosing is N/A ?

    I have tried to do it on paper but couldnot come up with the intution.

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

      It should be $$$\frac{N - 1}{A}$$$ fixed it now, thanks for notifying me.

      The reason for that is for every $$$A$$$ there can be $$$\frac{N}{A}$$$ numbers for be such that $$$ A \times B \le N$$$, however we should subtract $$$1$$$ because $$$C$$$ can't be equal to zero.

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

For problem C i counted the number of factors of n-c In order to precompute number of factors for numbers in range [1,1e6]. I tweaked seive like this:

vi factorize (vi v){
	v[0]=0; 
	v[1]=1;
	for(int i=2;i<N;i++)
		v[i]=1;       //counting 1 as a factor for all numbers>=1
	for(int i=2;i<N/2;i++)
		for(int j=i;j<N;j+=i){
			v[j]+=1;    
		}
	return v;
}

But it may accidentally have worked for first two cases but didn't work for n=1e6(The last sample case) please help me find where did it went wrong?

Thank You in advance

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

    My solution was quite similar to yours.You can check my solution for reference(I use Java) https://atcoder.jp/contests/abc179/submissions/16892756

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

    Can you link your submission for that problem

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

      I couldn't debug this so i didn't submit :(

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

        You can check my solution.

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

          Nice solution. orz

          Can you please explain the while(num>1) part in your solution?

          Thank You

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

            if num<=1 then the number has no prime factor.So as long as it greater than 1 the loop will run.

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

              So you're using this formula am I right?

              Let n = (p1^a1)*(p2^a2)*...(pn^an) where p1,p2,..,on are prime numbers And a1,a2,..,an are powers of primes Then number of factors of n = (a1+1)*(a2+1)*(a3+1)*...*(an+1)

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

                Yes I am using this formula to count the number of distinct divisors and add to the count.

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

                  Yes Thank You very much for helping me.

                  I didn't want do it this way it's tedious to code and prone to error because I am bad at programming(I knew the formula but couldn't have implemented it the way you did it). So I tried to go around in order not to implement it and couldn't solve it.

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

                  Welcome.You can follow CodenCode NumberTheory lectures to get better at solving these type of problems.I am learning from there.

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

                  Thank You

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

UPD: Corrected ...at the time of init of seg tree i increased size by(n+2)

Problem D just failing one testcase...can anyone help me out ?? I applied segment tree in this code..

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

Problem D was quite interesting.

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

Can E be solved with Matrix exponentiation??

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

I tried to solve E,but for some unkown reason,I got two RE.

Can you help me?

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

I couldn't even understand D,

Please correct me if I am wrong in my Interpretation:

We are given K ranges. After union of all those segments, we will have distinct distances.

So we need to find number of ways to reach from 1 to N using these distances.

Please help me

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

Editorial D

How to solve in O(nlogn) when the transitions cannot be written as a sum of small number of segments?

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

    Wondering the same thing, please let me know if you find the answer.

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

    [ignore this, too much complex]

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

    let $$$J$$$ be the set of possible jump lengths, now $$$ J = \cup[l_i,r_i] $$$

    Now we can use generating function $$$ G $$$ to define that set.
    $$$G = \sum_{i=0}^N c_i x^i $$$ where $$$ c_i = 1$$$ if $$${i \in J}$$$ else $$$c_i = 0$$$.

    Now, number of ways to reach from $$$1$$$ to $$$N$$$ using exactly $$$k$$$ jumps = $$$[x^{N-1}] G^k$$$.

    As there is no restriction of jumps,so we sum it over all possible $$$k$$$.
    so, finally what we need is $$$[x^{N-1}]\sum_{k>=0} G^k = [x^{N-1}]\frac{1}{1-G}$$$

    now coefficient of $$$ x^{N-1} $$$ in the polynomial $$$\frac{1}{1-G}$$$ can be easily calculated by calculating inverse of polynomial $$$ 1 - G $$$ restricted to max degree $$$N$$$.

    Overall complexity is $$$O(N\log{}N)$$$

    For calculating inverse of polynomial you can refer Operations on polynomials and series

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

Editorial F

Could anyone help me understand the approach. I am not able to get it. Thanks!

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

I am getting stuck in mod operations. Getting WA for few cases. Can someone take a look at the mod operation and let me know if you find the error.

Link to my submission: https://atcoder.jp/contests/abc179/submissions/16925676

Thanks!

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

ABC turning into AGC :/

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

How to apply binary search to D?

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

In problem C, why is this #b =(n-1)/2. Precisely, why we have to subtract 1?

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

I could not understand the editorial of the problem C.Can anyone explain it?