chokudai's blog

By chokudai, history, 9 months ago,

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!

• +142

 » 9 months ago, # |   0 Starts in 5min
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 are there names for each color? (like pupil, expert etc on cf)
 » 9 months ago, # | ← Rev. 4 →   -10 I was just trying to cheer up.
•  » » 9 months ago, # ^ |   +35 Maybe a little bit to exited for a contest that happens once a week. :)
•  » » » 9 months ago, # ^ |   0 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, # ^ |   0 exactly, I also learned a new trick in the or problem E
•  » » » » » 9 months ago, # ^ |   0 Can you share with others as well, what you learned
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 i had also learn new observation of xor
 » 9 months ago, # | ← Rev. 2 →   0 Excited but cant solve more than two
•  » » 9 months ago, # ^ | ← Rev. 2 →   -7 cant solve more than 3 ;( help, please
•  » » 9 months ago, # ^ |   0 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 →   -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.
•  » » 9 months ago, # ^ | ← Rev. 2 →   -24 I can't solve C either until I use cin cout instead of scanf printf :(
•  » » » 9 months ago, # ^ |   0 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, # ^ |   0 thanks for your reminding. I'll keep a mind next time.
•  » » 9 months ago, # ^ |   0 I thought I was the only one.
 » 9 months ago, # |   0 Damn F is tough. I solved the first five in 15 minutes. Couldn't solve the F one tho :(
•  » » 9 months ago, # ^ |   0 same..
 » 9 months ago, # |   0 E is the new D
 » 9 months ago, # |   -18 has someone solved d. can it be solved without segment tree
•  » » 9 months ago, # ^ |   0 I'll reply after the contest.
•  » » » 9 months ago, # ^ |   0 ok bro
•  » » 9 months ago, # ^ |   0 yes
•  » » 9 months ago, # ^ |   +9 Why to use chainsaw when work can be done with butter knife!
•  » » 9 months ago, # ^ |   0 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 →   0 Heyy, can you please tell why Your text to link here... is getting accepted and not Your text to link here...
•  » » » » 9 months ago, # ^ |   0 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, # ^ |   0 I used long longs for only variable 'sum' , isn't that sufficient?
•  » » » » » » 9 months ago, # ^ |   0 Why don't you try using long longs for b c and temp?
•  » » » » » » » 9 months ago, # ^ |   0 Because in the question , the constraints for b,c,temp are under 10^5....hence int is enough
•  » » » » » » » » 9 months ago, # ^ |   0 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, # ^ |   0 ohh true that....my bad Thank you so much bro
•  » » 9 months ago, # ^ |   0 Yes
•  » » 9 months ago, # ^ |   0 Yes It can be solved using map
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 it can be solved using hashmap
•  » » 9 months ago, # ^ |   0 https://atcoder.jp/contests/abc171/submissions/14563862Here is my solution .. let me know if you need any explanation
•  » » 9 months ago, # ^ |   0 Yea use map and store total sum , and then for each query sum-(b* count(b))+(c*count(c))
•  » » 9 months ago, # ^ |   0 Yes it can be solved without segment tree My approach1) Keep track of current sum of total elements2) 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 →   0 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, # ^ |   0 Don't discuss during running contests.
•  » » 9 months ago, # ^ |   +1 Use Map
 » 9 months 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..
•  » » 9 months ago, # ^ | ← Rev. 2 →   0
•  » » » 9 months ago, # ^ |   0 its showing my submission..i think now i canot see your solution..your solution with c++ ? then provide here please
•  » » » » 9 months ago, # ^ |   0 check now. its java tho.
•  » » 9 months ago, # ^ |   +6 E was Easy
•  » » 9 months ago, # ^ |   0 I got confused around base and modulo in C, waiting for editorial
•  » » 9 months ago, # ^ |   0 C: HintRepresent the number in base 26E: HintTake xor of all elements in the input, try to extract the value in each position from that.
•  » » 9 months ago, # ^ |   0 For E: Observe that you can get value of ith scarf if you xor all a[j] (where, 0<=j
•  » » 9 months ago, # ^ |   0 https://atcoder.jp/contests/abc171/tasks/abc171_chttps://atcoder.jp/contests/abc171/tasks/abc171_elet me know if you need any explanation
•  » » 9 months ago, # ^ | ← Rev. 2 →   -36 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<>n; vectorarr(n);int x=0; for(int i=0;i>arr[i]; x=x^arr[i]; } for(int i=0;i
•  » » 9 months ago, # ^ |   0
•  » » 9 months ago, # ^ |   0
 » 9 months ago, # |   -22 what is the logic for problem D
•  » » 9 months ago, # ^ |   0 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, # |   +4 Please don't ask contest related questions while it is ongoing
 » 9 months ago, # |   +9 Quite good maths in $F$
•  » » 9 months ago, # ^ |   0 Can you please tell the approach after the contest ends? Thanks.
•  » » » 9 months ago, # ^ |   0
 » 9 months ago, # |   -18 how to update an element in map
•  » » 9 months ago, # ^ |   +1 This sentence you wrote here, google it when contest is running, you'll find an answer
 » 9 months 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
•  » » 9 months ago, # ^ |   0 Check out My Video Editorial — F
 » 9 months ago, # | ← Rev. 2 →   +4 C is a popular interview problem with different name. https://www.geeksforgeeks.org/find-excel-column-name-given-number/
 » 9 months ago, # |   +3 E and C should have been swapped ):
 » 9 months ago, # |   0 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 →   +41 Super quick editorial in Python. More editorials at http://interview.solutionsA. A tutorialObvious. A codeprint('A' if input().isupper() else 'a') B. B tutorialBuy the cheapest kinds first. B codeN, K = map(int, input().split()) A = sorted(map(int, input().split())) print(sum(A[:K])) C. C tutorialWe do something similar to converting to base 26: the last character depends on N % 26. C codeN = int(input()) ans = [] while N: N -= 1 N, r = divmod(N, 26) ans.append(chr(ord('a') + r)) print("".join(reversed(ans))) D. D tutorialMaintain count[x] = number of occurrences of x in A. D codefrom 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. E tutorialThe xorsum of all the elements must be the xorsum of the original array. E codeN = 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. 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 codeMOD = 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) 
•  » » 9 months ago, # ^ |   0 Why are we doing n-=1 every time in the question c?
•  » » » 9 months ago, # ^ |   0 Because The 26 base system is 1 indexed , if you still don't get it check out this video — editorial
•  » » 9 months ago, # ^ |   0 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, # ^ |   0 why 26^k * (n+k)Ck not the answer? I was also thinking the same.
•  » » » » 9 months ago, # ^ |   0 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, # ^ |   0 thanks
•  » » 9 months ago, # ^ |   0 in prob. C, can you explain why n -= 1 ?
•  » » » 9 months ago, # ^ |   +6 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   +21 Try the naive DP, and notice that S doesnt matter.
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   0 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, # ^ |   0 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^KSo answer = C(|S|+K,K) * 26^K
•  » » » 9 months ago, # ^ |   0 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, # ^ |   0 Thanks..!
•  » » 9 months ago, # ^ |   +11 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, # ^ |   +9 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, # ^ |   0 Thank you.
•  » » 9 months ago, # ^ |   0 your F code is giving WA.
•  » » » 9 months ago, # ^ |   +8 try now
•  » » 9 months ago, # ^ |   0 Why the answer is the same if S was all 'a's ?
•  » » » 9 months ago, # ^ |   0 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, # |   -15 Fs statement would have been more clear if distinct strings had to be counted.
•  » » 9 months ago, # ^ |   0 Oh now i got my mistake
•  » » 9 months ago, # ^ |   0 Damn, i spent so much time over this
•  » » 9 months ago, # ^ |   +44 What else of a meaning can that be? It must be distinct strings even without the word distinct.
 » 9 months ago, # |   +4 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, # ^ |   0 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, # ^ |   +9 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, # |   0 Today's problem C is a subset of problem 1B
 » 9 months ago, # |   +31 I've posted an English editorial here: https://codeforces.com/blog/entry/79153
 » 9 months ago, # |   0 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, # |   0 that was my first atcoder contest and I couldnt solve C. Are there editorials after contests?
 » 9 months ago, # |   0 Please explain PROBLEM F
 » 9 months ago, # |   0 Nice contest. How to do F?
 » 9 months ago, # |   0 How to solve F ?
 » 9 months ago, # |   0 can someone tell logic behind on how to solve C?
•  » » 9 months ago, # ^ |   +3 convert N into base 26
 » 9 months ago, # |   0 I firmly believe that I'd seen the E in some last year's Codechef cook-off.
•  » » 9 months ago, # ^ |   +1 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, # |   +8 IMO, this contest was much easier than other ABCs. How to solve F?
 » 9 months ago, # | ← Rev. 2 →   0 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, # ^ | ← Rev. 2 →   0 [deleted]
•  » » 9 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 I solved it now it would be  sum = accumulate(v.begin(),v.end(),(long long)0);  Very silly mistake :(
•  » » » » 9 months ago, # ^ |   0 Ah I see, better luck next time :)
•  » » » » » 9 months ago, # ^ |   0 Yeahh... Thnx :)
 » 9 months ago, # |   0 What is the solution for F? I tried to solve it with combinatorial but I failed. Any theorems?
 » 9 months ago, # |   +10 F can be solved using this link.
•  » » 9 months ago, # ^ |   0 Thanks!
 » 9 months ago, # |   0 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, # ^ |   0 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, # ^ |   +7 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, # ^ |   0 Thanks
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 I got it now, thanks!
 » 9 months ago, # |   0 how to solve F?Any sorts of hints are appreciated.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Key observation: ans is fixed whatever the string is. Only length of string matters (and K too).
 » 9 months ago, # | ← Rev. 3 →   0 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, # ^ |   0 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
•  » » » 9 months ago, # ^ |   0 " m[y]+=m[x]; m[x]=0;" isn't it what's required?
•  » » » » 9 months ago, # ^ |   0 oh right, but why are you taking your answer modulo something.
•  » » » » » 9 months ago, # ^ |   0 earlier it was without modulo but that didn't worked either so,i thought they might have forgot the modulo part.
•  » » » » 9 months ago, # ^ |   0 I removed accumulate function and got ac on your codehttps://atcoder.jp/contests/abc171/submissions/14588887
•  » » » » » 9 months ago, # ^ |   0 but what's the problem with accumulate?
•  » » 9 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 accumulate function sums up things in a given range. here i was using it for the initial sum of the array.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 Oh. your laziness costed you AC lol.
•  » » » » » 9 months ago, # ^ |   0 yeah that's ok for me. but why didn't it worked?
•  » » » » » » 9 months ago, # ^ |   0 hmm I don't know. I code in java.
•  » » » » » » 9 months ago, # ^ |   +1 AFAIK, return type of accumulate() is same as datatype third parameter. If you pass third parameter as 0LL it will give AC.
•  » » » » » » » 9 months ago, # ^ |   0 i have used the same thing for many platforms/problems but didn't get any such problem earlier.
 » 9 months ago, # | ← Rev. 4 →   +64 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
•  » » 9 months ago, # ^ |   0 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, # ^ |   0 Seems so easy after reading this explanation. Thanks! Minor typo in the last formula $i$ should be $x$.
•  » » » 9 months ago, # ^ |   0 Fixed, thanks.
•  » » 9 months ago, # ^ |   +3 It should be ${|S|-1+k-x \choose |S|-1}$?
•  » » 9 months ago, # ^ |   0 Why build 'a' such that 'ai' is minimum ? What about the other cases ?
•  » » » 8 months ago, # ^ |   0 I think he just introduced it to make counting easy. In this manner you will not overcount anything.
•  » » 8 months ago, # ^ |   0 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, # ^ |   0 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, # |   0 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, # ^ |   0 I did the same...
•  » » 9 months ago, # ^ | ← Rev. 2 →   +2 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, # ^ |   0 Hi is there an editorial for this?
•  » » » » 9 months ago, # ^ |   0 Yes, the english version is yet to come. It takes a day for Atcoder for the same
•  » » » » » 9 months ago, # ^ |   0 oh thanks a lot :D
•  » » » 9 months ago, # ^ |   0 Ohhhhhhhhhh. I missed that. Thanks a lot. Now understood it.
 » 9 months ago, # |   0 Can anybody explain a shorted method for question E? I could solve it but my method is a bit overkill?
•  » » 9 months ago, # ^ |   +3 Take xorsum of each integers like s^=a[i]; Again for each integer do xor with s and current element and print it.
•  » » » 9 months ago, # ^ |   0 Ya,I realized it ,anyways thanks!!
•  » » 9 months ago, # ^ |   0 https://atcoder.jp/contests/abc171/submissions/14569053just go through the main function. let me know if any explanation is needed.
•  » » 9 months ago, # ^ |   0 Calculate xor of every element of the array, except at the current index and print
•  » » 9 months ago, # ^ |   0 https://atcoder.jp/contests/abc171/submissions/14583501Here take a look into my solution!
 » 9 months ago, # |   0 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, # |   0 hai everyone.. why my code give wa on D..this is my codepls help me.. thank you
•  » » 9 months ago, # ^ |   0 the result of x * b and x * c might be bigger than the range of int
•  » » » 9 months ago, # ^ |   0 thank you.. now i know these is different (long long) (a * b) and (long long) a * b 
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 more generally, we can use 1ll * a * b to change the result into long long xD
•  » » 9 months ago, # ^ |   0
•  » » 9 months ago, # ^ |   0 you can do it like sum+=x*(b-c)
 » 9 months ago, # | ← Rev. 2 →   0 In my small carrier of cp, F has the stupidest statement and example I have ever seen.
 » 9 months ago, # |   0 Can anyone Explain Problem C
•  » » 9 months ago, # ^ |   0 Exactly the same: https://www.geeksforgeeks.org/find-excel-column-name-given-number/
•  » » » 9 months ago, # ^ |   0 Thank you
•  » » 9 months ago, # ^ |   0 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, # |   0 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 →   0 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, # |   +7 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, # |   0 Can someone please tell me where am I wrong in C. It is showing WA for some test cases. #include 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 →   0 I will provide you a testcases where your code is failing: n=52 and n=26Debug it!!
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Ahh!! So n%26 is 0 and then 'a'-1 is giving me the wrong character. Got it thanks.
 » 9 months ago, # |   0 In cpp.If anyone need . Aint n; string s; char ch; cin>>ch; if(ch>='A' && ch<='Z') cout<<"A"<>n>>k; long long ar[n+5]; for(i=0;i>ar[i]; sort(ar,ar+n); for(i=0;i>n; string ans; while(n>0){ n--; ans+=('a'+n%26); n/=26; } reverse(ans.begin(),ans.end()); cout<>n; long long ar[n+5],cnt[N]={0}; for(i=0;i>ar[i]; cnt[ar[i]]++; sum+=ar[i]; } cin>>m; for(i=0;i>x>>y; if(cnt[x]==0) cout<>n; long long ar[n+5],ans[n+5]; int xxor=0; for(int i=0;i>ar[i]; xxor^=ar[i]; } for(int i=0;i 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; } 
•  » » 9 months ago, # ^ |   0 Thank you. Can u explain the logic of problem C ????
•  » » » 9 months ago, # ^ |   0 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, # ^ |   0 Thank you very much. Nice explanation.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 In question D. What is the size of count array i.e N ?
•  » » » 9 months ago, # ^ |   0 I used 1e5+5
•  » » » » 9 months ago, # ^ |   0 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, # ^ |   0 1e5 means 0 to 1e5-1..so if found 1e5 it failed to store..
•  » » » » » » 9 months ago, # ^ |   0 I didn't know that. Thanks
•  » » » » » » » 9 months ago, # ^ |   0 most welcome brother !
•  » » 9 months ago, # ^ |   0 can you point out the mistake in my code for problem C and why have you decremented n in while loop?
•  » » » 9 months ago, # ^ |   0 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 →   +5 Video solution for problem F. UPD: sorry for uploading this video that late, it's because of slow internet connection.
 » 9 months ago, # |   0 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, # ^ |   0 A,B should be 800, C,D,E should be 1100 and 1300 not more than that
•  » » 9 months ago, # ^ |   0 use that site: https://kenkoooo.com/atcoder#/table/slimnetinstead 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, # ^ |   0 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, # |   +1 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, # |   0 for cwhy is this solution is wrong. please clarify someone.https://atcoder.jp/contests/abc171/submissions/14552303
•  » » 9 months ago, # ^ |   0 Hint: can your program output EVERY alphabet?
•  » » » 9 months ago, # ^ |   +8 oh yes got it thank you
 » 9 months ago, # |   0 Can anybody explains why in problem F, we have to multiply by 25K−(the number of letters before SN).
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 9 months ago, # ^ |   0 my mistakes, thanks
 » 8 months ago, # |   0 vedio editorial for all problems : https://youtu.be/eTKfAdpP1Cc
 » 8 months ago, # |   0 Can anyone explain problem E: Red Scarf?I can't understand Japanese editorial...
•  » » 8 months ago, # ^ |   0 Did you know that the PDF also contains English editorials?
•  » » » 8 months ago, # ^ |   0 Nope, I didn't....
 » 8 months ago, # |   0 Can anyone explain Problem F?I can't understand the editorial's explanation...
•  » » 8 months ago, # ^ |   0 Which specific part don't you understand?
 » 8 months ago, # | ← Rev. 9 →   0 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).
•  » » 8 months ago, # ^ |   0 The solution in the editorial is way way easier than this.