We will hold AtCoder Beginner Contest 171.

- Contest URL: https://atcoder.jp/contests/abc171
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200621T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: evima, gazelle, Kmcode, kyopro_friends, sheyasutaka, tozangezan
- Rated range: ~ 1999

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

We are looking forward to your participation!

Starts in 5min

are there names for each color? (like pupil, expert etc on cf)

I was just trying to cheer up.

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

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

PS: cant solve

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

Can you share with others as well, what you learned

i had also learn new observation of xor

Excited but cant solve more than two

cant solve more than 3 ;( help, please

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

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.

I can't solve C either until I use

`cin cout`

instead of`scanf printf`

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

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

I thought I was the only one.

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

same..

E is the new D

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

I'll reply after the contest.

ok bro

yes

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

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

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

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

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

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

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

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

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

Yes

Yes It can be solved using map

it can be solved using hashmap

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

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

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

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

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.

Don't discuss during running contests.

Use Map

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..

C

E

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

check now. its java tho.

E was Easy

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

C:

HintRepresent the number in base 26

E:

HintTake xor of all elements in the input, try to extract the value in each position from that.

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

https://atcoder.jp/contests/abc171/tasks/abc171_c

https://atcoder.jp/contests/abc171/tasks/abc171_e

let me know if you need any explanation

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;

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

C

E

Check the video editorial out

what is the logic for problem D

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

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

Quite good maths in $$$F$$$

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

Video Editorial — F

how to update an element in map

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

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

Check out My Video Editorial — F

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

E and C should have been swapped ):

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 :(Super quick editorial in Python. More editorials at http://interview.solutions

A.

A tutorialObvious.

A codeB.

B tutorialBuy the cheapest kinds first.

B codeC.

C tutorialWe do something similar to converting to base 26: the last character depends on N % 26.

C codeD.

D tutorialMaintain count[x] = number of occurrences of x in A.

D codeE.

E tutorialThe xorsum of all the elements must be the xorsum of the original array.

E codeF.

F tutorialActually, the answer is the same if S was all 'a's and had the same length. Let N = len(S) + K. By the binomial theorem expansion of (1 + 25)^N, we can find the number of sequences with k >= len(S) 'a's.

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

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

How did you come with that solution for F.

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

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

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.

thanks

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

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]

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

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 .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?

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

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).

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

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.

Thanks..!

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

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$$$".

Thank you.

your F code is giving WA.

try now

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

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 hereFs statement would have been more clear if distinct strings had to be counted.

Oh now i got my mistake

Damn, i spent so much time over this

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

How to solve F please help

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

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.Thanks a lot buddy! I had up-solved it on that day itself, thanks to AnandOza for his wonderful editorial (right after the contest) !

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

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

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

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

Please explain PROBLEM F

Nice contest.

How to do F?

How to solve F ?

can someone tell logic behind on how to solve C?

convert N into base 26

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

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 :)

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

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

[deleted]

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.I solved it now it would be

`sum = accumulate(v.begin(),v.end(),(long long)0);`

Very silly mistake :(Ah I see, better luck next time :)

Yeahh... Thnx :)

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

F can be solved using this link.

Thanks!

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?

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

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.

Thanks

I got it now, thanks!

how to solve F?

Any sorts of hints are appreciated.

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

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

Not correct logic. Once you change your B with C according to query you should then update your map with new C's.

my submission

" m[y]+=m[x]; m[x]=0;" isn't it what's required?

oh right, but why are you taking your answer modulo something.

earlier it was without modulo but that didn't worked either so,i thought they might have forgot the modulo part.

I removed accumulate function and got ac on your code

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

but what's the problem with accumulate?

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.

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

Oh. your laziness costed you AC lol.

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

hmm I don't know. I code in java.

AFAIK, return type of

accumulate()is same as datatype third parameter. If you pass third parameter as0LLit will give AC.i have used the same thing for many platforms/problems but didn't get any such problem earlier.

F's solutionI find this comment from yesterday quite funny. I will try to explain a detailed solution.

We want to count the number of strings $$$T$$$ of length $$$|S|+K$$$ such that the given string $$$S$$$ is a subsequence of $$$T$$$. Let's fix $$$T$$$ and try to build an algorithm to check if $$$S$$$ is a subsequence. Our algorithm if successful will return $$$a_1, a_2, ..., a_{|S|}$$$ such that $$$S_i=T_{a_i}$$$. Let's build $$$a$$$ in a way such that $$$a_i$$$ is minimum possible for all $$$i$$$. Note that for each $$$i<|S|$$$, characters $$$T_{a_i+1}, ..., T_{a_{i+1}-1}$$$ can't be equal to $$$T_{a_{i+1}}$$$ (otherwise we can minimize $$$a_{i+1}$$$), so for those characters we have limited choices (only $$$25$$$). Characters after $$$a_{|S|}$$$ can be anything ($$$26$$$ choices).

So, let's loop over how many characters will be after $$$a_{|S|}$$$; let that number be $$$x$$$. We have $$$26^x$$$ choices for that suffix. For each of the other $$$K-x$$$ characters, we only have $$$25$$$ choices, so we have $$$25^{K-x}$$$ choices for them in total. Still, we have to decide how to distribute these $$$K-x$$$ characters. We have $$$|S|$$$ slots for them (before the first character of $$$S$$$, between the first and the second character, ...). Using stars and bars, we can distribute them in $$$|S|-1+k-x \choose |S|-1$$$ ways. So, we will loop over $$$x$$$ and add to the answer $$$25^{K-x}*26^x*{|S|-1+k-x \choose |S|-1}$$$.

Submission

thanks a lot for such a good explanation.

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

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

Fixed, thanks.

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

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

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

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

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

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.

I did the same...

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

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

Hi is there an editorial for this?

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

oh thanks a lot :D

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

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

Ya,I realized it ,anyways thanks!!

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

just go through the main function. let me know if any explanation is needed.

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

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

Here take a look into my solution!

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.

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

this is my code

pls help me.. thank you

the result of

`x * b`

and`x * c`

might be bigger than the range of intthank you.. now i know these is different

and

more generally, we can use

`1ll * a * b`

to change the result into`long long`

xDChanged everything from int to long long and AC

you can do it like sum+=x*(b-c)

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

Can anyone Explain Problem C

Exactly the same: https://www.geeksforgeeks.org/find-excel-column-name-given-number/

Thank you

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

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

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.

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

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

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

Debug it!!

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

In cpp.If anyone need .

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

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 .

Thank you very much. Nice explanation.

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

I used 1e5+5

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??

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

I didn't know that. Thanks

most welcome brother !

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

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..

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.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?

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

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

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.

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

for c

why is this solution is wrong. please clarify someone.

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

Hint: can your program output EVERY alphabet?

oh yes got it thank you

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

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.

my mistakes, thanks

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

Can anyone explain problem E: Red Scarf?

I can't understand Japanese editorial...

Did you know that the PDF also contains English editorials?

Nope, I didn't....

Can anyone explain Problem F?

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

Which specific part don't you understand?

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:

(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:

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

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)`

.The solution in the editorial is way way easier than this.