We will hold AtCoder Beginner Contest 159.
- Contest URL: https://atcoder.jp/contests/abc159
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200322T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: DEGwer, kyopro_friends, latte0119, namonakiacc, satashun, tempura0224, EnumerativeCombinatorics, yokozuna57
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
How to solve E?
brute force over all possible lines for the rows. Then solve greedily for columns.
What is the greedy for columns?
For every "block" (rows between two horizontal cuts), maintain count of 1's for each column.
So if you had something like:
Let's say currently you're making cuts under rows 1 and 3 (1-based), so it'd be something like:
Now maintain count of 1's for each block at each column:
You know that if in any block, any count is bigger than k, than this horizontal cut setup is impossible, so you can just try the next mask.
But in this case, let's say $$$k=2$$$. Now iterate through each column and each block and maintain one horizontal sum for each block, if at any index $$$i$$$ $$$\text{horizontal sum of some block} > k$$$, than you have to make a cut, and sum in each block becomes the i-th element in that block.
So in the first block and second block, sum of the first three elements will exceed k, so you will make a cut there and sum will reset ($$$sum[1] = 1, sum[2] = 2, sum[3] = 1)$$$.
Welp, hope that explanation wasn't terrible haha.
Thanks a lot, you explained far better than the editorial.
Go through the array column by column. If the group size exceeds k for any of the groups in a column, we draw a line before the column and update the size of each group.
Another way to understand greedy is to solve the 1-D problem; A = [1 1 0 0 1 ... etc]. In this case you will obviously keep going as far as possible until you need to make a cut. "As far as possible" means until your current sum exceeds K. Then extending this idea to the columns is easy.
For splits across rows, try out all 2^r (actually 2^(r-1)) splits, for e.g using bit masks. Then greedily perform splits across the columns.
Why should I go over 0 to 2^(h-1). Can anyone explain this in detail please :(
Coz you are checking all possible combination. Suppose you have 3 rows, then row-wise you have 2 possible lines to cut the bar ( one line between 1st and 2nd row, and another between 2nd and 3rd row ), generally speaking in a N row bar you have (N-1) lines to possibly cut the bar. Now you don't know which lines you should cut through to have MINIMUM value of cuts and meet the condition, so you check all possibilities. In our example, [ 0 , 2^(3-1) — 1 ] == [ 0, 3 ]. If you observe the binary representation of the numbers,
decimal --> binary --> interpretation
0 --> 00 --> No cut is needed row-wise
1 --> 01 --> Cut only through the 2nd line
2 --> 10 --> Cut only through the 1st line
3 --> 11 --> Cut through all the lines
If you observe carefully the binary representation of numbers from [ 0, 2^(n) — 1] actually contains all possible combination for n items as described above. It is a simple trick we use in cp.
Hey makes sense to me thank you for the reply :) care to explain what to do in each and every combination.
If you want to see solution, You can see my submission, if you still have any doubt. i have used naming convention related to my approch such that someone can understand it !!
How to solve F?
Let $$$\mathrm{dp}[i][j]$$$ be the sum of left endpoints of all sequences that end at $$$i$$$ and have weight $$$j$$$. The answer is $$$\sum_{i = 1}^n (n - i + 1) \mathrm{dp}[i][S]$$$.
I understand that we basically add for all i,j of subsequences the pairs of indexes including i,j. That is all where left is less or eq i, and right bg j.
But I do not get how we find all i,j of subseqs with sum==s? And even not the sum of the i?
I don't understand a word of what you just said, but I'll try to elaborate a bit. If we have a subsequence with sum $$$S$$$ that starts at $$$l$$$ and ends at $$$r$$$, its contribution to the answer is $$$l (n - r + 1)$$$. That's because it is contained in $$$f(L, R)$$$ exactly if $$$L \le l$$$ and $$$r \le R$$$.
We can think of it like this. There are many different subsequences with left endpoint $$$l$$$ and right endpoint $$$r$$$, suppose the $$$i$$$-th of them has left endpoint $$$l_i$$$ and right endpoint $$$r_i$$$. Then the answer to the problem looks like
(Obviously, this sum is too large to calculate directly, it is just to help with thinking.)
Let's look at one particular $r$ and all the summands of the form $$$l_i (n - r + 1)$$$. That part of the sum above looks like
So, we are interested in the sum of left endpoints of all subsequences with weight $S$ that end at $$$r$$$.
This can be calculated through dynamic programming. As I stated above, define $$$\mathrm{dp}[i][j]$$$ as the sum of left endpoints of all subsequences with weight $$$j$$$ that end at $$$i$$$. Then we can calculate it for all $$$i$$$ like:
Isn't this O(N*N*S) ?
No, it is $$$\mathcal{O}(NS)$$$. We can calculate the last formula using standard prefix sums.
Will there be illegal transitions?As dp[k][j-A[i]](k<i,j>A[i])->dp[i][j],but A[k]>A[i]. According to the problem statement, this is a illegal transition.
Made a mistake reading the statement.233
Hint :
Consider a sequence Ai...Aj...Ak ,that ∑A = S.
There are i*(n-k+1) pairs that contain this.
For each k(the last index in the sequence) , We must know ∑i(the first index)
Dp[i][j] means the sum of (the first index) of the sequences that the sum of that is j.
You can update the Dp easily.
Then consider the i-th element as the last one,the answer add (n-i+1)*(dp[i-1][s-a[i]])
Just one optimization, but i believe E can also be solved considering (2^(H-1)) masks.
can you please explain your logic?
For reducing the mask value, you could do a recursion for each row based on the assumption if ith row remains together with (i-1)th row or not after all the cuts are made.So we only do this differently (2^(H-1)) times, because 1st row doesn't have any preceding row, so it is assigned any relation with a previous row. Or simply just select (H-1) bits for masking where ith bit denotes if (i+1)th row is together with ith row or not in the final cut. Edit : 0 based indexing used here
Thank you:)
For problem E, does some fail in test6 and pass at last? I've been struggling for quite a while, my code status.Thanks in advance.
Supplementary editorial for questions 2, 4, 5, 6 AtCoder ABC 159
Hey guys, does any of you got to read the editorial for problem F and can help me understand the transitions for the DP? It seems quite interesting.
I don't understand why at this point when we calculate
dp[i+1][j+a[i]][2]
we have to includedp[i][j][0]
, why should we add R without actually adding the L ?Thank you in advance for help.
Can you tell the meaning of Adding Only L , not adding L and R , adding both L and R ?? TheRedLegend
As far as I understand it, we can start a new interval at each
i
, where1 <= i <= n
, this means that we set L(t = 1)
to mark the beginning, then we can stop and interval meaning that we set R(t = 2)
(but when setting R we need to have set L before, I understand this as transition betweent = 1
tot = 2
). We can set R at any position from[i..n]
. And being betweenL
andR
we can add elements to the partial sum.When you think about this for a while you can easily notice that we will have
L
at any position and thenR
after L soL <= R
, this meaning that we will iterate through all the possibleL
andR
.I think this is the logic but I am not 100% sure. Still I don't understand why when computing
dp[i+1][j+a[i]][2]
we have to includedp[i][j][0]
.Can someone explain tmwilliamlin168's solution for F? https://atcoder.jp/contests/abc159/submissions/11099994
As far as I see,
dp[i][j]
is the answer for the first $$$i$$$th number if the required sum is $$$j$$$.When we are processing the new number $$$x$$$, obviously the previous sequence could be reused. Now consider how the new number could contribute to answer: First, itself could be a sequence so
dp[i][x]=i
. Then it could also form a sequence with previous sequences sodp[i][j]+=dp[i-1][j-x]
for all $$$j\ge x$$$where can I find solutions in English?
This may seems weird but can anyone explain the idea of C?
Sadly i couldn't understand what was written in the editorial..
Have to find the maximum volume. As we know when l == b then area of rectangle is maximum . In the same way in three dimensions you should have all sides same to get max volume of cuboid i.e. cube so each side become L/3,L/3,L/3 volume
L*L*L/27
F can be solved with O(S) memory also. Submission