AtCoder Beginner Contest 171 Announcement

4 years ago, # ^ |

exactly, I also learned a new trick in the or problem E

→ Reply

4 years ago, # |

← Rev. 2 →

-11

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 →

-24

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

→ Reply

4 years ago, # ^ |

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, # ^ |

thanks for your reminding. I'll keep a mind next time.

→ Reply

mrslowmo

4 years ago, # ^ |

I thought I was the only one.

→ Reply

sharmapriyansh

4 years ago, # |

-18

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

→ Reply

Sumanto

4 years ago, # ^ |

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

→ Reply

shuba400

4 years ago, # ^ |

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

Legend_of_Azkaban

4 years ago, # ^ |

← Rev. 2 →

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

Kishansingh47

4 years ago, # ^ |

Use Map

→ Reply

4 years ago, # |

-9

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

younoknowme

4 years ago, # ^ |

← Rev. 2 →

→ Reply

4 years ago, # ^ |

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

→ Reply

mike1729

4 years ago, # ^ |

E was Easy

→ Reply

ridl

4 years ago, # ^ |

Hint

→ Reply

grimjaw

4 years ago, # ^ |

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

Check the video editorial out

4 years ago, # ^ |

→ Reply

AduPadu

4 years ago, # |

-22

what is the logic for problem D

→ Reply

TheNR

4 years ago, # ^ |

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

disgrace_2k

4 years ago, # |

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

→ Reply

rishabhdeepsingh

4 years ago, # |

Quite good maths in $$$F$$$

→ Reply

ColorlessCoder

4 years ago, # ^ |

Can you please tell the approach after the contest ends? Thanks.

→ Reply

4 years ago, # ^ |

Video Editorial — F

→ Reply

sharmapriyansh

4 years ago, # |

-18

how to update an element in map

→ Reply

4 years ago, # ^ |

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

→ Reply

Atish508

4 years ago, # |

+18

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, # ^ |

Check out My Video Editorial — F

→ Reply

Sumanto

4 years ago, # |

← Rev. 2 →

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

→ Reply

Zeroooiq

4 years ago, # |

E and C should have been swapped ):

→ Reply

dush1729

4 years ago, # |

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 →

+41

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

A tutorial

A code

print('A' if input().isupper() else 'a')

B tutorial

B code

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
print(sum(A[:K]))

C tutorial

C code

N = int(input())
ans = []
while N:
    N -= 1
    N, r = divmod(N, 26)
    ans.append(chr(ord('a') + r))
print("".join(reversed(ans)))

D tutorial

D code

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
S = sum(A)

for _ in range(int(input())):
    b, c = map(int, input().split())
    k = count[b]
    count[b] = 0
    count[c] += k
    S += (c - b) * k
    print(S)

E tutorial

E code

N = int(input())
A = list(map(int, input().split()))
S = 0
for x in A:
    S ^= x
for i in range(len(A)):
    A[i] ^= S
print(*A)

F tutorial

F code

MOD = 10 ** 9 + 7
K = int(input())
M = len(input())
N = M + K

pow25 = [1] * (N + 1)
fac = [1] * (N + 1)
inv = [1] * (N + 1)
for x in range(1, N + 1):
    fac[x] = fac[x - 1] * x % MOD
    pow25[x] = pow25[x - 1] * 25 % MOD
inv[N] = pow(fac[N], MOD-2, MOD)
for x in range(N - 1, -1, -1):
    inv[x] = inv[x + 1] * (x + 1) % MOD

def binom(n, k):
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD

ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

→ Reply

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Because The 26 base system is 1 indexed , if you still don't get it check out this video — editorial

→ Reply

rheo-chiti

4 years ago, # ^ |

How did you come with that solution for F.

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

→ Reply

decoder__

4 years ago, # ^ |

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

→ Reply

nikeshthapa255

4 years ago, # ^ |

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

myFakeHandle

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

myFakeHandle

4 years ago, # ^ |

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, # ^ |

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

kanishk779

4 years ago, # ^ |

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, # ^ |

+21

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

→ Reply

at.f

4 years ago, # ^ |

← Rev. 3 →

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

hetp111

4 years ago, # ^ |

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

kanishk779

4 years ago, # ^ |

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

Gary2005

4 years ago, # ^ |

+11

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, # ^ |

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

Gary2005

4 years ago, # ^ |

Thank you.

→ Reply

vineetjai

4 years ago, # ^ |

your F code is giving WA.

→ Reply

4 years ago, # ^ |

try now

→ Reply

Gats

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

AM_I_Learning

4 years ago, # |

-15

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

→ Reply

spookywooky

4 years ago, # ^ |

+44

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

→ Reply

cis_pie

4 years ago, # |

How to solve F please help

→ Reply

Imperial_Lord

4 years ago, # |

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, # ^ |

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

Imperial_Lord

4 years ago, # ^ |

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

prodipdatta7

4 years ago, # |

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

→ Reply

4 years ago, # |

+31

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

→ Reply

_aadiupadhyay_

4 years ago, # |

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

→ Reply

didedoshka

4 years ago, # |

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

→ Reply

dbs_mnnit

4 years ago, # |

Nice contest.

How to do F?

→ Reply

Retired_NarutoElMatria

4 years ago, # |

How to solve F ?

→ Reply

HurricKane

4 years ago, # |

can someone tell logic behind on how to solve C?

→ Reply

dbs_mnnit

4 years ago, # ^ |

convert N into base 26

→ Reply

3o1

4 years ago, # |

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

→ Reply

Matuagkeetarp

4 years ago, # ^ |

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

hydro_lyte

4 years ago, # |

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

→ Reply

arpeggio5588

4 years ago, # |

← Rev. 2 →

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

→ Reply

coder1033

4 years ago, # ^ |

← Rev. 2 →

[deleted]

→ Reply

ridl

4 years ago, # ^ |

I manually computed the initial sum instead of using accumulate , and got AC using your code. I don't understand why accumulate was giving you WA though.

→ Reply

arpeggio5588

4 years ago, # ^ |

← Rev. 2 →

I solved it now it would be sum = accumulate(v.begin(),v.end(),(long long)0); Very silly mistake :(

→ Reply

ridl

4 years ago, # ^ |

Ah I see, better luck next time :)

→ Reply

Beyrad

4 years ago, # |

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

→ Reply

adisava

4 years ago, # |

+10

F can be solved using this link.

→ Reply

Beyrad

4 years ago, # ^ |

Thanks!

→ Reply

terencehill

4 years ago, # |

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

Beyrad

4 years ago, # ^ |

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

Your code with minor changes..

4 years ago, # ^ |

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

terencehill

4 years ago, # ^ |

← Rev. 2 →

I got it now, thanks!

→ Reply

Saksham_2000

4 years ago, # |

how to solve F?

Any sorts of hints are appreciated.

→ Reply

Iftekhar_Hakim_K

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

AyanoGod

4 years ago, # |

← Rev. 3 →

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

younoknowme

4 years ago, # ^ |

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

AyanoGod

4 years ago, # ^ |

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

→ Reply

younoknowme

4 years ago, # ^ |

← Rev. 2 →

Oh. your laziness costed you AC lol.

→ Reply

AyanoGod

4 years ago, # ^ |

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

→ Reply

Levi.Ackerman.

4 years ago, # ^ |

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

→ Reply

Osama_Alkhodairy

4 years ago, # |

← Rev. 4 →

+64

F's solution

→ Reply

Saksham_2000

4 years ago, # ^ |

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

lemongrab

4 years ago, # ^ |

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

→ Reply

Osama_Alkhodairy

4 years ago, # ^ |

Fixed, thanks.

→ Reply

dibyadarshan

4 years ago, # ^ |

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

→ Reply

hetp111

4 years ago, # ^ |

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

→ Reply

lemongrab

4 years ago, # ^ |

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

→ Reply

Thallium54

4 years ago, # ^ |

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

→ Reply

Priyansh31dec

4 years ago, # |

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

minus_plus

4 years ago, # ^ |

← Rev. 2 →

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

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

→ Reply

yozaam

4 years ago, # ^ |

Hi is there an editorial for this?

→ Reply

minus_plus

4 years ago, # ^ |

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

→ Reply

Priyansh31dec

4 years ago, # ^ |

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

→ Reply

jpratik15

4 years ago, # |

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

→ Reply

Hz_

4 years ago, # ^ |

Take xorsum of each integers like s^=a[i];
Again for each integer do xor with s and current element and print it.

→ Reply

hydro_lyte

4 years ago, # ^ |

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

→ Reply

pucuk16

4 years ago, # |

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

this is my code

pls help me.. thank you

→ Reply

4 years ago, # ^ |

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

→ Reply

pucuk16

4 years ago, # ^ |

thank you.. now i know these is different

(long long) (a * b)

and

(long long) a * b

→ Reply

4 years ago, # ^ |

← Rev. 2 →

more generally, we can use 1ll * a * b to change the result into long long xD

→ Reply

iabhishek15

4 years ago, # |

← Rev. 3 →

→ Reply

Lazarusx2

4 years ago, # |

Can anyone Explain Problem C

→ Reply

4 years ago, # ^ |

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

ashish_vaghani

4 years ago, # |

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 →

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

void.abyss

4 years ago, # |

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

→ Reply

mrslowmo

4 years ago, # |

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

RisingWizard

4 years ago, # ^ |

← Rev. 2 →

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

Debug it!!

→ Reply

mrslowmo

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

4 years ago, # |

In cpp.If anyone need .

int n;
           string s;
           char ch;
           cin>>ch;
           if(ch>='A' && ch<='Z')
            cout<<"A"<<endl;
           else
            cout<<"a"<<endl;

           long long n,k,i,ans=0;
           string s;
           cin>>n>>k;
           long long ar[n+5];
           for(i=0;i<n;i++)
            cin>>ar[i];
           sort(ar,ar+n);
           for(i=0;i<k;i++)
            ans+=ar[i];
           cout<<ans<<endl;

long long n;
           cin>>n;
           string ans;
           while(n>0){
            n--;
            ans+=('a'+n%26);
            n/=26;
           }
           reverse(ans.begin(),ans.end());
           cout<<ans<<endl;

           long long n,i,sum=0,m,x,y;
           string s;
           cin>>n;
           long long ar[n+5],cnt[N]={0};
           for(i=0;i<n;i++){
            cin>>ar[i];
            cnt[ar[i]]++;
            sum+=ar[i];
           }
           cin>>m;
           for(i=0;i<m;i++){
            cin>>x>>y;
            if(cnt[x]==0) cout<<sum<<endl;
            else{
               sum-=(cnt[x]*x);
               sum+=(cnt[x]*y);
               cout<<sum<<endl;
               cnt[y]+=cnt[x];
               cnt[x]=0;
            }
           }

           long long n;
           cin>>n;
           long long ar[n+5],ans[n+5];
           int xxor=0;
           for(int i=0;i<n;i++){
            cin>>ar[i];
            xxor^=ar[i];
           }
           for(int i=0;i<n;i++){
            ans[i]=xxor^ar[i];
            cout<<ans[i]<<' ';
           }

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
 
const int N = 2000001;
 
int n, k, fact[N], inv[N], mod = 1e9 + 7;
string s;
 
int powlog(int a, int b){
    if(b == 0) return 1;
    int ret = powlog(a, b / 2);
    if(b % 2) return 1LL * ret * ret % mod * a % mod;
    return 1LL * ret * ret % mod;
}
int C(int n, int r){
    if(r > n) return 0;
    return 1LL * fact[n] * inv[n - r] % mod * inv[r] % mod;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fact[0] = 1;
    for(int i = 1 ; i < N ; i++){
        fact[i] = 1LL * i * fact[i - 1] % mod;
    }
    inv[N - 1] = powlog(fact[N - 1], mod - 2);
    for(int i = N - 2 ; i >= 0 ; i--){
        inv[i] = 1LL * (i + 1) * inv[i + 1] % mod;
    }
    cin >> k >> s;
    n = s.size();
    int ans = 0;
    for(int i = 0 ; i <= k ; i++){
        ans = (ans + 1LL * powlog(25, k - i) * powlog(26, i) % mod * C(n - 1 + k - i, n - 1)) % mod;
    }
    cout << ans << endl;
}

→ Reply

____ALPHA____

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

→ Reply

abhijeet3099

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

4 years ago, # ^ |

I used 1e5+5

→ Reply

abhijeet3099

4 years ago, # ^ |

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, # ^ |

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

→ Reply

abhijeet3099

4 years ago, # ^ |

I didn't know that. Thanks

→ Reply

4 years ago, # ^ |

most welcome brother !

→ Reply

Amaterasu

4 years ago, # ^ |

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

→ Reply