Educational Codeforces Round 123 Editorial
source link: http://codeforces.com/blog/entry/100227
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Tutorial of 
12 hours ago, # |
Approach of D problem was great
-
yup, somewhat similar to this question's approach( two contests ago) https://codeforces.com/problemset/problem/1638/D
In problem D why we process the queries backward?
-
When you process backwards, the query is equivalent to "color all squares in this row and column which are not yet colored". This way, each square will be colored at most once. So now your answer will be raised to some power(which is actually the number of queries where at least one square was colored).
-
I processed all the queries forwards but ended up getting WA, but I am unable to understand how is there a difference between processing it forwards or backwards? Even if we are doing it forwards then, yes it might be possible that some square is getting colored more than once but in the end I am counting the different number of colors for all the squares so that shouldn't make a difference.
-
For each query you want to determine something that happens in the future — in the later queries. So to tell something about query , you have to first process queries ... That is exactly the same as going backwards over queries: you first determine the status of the query, then add the information about it to stone data structure.
-
Failing testcase for your approach: Ticket 587
-
Can anyone help why is this giving me TLE for D 147473308 ?
-
You have initialized arrays visr and visc of size n and m respectively. Hence your time complexity is O(t*(n+m)) or larger, which in the worst case will be 2*1e9 since there is no limit on sum of m,n over all test cases.
8 hours ago, # |
I appreciate all the work that all problem setters and editorialists put in creating problems and writing editorials, but I want to know why there's a delay of almost a day between contest ending and editorials getting out? The excitement and the curiosity fade away (at least for me) due to such a long delay...
7 hours ago, # |
If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com
Problems added: "A, B, C, D, E, F".
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
6 hours ago, # |
No need for FFT in problem since we need only sum of those Stirling's number and this can be done in O(i): Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have:
S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ).
Let d = j-t, then ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed
C can be done with 2D DP. My submission is linked below 147347109
Note that I only used the custom "getbigger" function instead of the max function because the max function was being annoying for me.
Here are two alternate solutions for F. (Neither one uses any prior knowledge about the Stirling numbers.)
6 hours ago, # |
Can someone help me understand why we need the break condition in D? What are those cases requiring that break?
-
Let's say after i'th query you get all rows (column can be anything) in the query. This would mean that whatever colours were present in all the cells before, are updated (possibly to the same colour but updated for sure) so any query that was processed before i'th query is no longer relevant to the final state. If however, we do process them in reverse order, it will update colour of some cell which shouldn't have been the case. Same goes for queries covering all columns instead of rows hence we have to check for both.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK