chokudai's blog

By chokudai, history, 7 months ago, In English

We will hold AtCoder Beginner Contest 161.

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

We are looking forward to your participation!

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

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

Excited for my first atcoder contest...

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

I wish it will be a perfect contest!

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

In Problem F
For N = 6
When K = 3 : 6 -> 2 -> 1
Why K = 3 is not considered in first sample?

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

    If you subtract 3 from 2, it does not become 1, it turns -1, which is not what is expected!

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

    When 3 divides 6 it changes N to N/k which is 2 and N-K,i.e., 2-3 is equal to -1 and not 1. :)

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

    for k=3

    n = 6

    1> 6%3==0: n = 6/3=2

    2> 2%3!=0: n = 2-3=-1

    it's wrong

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

      Ok, Thanks I wrongly interpreted the question, I thought that we can choose different K at each step while reducing N.

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

    Hmm, everyone is pointing out wrongly... If you choose $$$K = 3$$$, performing one operation results in $$$2$$$, which is less than K, so you don't have to consider operations one more time :)

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

Do you have a smooth network today?

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

Why does this solution fail E?

Code

If max amount of work is greater than k then the answer is empty.
Else let bottleneck day be the only day on which max amount of work is equal to j(say),search for bottleneck, it would be part of the answer, now search for bottleneck again starting from index (currentbottleneck+c+1) and repeat till i=n-1

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

    I solved E doing dpl[n + 1] and dpr[n + 1] — the max days we can work in 0...i for dpl and i...n dpr. So i will be in the answer if dp[i] + dp[n — i — 1] < k and dp[i] + dp[n — i — 1] + 1 == k and
    s[i] == '0'.Sorry for my poor English.

    Code:

    #include <bits/stdc++.h>
    #define int long long
     
    using namespace std;
     
    signed main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        int n, k, c;
        string s;
        cin >> n >> k >> c >> s;
        int dpl[n + 1], dpr[n + 1];
        dpl[0] = 0;
        dpr[0] = 0;
        int last = -10000000;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'x') dpl[i] = dpl[i - 1];
            else if (last + c < i) {
                last = i;
                dpl[i] = dpl[i - 1] + 1;
            }
            else dpl[i] = dpl[i - 1];
        }
        last = -10000000;
        for (int i = 1; i <= n; ++i) {
            if (s[n - i] == 'x') dpr[i] = dpr[i - 1];
            else if (last + c < i) {
                last = i;
                dpr[i] = dpr[i - 1] + 1;
            }
            else dpr[i] = dpr[i - 1];
        }
        //for (int i = 0; i <= n; ++i) cout << dpr[i] << " ";
        for (int i = 0; i < n; ++i) {
            int left = i;
            int right = n - i - 1;
            if (s[i] == 'o' && dpl[left] + dpr[right] < k && dpl[left] + dpr[right] + 1 >= k) cout << i + 1 << endl;
        }
        return 0;
    }
    
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    You need an else block for when indices.size()!=1: In this case, the best strategy (i.e. causes the least forced days) is to work on the earliest day $$$d^*$$$ inside indices{}, because if a future day is forced when using $$$d^*$$$ then it is also forced for any other $$$d$$$ inside indices{}, but not necessarily the other way around. After you select $$$d^*$$$, you should increment the index appropriately.

    For instance suppose you have 4 o's in a row, where the first and second have maxwork=2, and the third and fourth have maxwork=1. Then assume you work on the day with the first o. This might disqualify the 3rd o, making the 4th o forced. So you need a condition similar to your index=c+1+index1, except assuming you work on the earliest day $$$d^*$$$.

    I think something like "oooxo" with k=2, c=2 should exhibit this problem- you'll have maxwork = 2, 2, 1, 1, etc.

    Mine to compare (btw linear time with a stack instead of a set is possible) https://atcoder.jp/contests/abc161/submissions/11538625

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

      Thank you very much :D
      Moved the index=c+1+index1; part outside if statement and it worked :D

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

    Maybe the hardest thing to encounter image

    Can anyone check why this fails in one test case? https://atcoder.jp/contests/abc161/submissions/17260017

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

I think the difficulty gap from C to D is way more than expected

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

    D is bruteforce recursion, and I feel F is also much easier this time.

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

    D is not hard, just dfs.

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

      How you used dfs in it?

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

        I just generated up to 10^5 Lunlun Numbers and output the kth

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

          bro can you elaborate the above solution.

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

Video tutorials + Screencast

Screencast

Video Editorials

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

I think F is easier than D;

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

    With D a brute force works, just maintain the lunlun numbers as an array, and increment i times. That is fairly simple compared to F.

    Submission

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

      Can you explain your logic please !

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

        We store the digits of the number in an array as if written down on paper.

        Incrementation works just like that, we increment the lowest significant digit. If it runs out of scope (higest possible number), then we increment the one at one position higher, and use the lowest possible number for the digits at the lower positions.

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

Can somebody explain me logic behind problem F? I only can guess that n = (ak + 1) * b or n = ak + 1.

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

    Solution to $$$F$$$:

    If $$$N=2$$$, the answer is $$$1$$$.

    Otherwise, let's define the function $$$f(x, y)$$$ like this:

    bool f(long long x, long long y)
    {
        while(x%y==0)
        {
            x/=y;
        }
        return x%y==1;
    }
    

    Now for all $$$i$$$ $$$(i>1)$$$ which is the factor of $$$N$$$, add $$$f(N, i)$$$. Let's define this sum as $$$S$$$, and the number of factors of (N-1) as $$$T$$$. The answer is $$$S + T$$$.

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

    $$$n$$$ can be of the form $$$k^p$$$ or $$$k^p(km+1)$$$. So we can loop over $$$\sqrt{n}$$$ values to check such $$$k$$$. Here

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

      Can you please explain it with more details?

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

        Umm I mean suppose you have reached $$$1$$$ then either you reached it by dividing some other number by $$$k$$$ or adding $$$k$$$.

        Now just follow the question's operations. Note that as soon as our number is not divisible by $$$k$$$ then we may only subtract $$$k$$$. So in the first case in above paragraph, it must be that number is $$$k^p$$$. In second case, we may add any number of $$$k$$$, and after that multiply by $$$k$$$ any number of times, so that following questions sequence of operations always reduces it to $$$1$$$.

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

Can anyone reason out why adding codes for compiler optimization gives RTE ? I wasted a lot of time and attempts over it. RTE   AC chokudai ?

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

https://ide.codingblocks.com/s/205523

Why is this giving WA in B ?

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

    it should be ceil(sum/(4.0*(double)m)). you are meant to round it up to fit the requirement

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

      Thank you brother....i'm getting wa in test case 5 and 6...this thing helped me.

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

    you are dividing sum by 4*m and both of them are int, so there division gave you a rounded down int. suppose sum/(4*m) is 96.5, your code will convert it to 96 and then include all the 96s in the array which shouldn't be include as 96<96.5 . use double while dividing and then use ceil function.

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

    Line 23: if(v[i]>=sum/(4*m)), this does integer division as both sum and m are integers.

    The correct way would have been to store it in a double and then compare.

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

    Cast integers to doubles where you are doing division and comparison

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

      Better use multiplication on the left side instead of divison on the right.

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

    Change if(v[i]>=sum/(4*m)) to if(4*m*v[i]>=sum) .

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

    Use this if(((v[i]*4)*m)>=sum)

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

Could someone tell me where my code for F is wrong. Only 6 out of 25 test cases were wrong.

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

    if i is a factor then n/i is also a factor.U missed to check for n/i in the first for loop.

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

    You are printing twice when n=2

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

      I accidently removed return in the if condition while debugging.

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

D OEIS but for the first 1k only :v .. waiting for English editorial and thanks for the round

EDIT: video editorial

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

In D I used binary search + digit dp. It took me a lot of time to implement that :/// solution link

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

    Can you explain please what dp[12][N][2][2] in your code means?

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

      You may check the digit Dp article if you don't know about it.

      Digit DP

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

      yeah sure,

      first dim means — the last digit that is used

      second dim means — the length of number iterated

      third means — the lower limit is fixed or not (this one is not required as lower limit is always one)

      fourth one — if upper limit is fixed or not

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

    Wow, Thank you!

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

    Same here. D was a bit tough for me while F was much easier. It took me 25 minutes to solve D with BS+digitdp and just 7 minutes in F.

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

What am I missing for D? 100000 case doesn't work.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());

        HashSet<Long> set = new HashSet<>();
        LinkedList<Long> q = new LinkedList<>();
        for (long i = 1; i <= 9; i++) {
            q.add(i);
            set.add(i);
        }

        if (k <= 9) {
            pw.println(k);
            pw.close();
            return;
        }

        while (!q.isEmpty()) {
            long head = q.poll();
            for (long i = head % 10 - 1; i <= head % 10 + 1; i++) {
                if (i < 0) continue;

                long val = head * 10 + i;
                if (set.contains(val)) continue;

                set.add(val);
                q.add(val);

                if (set.size() == k) {
                    pw.println(val);
                    pw.close();
                    return;
                }
            }
        }

        pw.close();
    }
}
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Never mind, I figured it out. When the last digit is 9, the queue puts in a 0, bc (9 + 1) % 10 = 0

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

Can someone describe how to solve D? Was it dp digits?

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

    My approach for D was a bit different. I had a set $$$s$$$ which would store all possible answers for all $$$K$$$. Now I had an integer $$$z$$$, such that the next numbers to be added to $$$s$$$ were $$$z*10+d-1$$$, $$$z*10+d$$$, $$$z*10+d+1$$$, where $$$d=z(\mod 10)$$$. Note that $$$z$$$ $$$\epsilon$$$ $$$s$$$ $$$\forall$$$ $$$z$$$. Hence I incremented $$$z$$$ by $$$1$$$ and set $$$z =$$$ *$$$s$$$.lower_bound($$$z$$$). I continued this until size of $$$s<=K$$$. Then I just printed the $$$K$$$ th element of the set.

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

    I solved it using bfs. Here is my solution

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

    I used simple BFS.

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

    I did it using simple bfs.

    link to submission

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

    You can solve with bruteforce, just store Lunlun numbers in an array.

    Then check the last digit of i'th entry, let it be x. Then for next position, you can have digit -> x-1, x and x + 1.

    For example: Initial array : [1, 2, 3, 4, 5, 6, 7, 8, 9]

    Consider you are at 1 -> 10 , 11, 12. Then increase the pointer after you try all consecutive of current entry.

    Now do same for 2-> 21, 22, 23.

    and keep adding them in the array. You can implement it recursively as well as iteratively.

    Iterative

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

    BFS can solve the problem.

    int n,cnt;
    void solve(){
    	cin>>n;
    	queue<string> q;
    	rep(i,1,10)q.push(to_string(i));
    	while(1){
    		int m = q.size();
    		for(int i=0;i<m;i++){
    			string s = q.front();
    			q.pop();
    			if(++cnt==n){
    				cout<<s;
    				return ; 
    			}
    			if(s.back()=='0')q.push(s+'0'),q.push(s+'1');
    			else if(s.back()=='9')q.push(s+'8'),q.push(s+'9');
    			else q.push(s+(char)(s.back()-1)),q.push(s+s.back()),q.push(s+(char)(s.back()+1));
    		}
    	}
    }
    
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong with the following code for problem B?

    int n,m;
    cin>>n>>m;
    int tot = 0;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++) {
    	cin>>arr[i];
    	tot+=arr[i];
    }
    sort(arr.rbegin(),arr.rend());
    int req=tot/(4*m);
    int cnt = 0;
    for(int i=0;i<n && cnt<m;i++) {
    	if(arr[i]>=req) {
    		cnt++;
    	} else break;
    }
    if(cnt>=m) cout<<"Yes";
    else cout<<"No";
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try making req into a double: double req=(double)(tot)/(4*m);

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

I think this contest is more difficult than before.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;

int main(){
  long long n,k;
  cin>>n>>k;
  long long N=n;
  long long mn=1000000000000000000;
     while(n>=0){
        mn=min(n,mn);
        if(n<k){
            n=k-n;
        }
        else{
            n=n-k;
        }
        if(n==mn){
        mn=min(n,mn);
            break;
        }
     }
     cout<<mn;

   return 0;
       }

i was getting tle. Can anyone help me ?

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

    For small k and big n the loop will run n/k times, wich then is to slow. You can speed this up by using mod operations.

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

      i tried but it was showing error.

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

      oh yes. thanks. i tried to make both conditions using mod but the k>n condition was giving error. But why? can you please explain ?

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

        I think there are a lot of possible implementations. The basic aproach is the same for all: For big $$$n$$$ and small $$$k$$$ the loop is shortened by removing a multiple of $$$k$$$ in one step.

        My Submission

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

          Hey man appreciate it. thanks for helping me.

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

So,how to solve the problem D?

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

    If you were to generate all numbers, it'd be something like this:

    vector<long long> num;
    void brute(int i, int last, long long cur){
        if(i == 0) return;
        num.push_back(cur);
        if(last > 0) brute(i-1, last-1, cur * 10 + last - 1);
        if(last < 9) brute(i-1, last+1, cur * 10 + last + 1);
        brute(i-1, last, cur * 10 + last);
    }
    

    Where $$$i$$$ is the maximum number of digits, $$$last$$$ is the last digit you used and $$$cur$$$ is your current number.

    Then, you can use nth_element or sort to get $$$k-1$$$ smallest.

    But why does this work? Well since there are only 3 transitions, complexity would be $$$O(3^D)$$$ where D is the maximum number of digits. Turns out answer will have not more than 12 digits so you can just brute force it =p.

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

    You can approach that problem by using backtracking. Let's say you have a lunlun number x, you can find another lunlun number by taking the last digit of x which is d = (x%10) and appending d, d+1, d-1 to x. Then you keep doing the same on the new lun lun number. Also you have to keep in mind that initially you have start with all the single digit numbers. You can imagine the tree as 0 at the top and the root node, the from that emerges 9 branches to 1, 2, 3, 4, 5, 6, 7, 8, 9. Then from each one of them will emerge at most 3 branch. Like from 2 we will have 21, 22, 23. And so on.

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

So how to solve E?

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

    Let's define dpl[i] as the max number of days that we can work in first i days, and define dpr[j] as the max number of days that we can work in last j day. The size of both arrays is n + 1. We can precalculate dpl and dpr greedy, base: dpl[0] = 0, dpr[0] = 0, last = -inf. Then iterate from left to right, keeping last as last day when he worked. Same for dpr.

    If day i is in the answer, then s[i] == 'o'(Im counting days from 0 to n — 1) and dpl[i] + dpr[n — i — 1] < k and dpl[i] + dpr[n — i — 1] + 1 == k(may be its useless condition). Time complexy: O(n) Code:

    https://atcoder.jp/contests/abc161/submissions/11534466

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

      Thank you very much, nice explanation.

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

Please atcoder! can you make english editorial.

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

    Or if someone just translates the existing one to English.

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

can anyone explain the d part and what is written in the editorial of d in japanese

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

    This problem can be solved efficiently using Queue.

    Prepare one Queue and Enqueue 1, 2, ..., 9 in order. Then do the following K times:

    • Dequeue the Queue. Let x be the extracted element.

    • Let d = x mod 10.

    • if d = 0. Enqueue 10x, 10x+1.

    • if d = 9. Enqueue 10x + 8, 10x + 9;

    • else Enqueue 10x + d-1, 10x + d, 10x + d + 1.

    Kth extracted element will be the answer.

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

      Above is what you get if you translate the Japanese editorial for D.

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

      Damn that's such a clean solution

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

      thanks man!!

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

    The same idea:

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

It's harder to understand the editorial than to understand the problem statement. (Since the editorial is in Japanese ! )

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

can anyone plz explain the logic behind E??

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

My submission for problem 'D' is giving Runtime error on sample test cases on Atcoder but this code is working fine on Codeforces custom invocation.

I tried to cut-short the code to find my mistake but still, I can't find my mistake, Here is the link of a very short and clean code which should give WA but is giving RE instead. Can someone help me find the mistake in either of the code?

Edit: It got accepted when I removed lines 8 to 12 (pragma tags) but I am still unable to understand why including pragma tags is giving RE here

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

Supplementary editorial and sample codes for last 4 problems AtCoder ABC 161

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

why this code is giving TLE for question F

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll func(ll n,ll x)
{
    while(n%x==0)
        n/=x;
    if(n%x==1)
        return 1;
    else return 0;
}
int main()
{
	ll t;
	t=1;
	while(t--)
    {
        ll n;
        cin>>n;
        ll s=0;
        for(int i=2;i*i<=(n-1);i++)
        {
            if((n-1)%i==0)
            {
                s++;
                if((n-1)/i != i)
                    s++;
            }
        }
        ll c=0;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i==0){
                c+=func(n,i);
            if(n/i != i)
                c+=func(n,n/i);
            }
        }
        cout<<c+s+2;
    }
}

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

    use long long for i instead of int

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

      thanks but can u tell me why it was giving tle earlier

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

        i*i becomes negative when overflowing so the for loop will become an infinite loop

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

I find a data that someone can not pass for Problem E 5 2 1 oxooo the result is empty,but someone will out 1

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

Here is the code

include<stdio.h>//----1

int main(void){//------2 long int n,k,t;//----3 scanf("%ld%ld", &n, &k);//---4 t=n%k;//-----5 if(2*t<k){//-----6 printf("%ld", t); } else{ printf("%ld", k-t); } return 0; } i do not understand the line 5 and 6.why i use this condition ????please anyone explain it??? thanks in advance

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

Whats wrong in this solution for problem 'Replacing integer' . I have even gone through editorial solution.Its same as mine.Whats wrong here..Please someone look at this

https://atcoder.jp/contests/abc161/submissions/11572033

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(a[i]>=(sum/(4*m)))
    

    Instead of dividing on the right you better multiplicate on the left side, to avoid rounding issues.

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

      I am talking about this solution..Please help with below https://atcoder.jp/contests/abc161/submissions/11572033

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

        check output for n = 14, k = 15. Correct output is 1. Your program prints 14.

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

          Thanku so much brother..Really appreciated..Thanks..Done

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

      Will u please see my solution of E.My solution is same as editorial. but i dont understand what the hell is wrong here?? pls look at this.
      thanks in advance
      https://atcoder.jp/contests/abc161/submissions/11577640

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

        I think the editorial means the size of array is K , here is My code ,the idea is the same with editorial.it's easy to understand ,hope it will help.

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

https://atcoder.jp/contests/abc161/submissions/11592729

what is the problem in this submission for problem C?

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

my code for problem no D(lunlun number):

include<stdio.h>

include<math.h>

long long int a[1000001],rem[100000001]; int main() { int n,i,j,k=1; scanf("%d",&n); for(i=0; i<9; i++) a[i]=k++; long long int x=9,cnt,flag,num; for(i=9; i<n; i++) { num = ++x,cnt = 0,flag = 1; while(x!=0) { rem[cnt++]=x%10; x/=10; } for(j=cnt-1; j>0; j--) { if(abs(rem[j]-rem[j-1])>1) { flag=0; break; } } if(!flag) { i--; continue; } else if(flag == 1) a[i]=num; } printf("%lld\n",a[n-1]); return 0; }

can anyone please tell me where I have made the mistake? I am getting CE for this code.

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

try to do the D with brute force but when it arrives I give the number 37 input the outputs start to be wrong. Could someone help me find the fault? Solution

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

Why do I get WA? Here's my code for problem E.

I'm looking for a savior.

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

    Your code gives wrong answer on oxooo with N=5,K=2 and C=1. In first iteration you are marking index 0 and 2 as true. In second iteration you are marking index 4 and 2 as true. And printing three as 2 come in both the iterations. However the i'th day should be same in both the iterations. Only then we can count it in our answer.

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

Hi! Not getting the logic of Solution D in the editorial. It's hard to come up with that kind of solution. Can anyone share other ways to do it? Thanks.

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

Can someone please help me...my two testcases are failing in problem B(The popular vote)

i even read the editorial solution...i can't figure out where my mistake is happening?

my code

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

I do not understand in problem E, why do we have to take the days greedily from left and right. Problem