chokudai's blog

AtCoder Beginner Contest 171 Announcement
By chokudai, history, 4 years 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

Comments Comments (151)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Starts in 5min

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

I was just trying to cheer up.

→ Reply
  • »
    »
    4 years 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. :)

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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 :(

    → Reply
    • »
      »
      »
      4 years 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

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

    I thought I was the only one.

    → Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

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

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

    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.

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

    Use Map

    → Reply
»
4 years 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..

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    C

    E

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    E was Easy

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

    C:

    Hint

    E:

    Hint
    → Reply
  • »
    »
    4 years 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

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

    Check the video editorial out

    → Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

what is the logic for problem D

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Quite good maths in $$$F$$$

→ Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

how to update an element in map

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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

→ Reply
»
4 years 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/

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

E and C should have been swapped ):

→ Reply
»
4 years 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 :(

→ Reply
»
4 years 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
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

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

    → Reply
    • »
      »
      »
      4 years 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]

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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 .

          → Reply
  • »
    »
    4 years 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?

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

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

      → Reply
      • »
        »
        »
        »
        4 years 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).

        → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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$$$".

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

    your F code is giving WA.

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

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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    What else of a meaning can that be? It must be distinct strings even without the word distinct.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F please help

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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) !

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
»
4 years 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.

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest.

How to do F?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell logic behind on how to solve C?

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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 :)

    → Reply
»
4 years 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?

→ Reply
»
4 years 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

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

F can be solved using this link.

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F?

Any sorts of hints are appreciated.

→ Reply
  • »
    »
    4 years 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).

    → Reply
»
4 years 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

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

    Your code with minor changes..

    I removed accumulate line because I didn't know what it did and precomputed res while taking input, and changed a bit in calculating res during query.

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

      accumulate function sums up things in a given range. here i was using it for the initial sum of the array.

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

        Oh. your laziness costed you AC lol.

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

          yeah that's ok for me. but why didn't it worked?

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

            AFAIK, return type of accumulate() is same as datatype third parameter. If you pass third parameter as 0LL it will give AC.

            → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +64 Vote: I do not like it
F's solution
→ Reply
  • »
    »
    4 years 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?.

    → Reply
  • »
    »
    4 years 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$$$.

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

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

    → Reply
  • »
    »
    4 years 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 ?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

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

      Hi is there an editorial for this?

      → Reply
      • »
        »
        »
        »
        4 years 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

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

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

      → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1. Take xorsum of each integers like s^=a[i];
    2. Again for each integer do xor with s and current element and print it.
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Calculate xor of every element of the array, except at the current index and print

    → Reply
»
4 years 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

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

    the result of x * b and x * c might be bigger than the range of int

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

      thank you.. now i know these is different

      (long long) (a * b)

      and

      (long long) a * b
      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone Explain Problem C

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
»
4 years 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;
}
→ Reply
  • »
    »
    4 years 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!!

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In cpp.If anyone need .

A
B
C
D
E
F
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years 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 .

      → Reply
  • »
    »
    4 years 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 ?

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

      I used 1e5+5

      → Reply
      • »
        »
        »
        »
        4 years 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??

        → Reply
        • »
          »
          »
          »
          »
          4 years 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..

          → Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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..

      → Reply
»
4 years 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.

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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

→ Reply
»
4 years 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

→ Reply
»
4 years 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).

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years 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...

→ Reply
»
4 years 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...

→ Reply
»
4 years 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).

→ Reply