Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### vovuh's blog

By vovuh, history, 11 months ago,

I'm really sorry about issues with problems E and F. Can't say anything more because I don't want to justify my mistakes.

1433A - Boring Apartments

Idea: vovuh

Tutorial
Solution

1433B - Yet Another Bookshelf

Idea: vovuh

Tutorial
Solution

1433C - Dominant Piranha

Idea: vovuh

Tutorial
Solution

1433D - Districts Connection

Idea: MikeMirzayanov

Tutorial
Solution

1433E - Two Round Dances

Idea: MikeMirzayanov

Tutorial
Solution

1433F - Zero Remainder Sum

Idea: MikeMirzayanov

Tutorial
Solution

1433G - Reducing Delivery Cost

Idea: MikeMirzayanov

Tutorial
Solution

• +115

 » 11 months ago, # |   +5 Thank you Vovuh for all of your time and effort you put into these Div 3s, please don't stop :( Also, E is a good problem if OEIS didn't exist, I found it pretty constructive. F too hard for a brik like me
•  » » 11 months ago, # ^ |   0 How to solve E using OEIS? Never used OEIS before.
•  » » » 11 months ago, # ^ |   0 OEIS is an encyclopedia for integer sequences. You can search by entering a sequence and you will find all others with formulas also. As, for problem E there can be only 10 inputs, and 4 of them are given, so simply searching with the sequence can be find from OEIS
•  » » » » 11 months ago, # ^ |   +3 It could be found even by this number 12164510040883200
•  » » » » » 11 months ago, # ^ |   0 wow!
•  » » » » » 11 months ago, # ^ |   -6 And i thought how E had 5k solves. Stupid me. HAHA
•  » » » 11 months ago, # ^ |   0 You can directly search the answer for input 20 and OEIS will give you a pattern. Sometimes this is very helpful.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 first, write a brute-force to generate the first few elements of the sequence or you can generate by hand in pen and paper, with those elements search in the OEIS. you will get all the sequences that start with these elements.
•  » » 11 months ago, # ^ |   +11 Would have used some MOD, then it's not straight forward!
•  » » 11 months ago, # ^ | ← Rev. 2 →   +6 without OEIS we can solve , by using simple math (n-1)!/(n/2) it's simple apply mathematics formula like combination of sitting in circular table (n-1)!/2
 » 11 months ago, # |   0 It was a great contest. I felt problems were easy. But I enjoyed. Thank you.
 » 11 months ago, # |   +3 Nice round vovuh really enjoyed the round !! Thanks for the round , hoping to have more such rounds with the interesting problems again.
 » 11 months ago, # | ← Rev. 8 →   0 In problem E how can we find sequence on OEIS ?? since we do not know the ans for i/p :6??
•  » » 11 months ago, # ^ | ← Rev. 3 →   +48 Underscore works as a wildcard:1, 3, _, 1260, _, _, _, _, _, 12164510040883200
•  » » » 11 months ago, # ^ |   0 thanks!!
•  » » » 11 months ago, # ^ |   0 Can you tell what is OEIS and how we can get anser from that??
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 oeis.org Web result with site links The On-Line Encyclopedia of Integer ... It contains information about integer sequences. For example the search https://oeis.org/search?q=1%2C+3%2C+_%2C+1260%2C+_%2C+_%2C+_%2C+_%2C+_%2C+12164510040883200&language=english&go=Search shows that such a sequence is known and displays formulas to get the nth term and more.
•  » » » » » 11 months ago, # ^ |   0 but how do we find that sequence what you searched in google specicifically??
•  » » » » » » 11 months ago, # ^ |   +1 Go to the website and enter the sequence or google the sequence and write oeis with it
•  » » » » 11 months ago, # ^ |   0 Its online encyclopedia where you enter a series of number a and get information about series like formula
•  » » » 11 months ago, # ^ |   +3 This was more useful than any above answers :)
 » 11 months ago, # |   +6 "Let dp[x][y][cnt][rem] be the maximum possible sum we can obtain if we are at the element ax,y right now, we took cnt elements in the row x and our current remainder is cnt."Shouldn't the current remainder be rem instead of cnt? I didn't AC this problem, and I want to know the solution. This round was fun, thank you. :)
•  » » 11 months ago, # ^ |   +3 Thanks, that was a typo, I fixed it.
•  » » 11 months ago, # ^ |   +3 Can someone suggest some problems similar to F one , i.e, combining the concept of dp and remainder ?
•  » » » 11 months ago, # ^ |   +3
•  » » » » 11 months ago, # ^ |   0 I think this is way simpler and a little different.
 » 11 months ago, # |   0 Very nice problemset, these round really help us (beginners) to improve and let us see that you really take care of this platform :)
•  » » 11 months ago, # ^ |   0 these were a bit too easy for mech keyboard merchants to type and get the precious rating.
•  » » » 11 months ago, # ^ |   0 I did the comment in fact because I feel more comfortable doing div 3 than div 2, plus div 3 contests are not that often :(
 » 11 months ago, # |   0 Amazing Editorial!
 » 11 months ago, # |   0 E is a good problem. I really like it.
 » 11 months ago, # |   0 typo in D:"Let's find any district $i$ that $a_i \ne a_i$"It should be $a_i \ne a_1$
•  » » 11 months ago, # ^ |   +3 Thanks, fixed.
 » 11 months ago, # |   0 Test cases for problem F were weak, like I just calculate the maximum sum I can get in matrix choosing m/2 element in each row lets call it sum then I print (sum/k)*k , its like greatest multiple of k just smaller then sum, and boom I got AC :). PS:: Later it got hacked (:.
 » 11 months ago, # |   0 In the editorial of F it's written our current remainder is cnt. whereas it should be our current remainder is rem.
 » 11 months ago, # |   0 I didn't understand one thing. In the first problem, why did he write 'dig=x[0]-'0'',basically,subtract the zero.
•  » » 11 months ago, # ^ |   0 x[0] is a character....to get the correct integer.. char of 0 is removed. for eg: let x[0] = '3' so x[0] — '0' = 51 — 48 = 3
•  » » » 11 months ago, # ^ |   0 Thanks
 » 11 months ago, # |   0 in C answer will be index of maximum element why is it showing wrong answer
•  » » 11 months ago, # ^ | ← Rev. 3 →   +3 TC15 5 5 5 2 TC22 5 5 5 5
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 Consider -> 5 5 5 4 1 2 In this the max index is 0(1 for the answer, since indexing is 1 based in the question). But the answer is 2(3). Also, maybe you did the indexing wrong.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 The answer will be the index of maximum element adjacent to a non maximal element. If suppose, one prints only index of maximum then it could be right in between 2 maximal elements, such as index 1 in 4 4 4 3. Index 1 is maximum in the array but it is next to another maximum and cannot eat the number next to it.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 There are multiple answers. 4 4 4 3 = 4 4 5 so index 3 is the answer
 » 11 months ago, # | ← Rev. 5 →   +1 The approach to sentence E is simpler 96159630: there are n people, calculate the number of ways to make 2 circles.The first person has 1 choice (because he is the first person in the first circle), the second person has n-1 choice, the third person has n-2 choices, ..., the n / 2 person has n / 2 + 1 choice, n / 2 + 1 person has 1 choice (since this is the first of the second circle), the n / 2 + 2 person has n / 2-1 choice .. .For example:With n = 6, the number of ways to choose will be calculated as 1x5x4x1x2x1.With n = 8, the number of ways to choose will be calculated as 1x7x6x5x1x3x2x1.=> The general formula is (n-1)! / (n/2).Sorry for my English not good.
•  » » 10 months ago, # ^ |   0 why first person has 1 choice in every circle?
•  » » » 7 months ago, # ^ |   0 Because his position is fixed since we can't count rotations. I guess he didn't mention it in his solution. But prolly that's the reason.
 » 11 months ago, # |   0 Can someone please explain in problem E how we choose permutations as n!/(n/2)? (Sorry for the silly question)
•  » » 11 months ago, # ^ |   0 You can see more here
•  » » 11 months ago, # ^ |   0 You can choose n/2 in nC2 ways..in each way u get (n/2-1)! ways in first round dance and further in each configuration of this,u get (n/2-1)! ways for 2nd round dance..Note here that u are double counting(so divide by 2)U will get (nC2*(n/2-1)!*(n/2-1)!)/2Which on simplification is (n!*2)/(n*n)
 » 11 months ago, # |   0 This is my second contest. Pretty good questions were there. Enjoyed a lot.
 » 11 months ago, # |   0 This round was great! Great editorial!
 » 11 months ago, # |   0 In Problem E why we have to divide our answer by 2 ?
•  » » 11 months ago, # ^ |   -8 You can see more here
•  » » » 11 months ago, # ^ |   +1 I got that logic. But I was trying to find out the tutorial
•  » » » » 11 months ago, # ^ |   +1 The Dancing pairs [1, 2 ,3 ,4] [5, 6, 7 ,8] is same as [5, 6, 7, 8] [1, 2, 3, 4] so, when we applied the formula, we are counting every possible pair twice. So, we need to divide the answer by 2.
•  » » » » » 11 months ago, # ^ |   0 i got it. thank you
 » 11 months ago, # |   0 There is a simpler formula in Problem E. Since we need exactly different round dances, we can notice that all of them can be represented as permutations with a fixed first element (for example, with a fixed number 1 at the beginning). Then the number of such sequences will be (n-1)!, now we just need to divide this number by (n / 2) (I don't know exactly how to prove why this works, but it works XD).
•  » » 11 months ago, # ^ |   0 Oh, I didn't notice that this solution was already shown above.
 » 11 months ago, # | ← Rev. 2 →   0 I am a very beginner at learning dp. So I understand recursive dp more than iterative. Can anyone provide me a recursive dp solution for problem F?UPD: solved.
•  » » 11 months ago, # ^ |   0 @Hafiz_ Checkout this video https://www.youtube.com/watch?v=-HPlOuGnEE4
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 96209145 u can check this out.
 » 11 months ago, # |   +6 Don't know why are you encouraging to find sequence on OEIS for E?It is bit surprising to see that
•  » » 11 months ago, # ^ |   0 Would've been a bit difficult if one didn't know the math. I think that should've been done though. It turned out to be too easy right now.
•  » » » 11 months ago, # ^ |   0 https://codeforces.com/contest/1433/submission/96212192 Can you tell me whwre i am doing wrong in my dp code ??for problem F
•  » » 11 months ago, # ^ |   0 You are very pretty <3
 » 11 months ago, # |   0 i think question d become many possible solution.is it true or not?
 » 11 months ago, # |   0 When will the changed rating be reflected in the account?
•  » » 11 months ago, # ^ |   0 About an hour after finishing system testing..
•  » » » 11 months ago, # ^ |   0 means in 20-25 min from now right??;-) , I am excited bcz it's my best rank yet.
•  » » » » 11 months ago, # ^ |   0 System testing is not started yet.. ;)
•  » » » » » 11 months ago, # ^ | ← Rev. 4 →   0 Where and how can I find out if the system has started testing? And how do you know that testing is already over? P.S solved
 » 11 months ago, # |   0 Can anyone help me to understand how to approach for problem F?
•  » » 11 months ago, # ^ |   +1 In this dp problem, we are simply tracking the results on variation of every parameter(since constraints are low, seeing every possibility like Dr. Strange ;D).Firstly, we are traversing over every element in the matrix. Secondly, we are also traversing over all possible number of elements picked in a row. And also varying remainder of total sum. If a configuration with such properties (number of elements picked in that row and the total sum remainder) exists, $dp[i][j][cnt][rem]$ will have the max sum. Otherwise value will remain $-inf$.If you have solved dp problems before, you'll have an idea now. Otherwise, I urge you to practice basic dp problems, after which you'll solve this one.
 » 11 months ago, # |   0 In F , why the answer is stored at dp(n,0,0,0)?? Thank U
•  » » 11 months ago, # ^ |   0 dp[n][0][0][0] represents max sum, when we are at (n,0) [out of the matrix], i.e we have traversed the matrix and came out of it, with 0 elements picked in this row(obviously, because this row is not a part of the matrix), with the sum havin 0 remainder.
•  » » » 11 months ago, # ^ |   0 ok got it . Thanks
 » 11 months ago, # |   0 https://codeforces.com/contest/1433/submission/96167479 what's wrong here?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 You have to make exactly n-1 connections.38 8 7For this testcase, your code is printing only 1 connection which is 1 3.
 » 11 months ago, # |   0 Это довольно стандартная задача на динамическое программирование. Пусть dp[x][y][cnt][rem] равно максимальной сумме, которую мы можем получить, если сейчас мы находимся на элементе ax,y, взяли cnt элементов в строке x и наш текущий остаток равен cnt (скорее всего хотели сказать rem).
 » 11 months ago, # |   0 Isn't the reduced formula for E wrong? Should be $(n!.2)/n^2$
•  » » 11 months ago, # ^ |   0 Yaa correct. For derivation Idea:we have total n peoples and we have to choose n/2 persons for that we use C(n,n/2) where C is for combinations. Now, those two n/2 peoples in each group there are total (n/2-1)! ways using circular permutations. Also we have to divide by 2 in order to remove the reverse order. So final answer = [C(n,n/2) * (n/2-1)! * (n/2-1)!] / 2 | | | | | | | | | \ / \ / \ / Choosing n/2 Dance Dance people from n group I group II
 » 11 months ago, # |   0 Solution of problem G is giving compilation error given by you. Can you please recheck
 » 11 months ago, # |   0 I just spent whole 2 hours during the contest thinking on $F$ that $O(N^4)$ space solution won't work in $1$ second and wrote a $O(N^3)$ space + $O(N^4)$ time solution & kept debugging it till end and got AC when 7 minutes left. Yesterday i realised how bad i am at handling base cases in iterative dp.Can anyone share how do they identify whether their solution will work or not when no. of operations & size of the array used is of the order more than ~10 million.
•  » » 11 months ago, # ^ |   0 in one second computer can do O(10^9) operations. since most of the times time limit is 1 second or 2 second you can do as below most of the cases. If an array is given the size of 10^5 . so you can apply o(N)(10^5) or O(NlogN) (10^5*log(10^5)) kinda algorithm in that cases. If array size is like 5000 somthing you can apply O(N^2) or maybe sometimes O(N^3) algorithm. if size~100 you can apply O(N^4) algorithm. So main thing is in one second you can do 10^9 operations keeping in mind , on seeing constraints calculate upper bound and think accordingly. And one thing is no of test cases. It should be also consider in taking time complexity. Hope this helps.
•  » » » 11 months ago, # ^ |   0 got it. thanks :)
 » 11 months ago, # |   0 In G, if you use floyd with int values it will pass. But using long long is causing TLE.
 » 11 months ago, # |   +1 There's a typo in the editorial of F. The current remainder is denoted by cnt instead of rem
 » 11 months ago, # | ← Rev. 4 →   -23 [DELETED]
•  » » 11 months ago, # ^ |   0 Asked for help only to get downvoted. What's wrong in asking for help politely :(
•  » » » 11 months ago, # ^ |   0 Use "spoler" or just link the submission. It's not nice to scroll through codes in comment section
•  » » » » 11 months ago, # ^ |   0 Thanks for the tip! Updated.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Keep applying mod operation with function calls.I think this will be one of the easiest solutions of problem F to learn, I haven't use comments, but the code is clean though.
 » 11 months ago, # |   +5 Has anyone seen more problems like F? Editorial says it's a standard DP.Also, What are some other standard DP problems not commonly available?
•  » » 11 months ago, # ^ |   0 It's basically 0/1 knapsack DP in a 2d grid. For some other standard DP problem you can check CSES problemset DP section.
•  » » » 11 months ago, # ^ |   0 Actually, it's the variation in standard problems that's tough.It would be nice if you can share some problems which are a variation of these standard problems.
•  » » » » 11 months ago, # ^ |   0 Here are some problems you can try. link
•  » » » 11 months ago, # ^ |   0 https://codeforces.com/contest/1433/submission/96212192 Can you tell me where i am doing wrong in my code for problem F??
•  » » » » 11 months ago, # ^ |   0 You got diagnosis of your submission and it says array index out of bound.
•  » » » » » 11 months ago, # ^ |   0 No it showing wrong answer on test case 4??
•  » » » » 11 months ago, # ^ |   0 I think you must take sum in your dp with MOD; int val= solution(i,j+1,count-1,(sum+arr[i][j] % k)); (sum + arr[i][j]) % k try this
•  » » » » » 11 months ago, # ^ |   0 where to put this line?? my dp state storing sum of numbers why to store with mod??
•  » » » » » » 11 months ago, # ^ |   0 https://codeforces.com/contest/1433/submission/96227486I copy your code and set parentheses in this line
•  » » » » » » » 11 months ago, # ^ |   0 Yess i got it thats silly mistake thanks for your time
 » 11 months ago, # | ← Rev. 3 →   0 In the problem F,What happens when we initialize dp array with $0$ instead of INT_MIN or LLONG_MIN? I tried this and got wrong answer. But overall, the value of every state is going to become zero before we arrive that state during dp transition. So how does initialising values with zero go wrong?
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 Never mind.
•  » » 11 months ago, # ^ |   0 int_min denotes that this state is impossible. If you initialise it as 0, you can distinguish between impossible states and states with sum 0.
•  » » » 11 months ago, # ^ |   0 But, if the state is impossible, it will have 0 sum, as we won't be able to create an impossible state. Also, the minimum sum that can be created is 0, not $-inf$.You can check the Accepted submission, and the one with Wrong Answer. You can see, the code with zero initialised dp array creates a difference of 1 in the first testcase.
•  » » » » 11 months ago, # ^ |   0 Try inputting some larger cases, deviation will be much greater than one.
 » 11 months ago, # |   0 In problem E, why are we dividing by 2 in last step? Can Anyone explain in detail?
•  » » 11 months ago, # ^ |   +1 Suppose we select n/2 members in first dance group and then the rest n/2 will automatically form the next dance group. But the formula here considers that the first n/2 and rest n/2 are 2 different cases. Hence we need to divide the value by 2 to make them identical.
•  » » 11 months ago, # ^ |   +1 Every selection is accompanied by a rejection.For eg — S = {1, 2, 3, 4}There (6C2) ways to choose 2 elements. But suppose you select {1, 2} then {3, 4} is automatically selected. Now you don't want to select {3, 4} again and {1, 2}, because this will be counted twice. So to avoid counting again, we divide by 2.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +1 When we are taking C(n,n/2) we are counting how many ways we can take n/2 different elements from n elements. Let's say n = 1, 2, 3, 4, 5, 6, 7, 8we can take one round as (1, 2, 3, 4) and the other round will be (5, 6, 7, 8)we can take one round as (5, 6, 7, 8) and the other round will be (1 ,2, 3, 4)But both are the same configuration. So we are counting it twice, hence we need to divide the C(n, n/2) by two.
 » 11 months ago, # |   0 How much more time would be taken in reflecting the rating changes from this round 677? Or has the contest become unrated!?
 » 11 months ago, # | ← Rev. 2 →   0 Hello Everyone.... Can someone please explain why we multiplied with (n/2-1)! in E (two round dances) problem. UPD : Solved
•  » » 11 months ago, # ^ |   0 There are two round dances each time and each one can have (n/2-1)! permutations everytime.
•  » » 11 months ago, # ^ |   0 For n people in a circle, there are (n-1)! permutations in which they can be arranged
 » 11 months ago, # |   0 why does rating change for Div3 and educational rounds take sooooo long???
•  » » 11 months ago, # ^ |   0 because there is hacking phase of around 12 hours in these rounds.So after that system testing happens and ratings get updated.:)
•  » » » 11 months ago, # ^ |   0 It has been 5 hrs since the hacking phase ended.
 » 11 months ago, # |   0 Can F be solved with a greedy solution???
•  » » 11 months ago, # ^ |   0 I don't think it can. I tried sorting every row, taking last m/2 elements and if the sum is not divisible by k than removing the element which difference from the previous in its row is the smallest, but this doesn't work. It also doesn't work if you simply try to remove the smallest element you find. So I don't think you can solve it with some kind of greedy.
•  » » » 11 months ago, # ^ |   -8 We could do it this way, sort all the elements then for each max val "a", get a max val "b" from any row such the (a+b)%k == 0 and number of numbers taken from rows of "a" and "b" is not more than m/2.
•  » » » » 11 months ago, # ^ |   +1 It won't work, since it's possible for some "a", there does not exist "b" such that (a+b)%k==0 i.e, Cases where (a+b+c)%k==0, or sum of more number of elements will be div by k.
•  » » » » » 11 months ago, # ^ |   0 Ya that would surely fail my solution. Thanks for the replies
•  » » » » 11 months ago, # ^ |   +1 I don't see how that would work. What if the number of elements you can take is not even. What if for example you can take only 4 numbers (2 from 2 rows) and you can't find pairs such that (a + b) % k == 0 but sum of all 4 is divisible by k 2 4 10 1 1 5 9 1 1 2 4 Here the answer would be 20 but your algorithm would not even find that. Also you would have to pay attention to how many numbers have you taken from which row. So I don't think that works
•  » » » » » 11 months ago, # ^ |   0 Ya that would surely fail my solution. Thanks for the replies
 » 11 months ago, # |   0 @vovuh start system testing so we can get our rating :P..
 » 11 months ago, # |   0 @Vovuh when will the ratings be updated?
 » 11 months ago, # |   -7 When I do well in the contest: Why rating changes takes so much time!!?? When I do bad in the contest: Please anyone find a fault and announce as unrated! :D
 » 11 months ago, # | ← Rev. 2 →   0 Could anyone share similar dp problems like F, which use divisibility and sum constraints?
 » 11 months ago, # |   0 Problem D is directly DSU base https://codeforces.com/contest/1433/submission/96215593
 » 11 months ago, # |   +1 This contest is pretty easy. A speedrun is required like this contest.
 » 11 months ago, # |   0 I could not give live contest. But I gave virtual and I was able to solve 6 questions first time. Thank you VOVUH for the amazing contest.
 » 11 months ago, # |   0 for problem G, what is the disadvantage in this apporach: -> find shortest paths (not just lengths) for all delivery routes -> find the intersection paths among all and keep track of the largest weight -> set it to 0 then from the total cost , subtract , largest_weight*number_of_delivery_routes
•  » » 11 months ago, # ^ |   0 Your idea will fail in the 2nd sample. The largest weight will be 5 on the intersection paths but that's clearly not the edge we want to reduce to 0.
 » 11 months ago, # |   0 Lassan problems
 » 11 months ago, # | ← Rev. 2 →   0 There is another way of thinking the partitioning of the given set in Problem E. Instead of dividing $\binom{n}{n / 2}$ by $2$, we can fix some arbitrary element, let's say $1$, and count in how many ways we can choose the other elements in $1$'s subset. That is $\binom{n - 1}{n / 2 - 1}$. This way, we don't have to worry about counting some configurations twice or more. And this idea can be applied in more complex recurrences involving set partitioning, like Bell Numbers, where the divide by $2$ thing won't work anymore.
 » 11 months ago, # |   0 vovuh there is a typo in F's Editorial, the first paragraph:...., we took cnt elements in the row x and our current remainder is cnt.(this cnt should be rem)! Thank you!
 » 11 months ago, # |   0 int idx = -1; for (int i = 0; i < n; ++i) { if (a[i] != mx) continue; if (i > 0 && a[i — 1] != mx) idx = i + 1; if (i < n — 1 && a[i + 1] != mx) idx = i + 1; }In C ,I can't understand this iteration , can anybody please kindly explain this part ? or why does it work?
•  » » 11 months ago, # ^ |   0 This loop only looks at the largest elements because they can surely become dominant. For a pirana to be dominant it needs to have at least one pirana(left or right) that has smaller value. First if cheks for piranas on left. Second if cheks for piranas on right.
 » 11 months ago, # |   0 Wyh Dijstra work well in problem G?Is't it O(n^2 log m)?I think SPFA is faster.
•  » » 11 months ago, # ^ |   0 Dijkstra on sparse graphs: O(ElogV).Running V times is O(VElogV)
 » 11 months ago, # |   0 When will ratings update?
•  » » 11 months ago, # ^ |   0 Same Question
•  » » » 11 months ago, # ^ |   0 It's done already
•  » » » » 11 months ago, # ^ |   0 Oh! Yea
 » 11 months ago, # |   0 how many questions in the contest should i solve to become pupil ? i did A,B,C,D still in the bottom of the newbies. please help me !!!!!!!!
 » 11 months ago, # | ← Rev. 2 →   0 dp[x][y+1][cnt+1][(rem+ax,y)%k]=max(dp[x][y+1][cnt+1][(rem+ax,y)%k],dp[x][y][cnt][rem]+axy)I am not able to understand this transition. What does dp[x][y][cnt][rem]+axy exactly mean?UPD : Understood. We are looking whether or not it is beneficial to take the current element or not.
 » 11 months ago, # |   0 vovuh What would be the Worst Case Time Complexity for the problem F using this DP approach.
 » 11 months ago, # |   0 Hi, for problem F, I submitted 2 codes. One has dp array initialized to -1, other has it initialized to -2.-1 works and gives Accepted but -2 doesnt. Why so?-1 => 96209145-2=> 96263305
•  » » 11 months ago, # ^ |   +4 memset(dp, -2, sizeof(dp)); does not do what you think it does.memset sets the value of every byte, not the actual element on the array. 0 and -1 works as intended because their binary representations have all zeroes and ones respectively.
•  » » » 11 months ago, # ^ |   0 Ohhhhh..... thanks a lot. I understood now. so memset(dp, 5, sizeof(dp)) is also wrong?
•  » » » » 11 months ago, # ^ |   +1 It's not "wrong", it will do what it's supposed to do- set all bytes to 1, 0, 1 continuously.It won't replace every elements with 5.
•  » » » » » 11 months ago, # ^ |   0 oh so for array of bits of size 5 called dp, memset(dp,5,sizeof(dp)) will do-> 1,0,1,1,0 ??
•  » » » » » » 11 months ago, # ^ |   +1 Bytes, not bits. So, every 8 bits of the array will be converted to 10100000.I'm not sure if that's reliable enough though.
•  » » » » » » » 11 months ago, # ^ |   0 Ok ok got it. Thanks a lot :))
•  » » 11 months ago, # ^ |   +1 memset(dp, -2, sizeof(dp)); -2 is illegal， only 0, -1 or some Hexadecimal number like 0x3f3f3f3f
 » 11 months ago, # |   0 I still dint understand what ordered pairs are being talked about . How are we double counting. Could someone please explain ?
•  » » 11 months ago, # ^ |   0 The double-counting essentially occurs in the first step, when you choose half of the dancers. For example, if you take abcd for the first set and efgh for the second, it is considered different from taking efgh for the first and abcd for the second. These two orderings are the same to us, so we need to divide by two.
 » 11 months ago, # |   0 Can Anyone help me up with Problem F I didn't get the overall concept. Thankyou
 » 11 months ago, # |   0 MyCode Can anyone help me? My code almost same as the standard solution, but get wrong answer on test 3
 » 11 months ago, # |   0 the tutorial for problem C is wrong for the example test case:n=5; arr=[5,3,4,4,5];resultant output=5 expected output=3any helps regarding this?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Both are correct!If the output is 5, 5 eats 4, 3, 2, 1.[5,3,4,4,5] -> [5,3,4,6] -> [5,3,7] -> [5,8] -> [9]If the output is 3, 3 eats 2, 4, 5, 1.[5,3,4,4,5] -> [5,5,4,5] -> [5,6,5] -> [5,7] -> [8]
•  » » » 11 months ago, # ^ |   0 thank you very much for the clarification
 » 11 months ago, # |   0 Can someone suggest a good resource to understand F.It says this is a standard dynamic programming problem but I am having trouble understanding it. Any similar problems?
•  » » 11 months ago, # ^ |   0 It is a variation of knapsack problem.
 » 11 months ago, # |   0 96297177 code for F with comments
•  » » 11 months ago, # ^ |   0 great job!
•  » » 11 months ago, # ^ |   0 Nice!
 » 11 months ago, # | ← Rev. 3 →   +1 The problems were fine, but I don't think E is an appropriate problem, 2 reasons.1)99% Math (Which is still fine, as most algorithm problems can be restated as Math problem, though this was a bit direct)2) OEIS (I hate using OEIS, and I hate problems that allows to use OEIS, because there is literally no fun in it, and we don't learn anything new and you are caught when asked to do the same problem in onsite, but Div3 is a sprint race, when most of them use oeis and you don't, your rating suffers)P.S. You don't even have to think of a few cases, you can copy paste 12164510040883200 in the OEIS search
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 I have no problem with a little of combinatorics, but OEIS feels like cheating. And our friend 1000000007 would have easily done away with that.
 » 11 months ago, # | ← Rev. 2 →   0 If we are (i,j) then why are we taking the state dp[i][j+1]? Shouldn't we take dp[i][j]?
 » 11 months ago, # |   0 Regarding F. Zero Remainder Sum: Can someone PLEASE tell me how can I make this code faster 96316767. I've been trying to figure it out all day. It is exceeding the Time limit test 6.
 » 11 months ago, # |   0 This is the second time I joined in the Codeforces contests. Such a nice one!
 » 11 months ago, # | ← Rev. 5 →   0 A solution for problem E that leads directly to the reduced formula:There are $(n-1)!$ ways for $n$ people to form a single round dance. Form two round dances from such a dance: one dance from people at odd positions, and the other — from people at even positions. There is a unique way to split a dance this way. On the other hand, two round dances of $\frac {n} {2}$ people each can be merged into $\frac {n} {2}$ different round dances of $n$ people.Thus the answer is $\frac {(n-1)!} {\frac{n}{2}}$.
•  » » 11 months ago, # ^ | ← Rev. 4 →   0 I cannot understand the last part two round dances of n/2 people each can be merged into n/2 different round dances of n people. You said each can be merged into n/2 same round dances. Then shouldn't we divide by (n/2)*(n/2) ? Are abcd efgh and bcda fghe two different combination?? Could you please clarify a little more..?
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Merge two round dances with $\frac{n}{2}$ people each into a round dance of $n$ people by placing the people from the first dance at odd positions, and the people from the second dance at even positions, preserving their respective orders. Then, fixing the set of people at odd positions and rotating the set of people at even positions, we get $\frac{n}{2}$ different circular arrangements of $n$ people all of which are obtained by merging the initial two arrangements.
•  » » » 11 months ago, # ^ | ← Rev. 3 →   0 You merge two circular arrangements of $\frac{n}{2}$ people in a way that after splitting the result as described in the beginning you get the same two arrangements. And there are $\frac{n}{2}$ ways to do it.
•  » » » » 11 months ago, # ^ |   0 Got it finally! Thanks. That was a cool solution btw..
 » 11 months ago, # | ← Rev. 2 →   0 I don't understand why the answer is dp[n][0][0][0] in problem F
 » 11 months ago, # |   0 plz conduct div3 regularly..
 » 11 months ago, # | ← Rev. 2 →   0 In problem F: The transitions from the last element of the row are almost the same, but the next element is a[x+1][0] and the new value of cnt is always zero.Why cnt is equal to 0, even if we take the current element?
 » 11 months ago, # |   0 THe contest was great. But I noticed that the Problem B is almost the same as the problem A Educational Round 82. Here's the link: https://codeforces.com/contest/1303/problem/A
 » 11 months ago, # |   0 In OEIS when I type the sequence 1,3, 40, 1260, 72576, 6652800, 889574400, 163459296000, 39520825344000, 12164510040883200 I got a(n) = (2*n + 1)!/(n + 1). This as result Can someone tell me what is n here??
 » 10 months ago, # |   0 Watch my solution of District Connection in-depth solution and approach building on how to achieve solution . Do check it out . Like share and subscribe to my channel. https://www.youtube.com/watch?v=KqQXJKiFOlg
 » 10 months ago, # |   0 Prob F Im unable to understand the need for this check- if (dp[i][j][cnt][rem] == -INF) continue;
 » 8 months ago, # |   0 my solution for problem G is somewhat same as that given in the tutorial, however, I am getting TLE. any suggestion? link to solution — https://codeforces.com/contest/1433/submission/104609982
 » 2 months ago, # |   0 i wish if any one can tell me what the last line of B problem solution do
•  » » 7 weeks ago, # ^ |   0 count(a.begin(), a.end(), 0) the function count the passing element in the vector , here the number zero passed , and this line print the numbers of zero in this vectors begin to vectors end :3 i hope u got it now :3****__
•  » » » 6 weeks ago, # ^ |   0 i got it thank you
•  » » » » 6 weeks ago, # ^ |   0 Welcome bro :)