chokudai's blog

By chokudai, history, 9 months ago, In English

We will hold AtCoder Beginner Contest 171.

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

We are looking forward to your participation!

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

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

Starts in 5min

»
9 months ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

I was just trying to cheer up.

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

    Maybe a little bit to exited for a contest that happens once a week. :)

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

      come on .. If you can't solve, then that's good you will learn something / discover some new trick !

      PS: cant solve F

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

Excited but cant solve more than two

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

    cant solve more than 3 ;( help, please

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

    It's better to solve question, learn new ago. , data structure rather than saying cant solve question more than 2...

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

I know this time E was actually easy, but the first time I solve E, I am unable to solve C, I'm so sad.

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

    I can't solve C either until I use cin cout instead of scanf printf :(

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

      I already am using cin, cout. Also this can be a potential hint, you should avoid telling anything like that during contest

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

    I thought I was the only one.

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

Damn F is tough. I solved the first five in 15 minutes. Couldn't solve the F one tho :(

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

E is the new D

»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

has someone solved d. can it be solved without segment tree

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

    I'll reply after the contest.

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

    yes

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

    Why to use chainsaw when work can be done with butter knife!

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

    Yeah you store the values of the array in a frequency array , refer to this https://atcoder.jp/contests/abc171/submissions/14566151

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

      Heyy, can you please tell why Your text to link here... is getting accepted and not Your text to link here...

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

        You used ints instead of long longs, as was said in the question that S_i may not fit into a 32-bit integer

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

          I used long longs for only variable 'sum' , isn't that sufficient?

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

            Why don't you try using long longs for b c and temp?

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

              Because in the question , the constraints for b,c,temp are under 10^5....hence int is enough

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

                well count*c may overflow as count can be all the elements of the array i.e. n and then and if c was 10^5 then you'd get overflow

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

                  ohh true that....my bad Thank you so much bro

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

    Yes

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

    Yes It can be solved using map

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

    it can be solved using hashmap

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

    https://atcoder.jp/contests/abc171/submissions/14563862

    Here is my solution .. let me know if you need any explanation

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

    Yea use map and store total sum , and then for each query sum-(b* count(b))+(c*count(c))

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

    Yes it can be solved without segment tree My approach

    1) Keep track of current sum of total elements

    2) Keep track of numbers of all the integers in array (i.e in array {1,2,1,3,1,,2,3,4} a[1] = 3, a[2] = 2, a[3] = 2, a[4] = 1. And current sum = 14.

    3) Than for each query update update the sum as

    sum = sum + (number of element in a[first number]) * (second number — first number)

    4) than change the array a at appropriate indices

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

    Segment tree is way overkill. It is actually quite simple. ARR[100005] stores the number of occurrences of each number in V[N] (V is the inital array given in the input). SUM stores the current sum of all elements. Then you encounter a query for example (1, 2). You know you should change all 1's into 2's. So just do S -= ARR[1] (coz 1's no longer exist). then S += ARR[1]*2 (coz all 1's are now 2's). And then ARR[2] += ARR[1] and ARR[1] = 0.

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

    Don't discuss during running contests.

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

    Use Map

»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

after contest ended,, can anyone provide the solution of C and E please.. I first-time attended and solved a,b,d. trying c and e for almost 50 minutes..

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

      its showing my submission..i think now i canot see your solution..your solution with c++ ? then provide here please

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

    E was Easy

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

    I got confused around base and modulo in C, waiting for editorial

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

    C:

    Hint

    E:

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

    For E:
    Observe that you can get value of ith scarf if you xor all a[j] (where, 0<=j<n and j!=i). But if you calculate all values like this, then complexity will be O(n*n), so what you can do to optimise is calculate any ith scarf value using method described above(say value of 1st scarf) and xor it with a[i] (here a[0]) , it will give us xor of all scarf values(say x). Then you can use this value(x) and xor it with each a[i] (for 0<=i<n) to get ith scarf value. My solution : Solution
    C is just calculating column name in a spreadsheat for given row(N) ,refer this : GeekForGeeks

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

    CODE WITH THE MAIN FUNCTION.INCLUDE THE HEADER YOURSELF TO MAKE IT WORK C code: `````````````````````````````````````````````````````````````````````````````````````````` int32_t main() { int n;cin>>n; string ans=""; while(n>0) { int d=n%26; if(d==0) d=26; ans+=(char)(d+'a'-1); n=n-d; n=n/26; } reverse(ans.begin(),ans.end()); cout<<ans<<endl; } ```````````````````````````````````````````````````````````````````````````````````````````````

    E code:

    ````````````````````````````````````````````````````````````````````````````````````````` int32_t main() { int n;cin>>n; vectorarr(n);

    int x=0; for(int i=0;i<n;i++) { cin>>arr[i]; x=x^arr[i]; } for(int i=0;i<n;i++) { int ans=x^arr[i]; cout<<ans<<" "; } cout<<endl;

    } ``````````````````````````````````````````````````````````````````````````````````

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

what is the logic for problem D

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

    Basically, keep a map which has the count of all numbers occurring in the array, and after each query, update the map. My submission-https://atcoder.jp/contests/abc171/submissions/14549573

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

Please don't ask contest related questions while it is ongoing

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

Quite good maths in $$$F$$$

»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

how to update an element in map

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

    This sentence you wrote here, google it when contest is running, you'll find an answer

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

trying problem F for more than 40 mins.. can't get anything.. even cant get the testcases ... anyone after the contest please help me for problem F with detailed explanation and how to arrive to such solution

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

C is a popular interview problem with different name. https://www.geeksforgeeks.org/find-excel-column-name-given-number/

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

E and C should have been swapped ):

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

Is F 26 ^ (k + s.size()) - number of strings of length k + s.size() that doesnt contain s as subsequence? How to get second value? I guess dp of O(n * 26) or O(n)? Halp me plzzz :(

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

Super quick editorial in Python. More editorials at http://interview.solutions

A.

A tutorial
A code

B.

B tutorial
B code

C.

C tutorial
C code

D.

D tutorial
D code

E.

E tutorial
E code

F.

F tutorial
F code
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why are we doing n-=1 every time in the question c?

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

    How did you come with that solution for F.

    I thought something like:- 26^k * (n+k)Ck ,then subtract all cases.

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

      why 26^k * (n+k)Ck not the answer? I was also thinking the same.

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

        Because their will be cases when some cases have common elements

        ex -> k = 1, s= 'ab'

        a*b, *ab

        aab, aab , It will occur in both but we have to count it once.

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

    thanks

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

    in prob. C, can you explain why n -= 1 ?

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

      We can just notice pattern like A = 1, B = 2, ... Z = 26, AA = 27, etc. We know already the value mod 26 will tell us the last character, so we try to map [1..26] to [0..25]

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

        i tried to do something like this in every iteration "zabcdefghijklmnopqrstuvwxy"[n%26] and then divide n by 26, lastly reversed what i got.

        can't figure out why this approach is wrong. it doesn't work for inputs like 26+26^2

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

          it doesn't work because 26 should correspond to 'z' but as 26 %26 = 0 and your code will give the answer to be 'aa'. Hence we have to subtract 1 for each iteration .

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

    alexwice could you elaborate how did you come up with such simple approach for F? My approach was to build strings which have the given string S as a subsequence, So we would need to choose |S| positions from K+|S| places, and fill the rest with any 26 letters, but the problem is overcounting. How does your solution handle this?

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

      Try the naive DP, and notice that S doesnt matter.

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

        A bit more complicated, but once you implement the naive DP you can notice it can be written in matrix notation.

        And that transition matrix can be split into a shift matrix and a diagonal matrix. Expanding with binomial theorem arrives at the same answer (Note: I think binomial expansion doesn't work with matrices in general, it just happened to work out in this case).

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

    For F, why is this Wrong:

    Number of strings such that S is a subsequence of string of length |S|+K : C(|S|+K,K)

    Number of strings of length K : 26^K

    So answer = C(|S|+K,K) * 26^K

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

      hetp111 Because this answer overcounts. for example if the string S is "oop" and K = 1, Then ooop will be counted 3 times by your formula, but we should count it only once.

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

    Can you explain why only the length of S matters?why different string of the same length won't affect the answer?

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

      I wrote up a different explanation of F. The gist of it is that you can count strings that don't contain $$$S$$$ as a subsequence, and think through a hypothetical implementation of "is $$$S$$$ a subsequence of $$$T$$$".

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

    your F code is giving WA.

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

    Why the answer is the same if S was all 'a's ?

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

      Because in F each insertion can be broken into 3 cases [var1var2'x'],[var1'x'var2], ['x'var1var2 ]. (Here we are inserting the variable x) .Try finding the answer for k=1 and take var1 and var2 same in one case and different in the other , you will reach at the same answer. If you still have any problem you can refer to my youtube editorial here

»
9 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Fs statement would have been more clear if distinct strings had to be counted.

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

How to solve F please help

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

Can anyone help me with the problem F? I can feel there is a lot of maths involved (possibly). Is there any simple way?

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

    It involves fundamental combinatorics only — of placing x same objects in N different places and filling the rest with any object other than x . If you still are having problem understanding the editorial refer to this Video Editorial — F.

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

      Thanks a lot buddy! I had up-solved it on that day itself, thanks to AnandOza for his wonderful editorial (right after the contest) !

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

Today's problem C is a subset of problem 1B

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

I've posted an English editorial here: https://codeforces.com/blog/entry/79153

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

It was my first atcoder contest only able to solve problems a,b,d. Looking forward to solve more in upcoming contests.

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

that was my first atcoder contest and I couldnt solve C. Are there editorials after contests?

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

Please explain PROBLEM F

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

Nice contest.

How to do F?

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

How to solve F ?

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

can someone tell logic behind on how to solve C?

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

I firmly believe that I'd seen the E in some last year's Codechef cook-off.

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

    It was in January or february cookoff this year. I couldn't solve it then but watched a video tutorial of it after the contest. I solved it today in one go without even reading the problem completely :)

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

IMO, this contest was much easier than other ABCs. How to solve F?

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

What is the problem in solving D using a dictionary? I got 8 AC and 4 WA Code: https://ideone.com/BWSxtc

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

What is the solution for F? I tried to solve it with combinatorial but I failed. Any theorems?

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

F can be solved using this link.

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

My approach for F was to calculate the number of ways to put K indistinguishable objects in |S| + 1 containers (the objects being the new characters and the containers the spaces between letters, here with |S| I denote the length of the string) and then choosing one letter for each new character. Resulting in $$$\binom{K + |S|}{|S|}\times{26^{K}}$$$. However, it didn't turn out to be right... can someone help me?

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

    Yes I tried that in the same way but it's wrong. I think it's because your counting some things more than once.

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

    You end up overcounting, because you can reach the same final string $$$T$$$ in many ways (for example, if you start with $$$S$$$ = abc, you can reach $$$T$$$ = abbc by inserting a b either before or after the middle b).

    I have a detailed explanation in this post.

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

how to solve F?

Any sorts of hints are appreciated.

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

    Key observation: ans is fixed whatever the string is. Only length of string matters (and K too).

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

Can someone please explain on which test case my submission failed for the problem D. I used the same approach as in editorial. https://atcoder.jp/contests/abc171/submissions/14558518

»
9 months ago, # |
Rev. 4   Vote: I like it +64 Vote: I do not like it
F's solution
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot for such a good explanation.

    btw could you suggest me some problems on combinatorics(or any sources) if you know any?.

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

    Seems so easy after reading this explanation. Thanks! Minor typo in the last formula $$$i$$$ should be $$$x$$$.

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

    It should be $$${|S|-1+k-x \choose |S|-1}$$$?

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

    Why build 'a' such that 'ai' is minimum ? What about the other cases ?

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

      I think he just introduced it to make counting easy. In this manner you will not overcount anything.

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

    In the last formula, it should be $$$+k$$$ instead of $$$-k$$$. It confused me for a while until I see your code.

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

    I cannot understand if i<|S| why we have 25 choices and else we have 26 choices can anyone explain me with example?

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

I thought of F like this: Let the length of the string given=N So, the final length of the string (to be formed) must be N+K Now, consider all the strings that can be formed of length N+K. This will be 26^(N+K) Now, we know that the original string must be a subsequence of the final string. So, the problem reduces to finding the number of ways of having the given string as a subsequence of the final string. So, we need to fix N positions from N+K with the letters of the given string. So, the ans = 26^(N+K-N) * 1*(C(N+K,N)) = 26^(K) * C(N+K,N) However, I was not getting the correct answer to this approach. Any ideas as to why this might be wrong.

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

    I did the same...

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

    There are repetitions in your approach. You are fixing say: _ _ o _ _ o_f_

    but then _ o o _ _ o _ f _ is counted thrice

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

      Hi is there an editorial for this?

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

        Yes, the english version is yet to come. It takes a day for Atcoder for the same

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

      Ohhhhhhhhhh. I missed that. Thanks a lot. Now understood it.

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

Can anybody explain a shorted method for question E? I could solve it but my method is a bit overkill?

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

I generally solve 3 problems in beginner contests but today for the first time I have solved 5 problems. Although these 5 problems are very easy for many participants, sometimes it gives inspiration for newbies like me.

Thanks to all the writers for giving thus problems.

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

hai everyone.. why my code give wa on D..

this is my code

pls help me.. thank you

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

In my small carrier of cp, F has the stupidest statement and example I have ever seen.

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

Can anyone Explain Problem C

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

I think, Atcoder should not give WA, if my code does not give right output in Test 1, just like codeforces. I received a penalty in A, just because I took test cases as input

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

    I agree, it's nice to have a simple check for I/O format.

    I've also submitted solutions to the wrong problem before, so it would be nice to avoid that penalty as well.

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

I think F is a very nice problem. The technique which is used for not to overcount any string is a genius idea.

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

Can someone please tell me where am I wrong in C. It is showing WA for some test cases.

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    unsigned long long int n;
    cin >> n;
    string ans = "";
    while (n)
    {
        string a(1, (n % 26) + 'a' - 1);
        ans.insert(0, a);
        n /= 26;
    }
    cout << ans;
}

int main()
{
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

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

    I will provide you a testcases where your code is failing: n=52 and n=26

    Debug it!!

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

      Ahh!! So n%26 is 0 and then 'a'-1 is giving me the wrong character. Got it thanks.

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

In cpp.If anyone need .

A
B
C
D
E
F
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. Can u explain the logic of problem C ????

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

      C is basically similar to converting a number into binary , except here the base is given to us to be 26 , one thing that is different is that you have to subtract one from n in each iteration . If you still can't understand check out this Video Editorial .

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

    In question D. What is the size of count array i.e N ?

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

      I used 1e5+5

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

        Thanks man! But i've a question i used 1e5 and it gives me WA. but when i used 1e5+5 it was right.Can you explain why??

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

          1e5 means 0 to 1e5-1..so if found 1e5 it failed to store..

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

    can you point out the mistake in my code for problem C and why have you decremented n in while loop?

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

      I decremented cause if i find 1 by while loop it means want to add 'a' but 'a'+1 means b..so i decremented 1. and add 'a'+ 0 means a..

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

Video solution for problem F.

Link: https://youtu.be/3mnwcJGO_MI

UPD: sorry for uploading this video that late, it's because of slow internet connection.

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

Can anybody give a comparison of difficulty between CF and AtCoder? Like what is the difficulty of AtCoder Beginner A,B,C,D,E in terms of the difficulty on CF?

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

    A,B should be 800, C,D,E should be 1100 and 1300 not more than that

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

    use that site: https://kenkoooo.com/atcoder#/table/slimnet

    instead of "slimnet" put your atcoder nickname.

    here, in "table" tab you should put a tick on "show difficulties", and you will see the tasks colors and their difficulties if u put your mouse cursor on the colored circles. if you want to compare it to cf you can add 300-500 to its atcoder rating and it will be pretty accurate cf rating of that task

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

    A and B are in the range 800-900.however once u get to d,e things start to get difficult.This is because if D or E is a dp question it surely is tough in the range of 1200-1400.Even slightly complicated way of data structure maybe in use.Hence if u are a newbie in cf,u should be able to solve A,B in Atcoder .C sometimes in Atcoder. If you are a pupil,try solving till d and if e problem is easy like in today's contest.That's it.

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

chokudai I want to point out a bug in the AtCoder's Virtual Contest system. I registered for this contest but didn't participate. So, I decided to do a virtual for this contest after it ended. But on viewing virtual standings, it shows only my contest participation by default, in which I didn't try any problem.

This is a screenshot of virtual standings during my VC participation:

Maybe this can be updated to show the virtual rank instead of the contest ones, in case someone is writing a VC for the contest

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

for c

why is this solution is wrong. please clarify someone.

https://atcoder.jp/contests/abc171/submissions/14552303

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

Can anybody explains why in problem F, we have to multiply by 25K−(the number of letters before SN).

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

    let string is abc and we place 'a' at all four available positions then results will be : aabc , aabc,abac,abca.

    to avoid such repetitions we use it in this way.

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

vedio editorial for all problems : https://youtu.be/eTKfAdpP1Cc

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

Can anyone explain problem E: Red Scarf?

I can't understand Japanese editorial...

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

Can anyone explain Problem F?

I can't understand the editorial's explanation...

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

Similar (But harder) idea for problem F:

Let $$$f(i, j)$$$ denote the number of strings T of length i in which the longest prefix of given string S which appears in our T as a subsequence is equal to j.

Then it's quite straightforward to reach the following recurrence:

$$$f(i, j) = f(i - 1, j - 1) + 25 * f(i - 1, j)$$$

(There is just one character available to increment the value of mentioned prefix of S. And 25 characters which don't increase the value of j).

The rest is just like the editorial. It was easier for me to reach the intended solution this way.

Actually this gives the idea to solve recurrence:

$$$f(0, 0) = 1$$$
$$$f(i, j) = a * f(i - 1, j - 1) + b * f(i - 1, j)$$$

In logarithmic time with linear preprocess (Read the editorial for F):

$$$f(i, j) = {i \choose j} * a ^ j * b ^ {i - j}$$$

Note that this is not true for problem F of this contest, because the value of j is at most the size of S, and there are some other constraints to reach state (i + 1, j + 1) from state (i, j).