### jdurie's blog

By jdurie, history, 4 months ago,

1838A - Blackboard List

Solution
Code

1838B - Minimize Permutation Subarrays

Solution
Code

1838C - No Prime Differences

Solution
Code

1838D - Bracket Walk

Solution
Code

1838E - Count Supersequences

Solution
Code

1838F - Stuck Conveyor

Solution
Code
• +218

 » 4 months ago, # | ← Rev. 2 →   -15 my mistake : (
•  » » 4 months ago, # ^ | ← Rev. 3 →   -16 .
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -17 Too many downvotes expected!
•  » » » » 4 months ago, # ^ |   +8 But your reply is late
 » 4 months ago, # |   +7 very observational tasks....found c easier than a and b
•  » » 4 months ago, # ^ |   0 What's your output for 3 7 ?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +33 n and m are bigger than 3
•  » » » » 4 months ago, # ^ |   +15 Wtf!!!I have wasted more than a hour finding solution for this case.
•  » » » » » 4 months ago, # ^ |   0 it happens :). I started writing down key points and constraints before attempting.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   -7 n,m>=4
•  » » » » 4 months ago, # ^ |   +9 There is 1 2 3 4 5 6 7 9 10 11 12 13 14 8 17 18 19 20 21 15 16
•  » » » » » 4 months ago, # ^ |   0 length should be 21
•  » » » » » » 4 months ago, # ^ |   0 It is
•  » » » » 4 months ago, # ^ |   +44 The only sizes that aren't solvable are 2x2 and 2x3. Below are some solutions for other small sizes: 2x41 2 3 4 5 6 7 8  2x5 1 2 3 4 5 7 8 9 10 6  2x6 1 2 3 4 5 6 7 8 9 10 11 12  2x71 2 3 4 5 6 7 9 8 12 13 14 10 11  3x31 9 5 2 8 4 6 7 3  3x4 1 2 3 4 5 6 7 8 9 10 11 12  3x5 1 2 3 4 5 7 6 15 14 13 11 10 9 8 12  3x6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  3x7 1 2 3 4 5 6 7 9 8 12 13 14 10 11 21 20 16 17 18 19 15 
•  » » » 4 months ago, # ^ |   +4 1 7 13 19 4 10 19 2 8 14 20 5 11 20 3 9 15 21 6 12 21 Making sure that columns with difference 3 aren't adjacent
•  » » » » 4 months ago, # ^ |   0 if any of the side has even size. answer is pretty easy. try to proveit for 9 * 3.
•  » » » » » 4 months ago, # ^ |   0 1 10 19 2 11 20 3 12 21 4 13 22 5 14 23 6 15 24 7 16 25 8 17 26 9 18 27
•  » » » » » » 4 months ago, # ^ |   0 sorry my bad, basically what I meant was,, try some odd numbers which has, prime * 3 dimensions, it will be difficult... 11 * 3 , or 17 * 3 , 19 * 3 , 7 * 3 ...Patters will not emerge...U have to do lot of head-banging.
•  » » » » » » » 4 months ago, # ^ |   0 we can take first odd then all even at junction of even and odd its not hard to find (odd-even) to be composite number like 1,7,13,19,25,31,4,10,16,22,28 .
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 in fact we can prove the junction will always be 3k ,k>1 provided prime>3.
•  » » » » » » » 4 months ago, # ^ |   0 yes when both the numbers are prime, it took me quite some time to find an ideal reordering (following my way).
•  » » » » 4 months ago, # ^ |   0 Why there is no "16 17 18" in ur solution?
•  » » 4 months ago, # ^ |   0 How is the case 4 * prime handled. I mean if we have n = 4, and m = prime. Then taking the alternating rows doesn't work out. as 1st, 3rd, 2nd, 4th have an issue with 2nd and 3rd being together.
•  » » » 4 months ago, # ^ |   0 if atlest one number is nonprime then the siln is straighforward for n=4,m=prime 1 5 ... 2 6 ... 3 7 ... 4 8 ...
 » 4 months ago, # |   0 Good contest
 » 4 months ago, # | ← Rev. 2 →   -20 Enjoyed problem C. Good Contest
•  » » 4 months ago, # ^ |   +6 I can't even solve C :(
•  » » » 4 months ago, # ^ |   0 i have solve C before A.
•  » » » » 4 months ago, # ^ |   +5 I spent about 1.5 hours, but I cannot come up with any ideas :(
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 sometimes it happen, like today i cannot figure out solution for A faster.
•  » » » » » » 4 months ago, # ^ |   0 Exactly in the same situation, A took me stupid amount of time to figure out, B was decent, C was very easy.
•  » » » » » 4 months ago, # ^ |   0 Same happened for me with B
•  » » » » 4 months ago, # ^ |   +2 Sorry for my bad English. Can you please share some problems like today C. I always struggle in such type of question.
•  » » » » » 4 months ago, # ^ |   +1 I guess this is a similar one :https://mirror.codeforces.com/problemset/problem/1783/B
•  » » » 4 months ago, # ^ |   +3 Same
•  » » » 4 months ago, # ^ |   0 I can't even solve B :(
 » 4 months ago, # | ← Rev. 2 →   +9 Forgot the case s[1] = ')' or s[n] = '(' ToT
•  » » 4 months ago, # ^ |   0 lol same T-T. That's why my color was turned TvT
 » 4 months ago, # | ← Rev. 2 →   0 ф
 » 4 months ago, # |   0 fast editorial!!
 » 4 months ago, # |   0 Good contest and fast tutorial! But I can only solve one problem.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 hope u will do better in upcoming contests.
•  » » » 4 months ago, # ^ |   0 Thank you for your encouragement! I'll keep up the good work! I hope I can complete two questions in the next competition.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 ...
 » 4 months ago, # |   0 fast editorial!
 » 4 months ago, # |   +5 Video Editorial for BVideo Editorial for CCredits to Dominater069 orz for C idea
•  » » 4 months ago, # ^ |   0 need D and E.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 based on Geothermal's solution
•  » » 4 months ago, # ^ |   0 The title of B video is incorrect.
•  » » 4 months ago, # ^ |   0 Please make for D as well. Thanks :)
 » 4 months ago, # |   0 fast editorial!
 » 4 months ago, # |   0 I've had this argument with quite a number of people, but can you explain how you can approach C without brute forcing random patterns?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 make difference between adjacent numbers in every row is 1.for column, try to make difference a even number if any of n or m is composite otherwise multiple of m.
 » 4 months ago, # |   0 A good idea about solving problem D! I didn't expect the implementation of D to be so simple.
•  » » 4 months ago, # ^ |   0 Agreed, the implementation for my idea for D is really tedious, I did not notice using the parity and bracket pair allows me to keep track of what I needed. Pretty nice solution overall!
 » 4 months ago, # |   +26 I found it cool that problems were not that standard, unlike usual div2s.
•  » » 4 months ago, # ^ |   -16 Please show me a recent div2 that had "standard" problems.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +11 Well, yesterday's contest for example (C was implementing a simple recursion and D was standard DP) and many others, and, in general, every educational round. I feel Div2 medium/hard problems are usually standard.
 » 4 months ago, # |   +9 Short solution of A — E. Impressive
 » 4 months ago, # |   +12 I enjoyed solving C most, it was a nice problem !
 » 4 months ago, # |   +23 Hit or miss forces
•  » » 4 months ago, # ^ |   0 Yeah, same.
•  » » 4 months ago, # ^ |   0 yeah lgms just have better luck so they hit more often
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Man went from 129th to almost 8000th in mere 24hrs dead emojiI felt the same, btw
•  » » » 4 months ago, # ^ |   +4 lol opposite for me :alive:
•  » » » » 4 months ago, # ^ |   +9 You forgot to be become CM
•  » » » » 4 months ago, # ^ |   0 Well done!
 » 4 months ago, # |   -17 Almost solved E once again :(. Didn't notice that you don't need the values of array $a$ to count $dp$. Enjoyed the round, although I can see there are not so many people who have the same feelings
•  » » 4 months ago, # ^ | ← Rev. 2 →   -8 :)
 » 4 months ago, # |   0 Anyone please help me out how to solve B and C questions in Div2. I got stuck many times in it.I had practice many questions but still am facing this issue.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Try participating in more contests and even virtual contests. And upsolve after the contest.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot.Can you suggest some more tips to improve skills in CP and rating?
•  » » 4 months ago, # ^ |   0 I had exactly the same problem (I still struggle with 3 sometimes), I suggest you solve problems from other websites especially leetcode. Also learn about prefix arrays,modular arthimatic and the very basics of DP and Graphs. Good Luck :)
•  » » » 4 months ago, # ^ |   0 Sure, I will learn and implement.Thanks!
 » 4 months ago, # |   +31 https://www.youtube.com/watch?v=GusESkLoLcA&ab_channel=tyroWhizSolutions from A-D and my insights on E
 » 4 months ago, # |   0 Is D well known trick? Why so many ACs...
•  » » 4 months ago, # ^ |   +9 editorial seems like magic but trust me its notif you try to consider what happens when (( occurs, its trivial
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +3 If you read basically anyone's AC solution, they maintain the position of occurrences of (( and )), which is the natural solution.The editorial's "( in an even index" is magic. So many people got AC because it's unnecessary magic.
•  » » » » 4 months ago, # ^ |   0 Yep, agree
 » 4 months ago, # |   0 Was I the only one to submit a brute-force recursion-with-backtracking solution for problem C?The worst-case time complexity is high, but it runs fast in practice because the problem is not very constrained.
 » 4 months ago, # |   +3 Perfect editorial
 » 4 months ago, # |   0 Is it just me who enjoys Ds that are more algorithm and implementation heavy and not Ds that are like "because math something something cout << i-am-clown is always the correct answer"
•  » » 4 months ago, # ^ |   +26 I too enjoy not thinking and getting my way through life as such. Unfortunately, this is often not possible.
•  » » » 4 months ago, # ^ |   +3 based reply, honestly these people make me so mad, they just dont want to think, and then get annoyed when problems need you to think
•  » » » » 4 months ago, # ^ |   -12 Is there any problem that doesn't require you to think?
•  » » » » » 4 months ago, # ^ |   0 i think you know what i meant "needs you to think". div2 abc problems that wud need ds would definitely need you not to think. (maybe if using easier ds) I cant find a segtree problem fit for div2C difficulty aside from the trivial ones.the core of the issue is : you cant have easy problems with data structurs because beginners should not be expected to have much knowledge of them. as maroonrk puts it, a problem should have thinking >>> knowledge. I would like to see a div2C in a 6 problem contest which uses ds and still follows that above principle
 » 4 months ago, # |   0 Can someone please explain why this brute-force idea for A is incorrect? 0) if there is a negative integer that is obviously the answer.1) insert all the elements in the array in a set. This set keeps track of all the elements which is impossible to get through the absolute difference of any 2 elements in the array.2) Use nested for loops(n^2) and iterate through the array(not set) and check the absolute difference of every 2 elements in the array. If this absolute difference is present in the set, remove this from the set.3) the element still remaining in the set, this must be one of the possible answers because of the fact that this element was impossible to get through any 2 elements' absolute difference.
•  » » 4 months ago, # ^ |   +8 hello,first of all — set is not good thing if you have equal numbers.second, you should check in your solution that removed element is not the one of the elements that you have considered as a difference.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 ooooooohhhhhhh right, thanks a lot. I was breaking my head for over an hour.thanks, a lot. That wrong submission cost me 200 ranks :(edit: the brute force got accepted with a single-line fix. :)https://mirror.codeforces.com/contest/1838/submission/208520942
 » 4 months ago, # | ← Rev. 2 →   +18 Here's my thought process for ABC, hopefully it helps people understand how to come up with the solution. Sometimes it seems unintuitive but it is possible.A: We notice that negative numbers are abit sus from the sample testcases, how come theres only 1 or 2 negative numbers? Then realise because we are taking absolute difference the rest of the numbers are positive, so negative numbers can only appear at the very start => meaning, if we see a negative number we just print it. Else, there is no negative numbers, what to do? If theres no negative numbers, because we are taking absolute difference we can just take the maximum value in the array, as we can only get smaller values in the future by taking absolute differences. Therefore: if min < 0 print min, else print maxB: Ok we want to minimise the number of permutation subarrays => What is the minimum value? Can we always get 1 and [1...n] as the only permutations? Ok idk if its possible, let me check the testcase: It seems that this is always possible after checking all the testcase. Therefore, we want only 1 and 1...n as the permutations, how to do so? See that if we place 1 and n beside each other, it may be good because every subsequent subarray afterwards that contains [1,n] will never be a smaller permutation. However we see from the testcase that ...2 1 n is still bad, because we only need 1 and 1...n as the permutations. 2 is pesky, so let us place it away from 1 so that we can never get 1,2 as a subarray. Ok how to do so? realise that 1, n, 2 and 2, n, 1 will be correct, so let us just make this pattern and we can ignore the rest of the subarrays. We can ignore the rest because we will always have [1,n] together without any other permutations formedC: Constructive, seems that many people are able to solve in the contest => Solution must be quite simple, aka spot the pattern or trick and the rest will fall out. Ok, seems that we need to find a simple solution, do not tunnel vision into the first approach you have! Try out a few different approaches and see which one is the most simple to implement and easier to extend: For example, I tunnel visioned into grouping all the even / odd numbers together, and then at the border of odd / even we need to make everything 1. Seems complex, so lets discard that idea (unfortunately I tunneled too hard into random ideas). Ok let us think of a very naive solution, for 4x4, we can try out 1 2 3 4 ... 14 15 16. Wow seems like it works, is it simple? yes, is it easier to extend? Hopefully. Realise that for 5x5 this doesnt work. Key insight: Think of why it doesnt work instead of just trying out other random approaches. Ok it doesn't work because the next row is +m, and m is 5. Ok so how to make the rows better? If we just think of why it doesn't work, can we possibly modify or extend this idea to make it work? Turns out, if we make the rows +2m +2m and so on, it will not be prime. So: we can place the even rows at the top and the odd rows at the bottom to make sure this difference is indeed > m and a multiple of m.Hope this helps
•  » » 4 months ago, # ^ |   +6 the point of "Don't tunnel vision into the same approach" is really important. I was lucky to have got the right approach on the first try, usually I tend to stick to one idea a lot ;)
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +5 Unfortunately I had all sorts of weird ideas like boxing the last column into the last m guys, zig zag, spiral, diagonals, grouping even odds together and making the borders 1, trying odd / even in a way that if n,m is odd we make the border zigzagged, making +4 +4 +4 and so on. If only I thought of simpler ideas I might have gotten it during the contest. At least I learnt something new I guess.
•  » » » » 4 months ago, # ^ |   0 Can you please explain how you coded Problem B: I got the idea partially but couldn't be able to implement it. Same for Problem C, i got if any n or m is even, we can simply have our grid, otherwise we have to keep the difference as 2*m, but couldn't be able to find a test case, on paper how to keep the difference as 2*m. Thanks for your guide to approaches!
•  » » » » » 4 months ago, # ^ | ← Rev. 5 →   0 Bonus: short solution to A (for fun): https://mirror.codeforces.com/contest/1838/submission/208557142short solution to C (for fun): https://mirror.codeforces.com/contest/1838/submission/208565313
 » 4 months ago, # | ← Rev. 3 →   +15 My solution for 1838D - Прогулка по скобкам:Observation behind the approachAny even length sequence of the form ((...)) is always walkable because the beginning and closing consecutive brackets can always be retraced to make up a valid bracket sequence, no matter the content inside. Also this is the only format of incorrect bracket sequence which gives correct path on a walk. So we can take the largest possible string of this type and just check for the correctness of the prefix and suffix bracket sequence.Also, the prefix and suffix string should be exactly of the form k*() for k>=0. Otherwise some consecutive brackets will occur which can't be corrected in a walk because consecutive brackets of opposing type won't cover for them.Implementation:Maintain two sets l and r storing indices of consecutive opening (( and closing )) brackets. Also maintain a data structure (segment tree) over the an array having +1 for ( and -1 for ). For every query, check the i-1 and i+1 index for index i being updated and update the sets l and r and sum-tree accordingly. To find the answer for each query: If n is odd, then answer is always NO as mentioned in solution. If both of l and r are empty, then check the whole array (index 0:n-1) for correct bracket sequence. Answer YES or NO accordingly. If one of l or r is empty, then answer is NO. Else consider the first index where (( occurs -say x (first element of l) and the last index where )) occurs -say y (last element of r): If x>y answer NO. If 0:x-1 and y+2:n-1 are correct bracket sequences, then answer YES, else NO. To check the correctness of bracket sequence i:j, following conditions need to be checked: If j
•  » » 4 months ago, # ^ |   0 I got the exact same idea while solving D, I also knew we should use a segment-tree to implement it, but I have never implemented a segment-tree before, just know the concept. I should start learning these advanced concepts soon.
•  » » » 4 months ago, # ^ |   +3 I don't think you need segment trees necessarily for this problem atleast: Here check this out : https://mirror.codeforces.com/blog/entry/116995#comment-1034970
•  » » » » 4 months ago, # ^ |   0 Yup, don't need segment tree, checking starting character ( and even length should be enough, sum will automatically be 0 for even sequence having no consecutive similar brackets. Then starting character will decide correct bracket sequence.
 » 4 months ago, # |   0 Hey .. Can someone suggest me a video to understand D , having a hard time warping my head around it
•  » » 4 months ago, # ^ |   0 I would suggest first try to solve few regular bracket sequence related easy problems. That will build your logic, then try to solve this problem.Editorial's solution as well as solution proposed by Spartanlord are good ones. I am sure u will be able to understand one of these solution once u build some logic.way to go ... https://leetcode.com/problems/longest-valid-parentheses/https://leetcode.com/problems/generate-parentheses/
•  » » 4 months ago, # ^ |   0 Just wrote this comment here: hopefully easy to understand. https://mirror.codeforces.com/blog/entry/116995#comment-1034970
 » 4 months ago, # |   0 Hi, is there to way to download the test data for problem C? Pretty sure the code should work for all inputs but it keeps finding an error, I often make some stupid mistake in code but already removed 3 problems from it and can't find another.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 The problem is that your code (in some cases) swaps rows and columns. For example on test 1 4 5 The code should output a grid with $4$ rows and $5$ columns, but your code outputs the following: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Since the checker doesn't care about whitespaces (spaces, linebreaks etc.) but it is expecting $5$ integers per line, your output gets interpreted as 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 which is obivously wrong.
•  » » » 4 months ago, # ^ |   +11 Thank you so much! Would have probably lost many more hours on this without your help. Originally thought that the checker checked for both cases and when I tried to change it so it worked for it just in case I absolutely forgot about the first part of my code that goes on if n is composite.
 » 4 months ago, # |   +29 during contest:WTF is this, I hate this contest. After reading editorials : what a beautiful problems. How much more stupid I can be !!!
•  » » 4 months ago, # ^ |   +12 For me, this contest was a reality check of how stupid I am.
 » 4 months ago, # |   0 can someone explain solution for c
•  » » 4 months ago, # ^ |   0 what part of editorial solution you don't understand ?
•  » » » 4 months ago, # ^ |   0 actually i didn't understand the code but now i figured it out thanks for replying
 » 4 months ago, # | ← Rev. 2 →   0 in D, what is the point to go back and forth in the bracket sequence? why it will not be a valid walk otherwise? Can't I walk directly from 1 to n if it is a regular bracket sequence?
•  » » 4 months ago, # ^ | ← Rev. 3 →   +1 suppose you have (())))))))))in order to do valid walk, u must have equal number of ( and ) in the final regular bracket sequence. To fulfill the requirement of ( , we must do back and forth at index 1 and 2 , so that we can generate enough number of ( . hope this makes sense.
•  » » » 4 months ago, # ^ |   +5 ohh! didn't see that perspective! thanks!!
 » 4 months ago, # |   0 I feel so stupid right now, I got C solution but did not implement it because I was fixed on the fact that 1 is not composite and forgot that it is not prime either.
 » 4 months ago, # |   0 best & shortest way to solve this question.
 » 4 months ago, # |   0 Yet again, so close to D. I knew it had something to do with two consecutive brackets but my mind went to prefix sums and segtrees to count the balance and I ended up ditching it
 » 4 months ago, # |   +19 When solving E, got weird answers on the samples, after 20 mins of debugging, found that I forgot to read the input array...
 » 4 months ago, # |   -20 Alternative solution for B: We only need to consider 1 and 2 as we want 1 and 2 far as possible. Because of that, there are at most 4 cases regarding choosing element 1 or 2 and swapping it with the element in position 1 and n.
 » 4 months ago, # |   0 so fast editorial
 » 4 months ago, # |   +4 My logic for 877D Problem D ( no segtree and all):Basically, just maintain two sets left and right so that left stores the indices i at which we have i & i+1 consecutive opening brackets. Similarly, right stores indices i s.t. i & i+1 both are consecutive closing brackets. Now, I claim that we just need these two sets to see if our string is walkable or not. Note that, updating these two sets after each query is simple. Since you just check the query index, the index before that and index after that and corresponding add or remove from both left and right sets.For final answer at each query, just see if the lowest value in left set is smaller than the lowest value in right set, and similarly, the highest value in left set is also smaller than highest value in the right set. After all these checks are done, we can't simply say 'YES' as there can be strings starting with ) and ending with (, so just check for these two positions in the string and output YES and NO accordingly.Here is the working run on input test case (most of it atleast ^_^): String : (())()())) left: {1} right: {3,8,9} "YES" switch position 9 String : (())()()() left: {1} right: {3} "YES" switch position 7 String : (())()))() left: {1} right: {3,6,7} "YES" switch position 2 String : ()))()))() left: {} right: {2,3,6,7} "NO" switch position 6 String : ()))(())() left: {5} right: {2,3,7} "NO" switch position 3 String : ()()(())() left: {5} right: {7} "YES" switch position 6 String : ()()()))() left: {} right: {6,7} "NO" switch position 7 String : ()()()()() left: {} right: {} "YES" Here is my submission: 208584903
•  » » 4 months ago, # ^ |   0 nice one
 » 4 months ago, # |   +11 E's solution is so elegant!
•  » » 4 months ago, # ^ |   +8 C D E all three are so elegant in my opinion...we want one more contest from jdurie <3
 » 4 months ago, # | ← Rev. 2 →   0 I wonder what is the editor's solution for problem A to check ALL possible correct answers? Also, "If there are multiple solutions, print any of them" statement is not entirely clear. It could mean that you accept either of two numbers. But since editorial mentions that for 9 2 7 both 2 and 7 are correct answers (in addition to 9) that means that you accept all possible starting numbers, not only those actually used for the generation.So you can't simply generate some sequence from 2 numbers and then only accept them. You need to accept all possible initital combinations. And in case of hacks, you even don't know how the hack was generated (but you need to check that this is correct sequence anyway).So the editor's solution should include some algo to generate all possible initial states. Is that's why $n \le 100$ ? So for each initial pair of numbers you can greadily grow the set of all numbers ($O(n^4)$) or so?
 » 4 months ago, # |   -18 This is just sad. Wait, no, not just sad. Sad and enraging.
 » 4 months ago, # |   +5 Did someone else also found problem D ("Bracket walk") a little confusing. I can't even wrap my head around the editorial as well!
 » 4 months ago, # |   +5 Solution for Problem A (I recommend watching it in 1.5X speed)Codeforces Round 877 Solution A Blackboard List
 » 4 months ago, # | ← Rev. 6 →   +5 I solve F in a constant number of queriesFirstly we do this queries (i mean n=10 here)? 1 1. >>>>>>>>>v. <<<<<<<<>>>>>>>>. >>>>>>>>>v. <<<<<<<<>>>>>>>>. >>>>>>>>>v. <<<<<<<<
 » 4 months ago, # | ← Rev. 2 →   +8 I solved E with an overkill solution that is worth mentioning using generating functions:I arrived at the DP solution where (if we let $f(i, j)$ be the number of arrays of length $j$, such that the subarray of length $i$ in $a$ appears in it), then we get $f(0, j) = k^j$ $f(i, 0) = 0 \text{ for } i > 0$ $f(i, j) = f(i - 1, j - 1) + (k - 1)f(i, j - 1) \text{ for } i, j > 0$and note that $f(n, m)$ is our answer.Now, if we let $B_i(x) = \sum_{j \ge 0} f(i, j)x^j$, we can multiply the last equation by $x^j$ and sum for $j \ge 1$, and then we get $B_i(x) = xB_{i - 1}(x)+(k - 1)xB_i(x)$then we get $\iff B_i(x)=\frac{x}{1 - (k - 1)x}B_{i - 1}(x)$this means $B_n(x)=[x^n/(1 - (k - 1)x)^n] B_0(x)$And note that since we want $f(n, m)$, we just want the coefficient of $x^m$ in $B_n(x)$.Now, note that by the generalized binomial theorem, we know $\displaystyle (1 - x)^{-n}=\sum_j\binom{n + j - 1}{j}x^j$and so $\displaystyle x^n \cdot (1 - (k - 1)x)^{-n} = \sum_j\binom{n + j - 1}{j}(k - 1)^j x^{n + j}$and $B_0(x) = \sum_j k^jx^j$and so (using the definition of power series multiplication, check this) $\displaystyle [x^m]B_n(x) = \sum_{i + j = m - n}\binom{n + i - 1}{i}(k - 1)^i \cdot k^j$so let $h = m - n$, the answer to our problem is just $\displaystyle \sum_{i = 0}^h \binom{n + i - 1}{i}(k - 1)^i \cdot k^{h - i}$(be aware that this solution assumes $0^0 = 1$, so when $k = 1$, $(k - 1)^i$ shall produce $1$ at $i = 0$).Let $d = (k - 1)/k$, and note that our summation is now $\displaystyle k^h \cdot \sum_{i = 0}^h \binom{n + i - 1}{n - 1}d^i$so we are only interested in finding the summation and disregard the $k^h$ for now.Note that $\binom{n - 1}{n - 1} \cdot d^0 = [x^{n - 1}](x + d)^{n - 1}$, and $\binom{n}{n - 1} \cdot d^{1} = [x^{n - 1}](x + d)^{n}$, in general, the required sum is $[x^{n - 1}]((x + d)^{n - 1} + (x + d)^{n} + \dots + (x + d)^{m - 1})$but since there is no term with $x^{n - 1}$ in $(x + d)^i$ for $i < n - 1$, we that the above is the same as $=[x^{n - 1}](1 + (x + d) + \dots + (x + d)^{m - 1})$or by the geometric series formula $\displaystyle=[x^{n - 1}]\frac{(x + d)^m - 1}{x + d - 1}$now if we ignore the -1 in the denominator for a moment, we note that since $\displaystyle \frac{1}{x + d - 1} = \sum \frac{(-1)^ix^i}{(d-1)^{i + 1}}$then the required coefficient is $\displaystyle [x^{n - 1}]\frac{(x + d)^m - 1}{x + d - 1} = \sum_{i + j = n - 1}\frac{(-1)^ix^i}{(d-1)^{i + 1}}\binom{m}{j}d^{m - j}$ $\displaystyle =\sum_{i = 0}^{n - 1}\frac{(-1)^i}{(d-1)^{i + 1}}\binom{m}{n - 1 - i}d^{m - n + i + 1}$which is finally a summation up to $n - 1$ which is computable in the given time limit!We just have to be careful that when $i$ hits $n - 1$, we have to take care of the -1 in the numerator that we just ignored, because the constant term in $(x + d)^m - 1$ is $d^m - 1$ not $d^m$, and now we can just tweak this summation a bit: $\displaystyle =k^{m - n}\left(\sum_{i = 1}^{n - 1}\frac{(-1)^{n - 1 - i}}{(d-1)^{n - i}}\binom{m}{i}d^{m - i} + (-1)^{n - i}\frac{d^{m} - 1}{(d - 1)^{n}}\right)$is the same summation but going backwards, and multiplied by the $k^h$ or $k^{m - n}$ that we disregarded above, but we just note that we can compute all $\binom{m}{i}$ the same way we did in the editorial. Here is my submission.P.S. I know, again, it is a very overkill solution, but I hope whoever read it all learned something from it :D
•  » » 4 months ago, # ^ |   0 Very impressive, I was stuck at the summation which is the same as yours:$S=\sum_{r=n}^m a^r \binom{r}{n}$Thank you for sharing!
•  » » » 4 months ago, # ^ |   0 Thanks! I hope it helped!I also got stuck in this summation for a while, and I felt like finding the coefficient of $x^{n - 1}$ wouldn't help and would just give the same thing, but it turns out it changes the boundaries of the summation to make it computable!
 » 4 months ago, # | ← Rev. 2 →   0 I think that 2500 rated. E problem is almost same as atcoder abc 171 F-Strivore and if you look at its editorial you get another elegant way to think about the problem
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 I think the difference is in the constraint on $K$ in atcoder ABC 171 F-Strivore. In my solution above, I was able to stop at this summation $\displaystyle \sum_{i = 0}^h \binom{n + i — 1}{i}(k — 1)^i \cdot k^{h — i}$in the atcoder problem.
 » 4 months ago, # |   0 Hi, could anyone have a look at my submission for problem D? I am not able to get the problem with my logic and why some testcases are failing. Please have a look at my submission and tell the mistake in logic. Thanks.
•  » » 4 months ago, # ^ |   0 Please reply someone
•  » » 4 months ago, # ^ |   0 Take a look at Ticket 16876 from CF Stress for a counter example.
 » 4 months ago, # |   0 Dear MikeMirzayanov I received a message as followingAttention!Your solution 208487626 for the problem 1838C significantly coincides with solutions codefforces/208477360, jvatsal0709/208480645, AMBUJ_2003/208487626, koraash/208495313, Timkador/208502256. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.First, I don't know any of these guys. I wrote my code in the online gdb compiler, so there was no copy of the code from that; also, I saw the code of 2 people, codefforces & jvatsal0709, and they were not similar to my code; one of them used Python while others code was a lot different than mine,we all did the same thing to make an array of the first 1000 primes because that was the limit in the questions, and so it might be because we have done the same thing, and I got the message that I copied, but please look into this. I still need to copy their code. We are in no way connected.So I hope someone looks into this. Please, let me know if I have to give any proof. Thanks.
 » 4 months ago, # |   0 Sorry to say this. But your description of problem B is terrible. It misleads in many ways. Please try to clarify more. Otherwise very creative problems. Nice work (y)
 » 3 months ago, # |   0 for C, isn't tutorial code giving wrong answer for n=5 and m=5?
 » 3 months ago, # | ← Rev. 5 →   0 The editorial for $E$ came up with such a nice expression. For comparison's sake, here's the form I came up with:(by the way, to make things simpler here, I decremented $k$ at the start) $- \binom{m - 1}{n - 1} \cdot (k - 1) ^{m - n + 1} + \sum_{i = 0}^{n - 1} \left[ (k + 1) \cdot k^{m - 1 - i} \cdot \binom{m - 1}{i} \right] - \frac{k + 1}{k} \cdot (n - 2) \cdot (k + 1)^{m - n} + \binom{m - 1}{n - 1} \cdot (k + 1) \cdot k^{m - n}$It gets AC thankfully: 211182571
 » 3 months ago, # |   0 There is a better solution in F，it only need 12 queries.
 » 3 months ago, # |   0 What a good E! The ignorance of the array $a$ is amazing!
 » 2 months ago, # |   0 what is the nature way to aproach a contructive problem?? for me , it's so hard although i took an hour for problem C. Every comment should be appreciated!! thank
 » 5 days ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } For C[problem:1838C] Why am i getting 'wrong answer' when I arranged the array in the same way but just starting from row 1,3,5.. and then row 2,4,6.. wrong solution-225752615 and also I did as mentioned too by starting from row 2,4,5 and its passing all test cases- 225750729.