How about this? I will write this before the contest starts and see how it really goes.
Since the last time I set problems I tried very hard to come up with problems for a SRM, it took long. Eventually though I had what looked like a SRM, I had a problem that was similar to BricksN (The div1 500) but harder and I thought it was good as div1 hard. I had some other problem for div1 500. The idea for the remaining slots was to finally use CountingSeries, a problem I created eons ago as a div1 250. And then use whatever is needed for div2 250 and div2 1000 (probably an easier version of the other problems).
It turns out that the idea I had for div 1 500 was very boring. In fact, it was very hard for me to come up with a good div1 500. Which is strange because usually that and div1 250 are the easier ones to make. After trying and trying, I had an idea for a interesting div2 250. Which I noticed that could be turned into a good div1 500 with some modifications. Finally, the admins liked the setting.
There was an issue though, it turns out that the idea I had for div1 1000 was, although interesting, very hard. In fact, the whole problem set was looking hard. So, we moved div1 500 to div1 900 and modified BricksN to become a different, easier problem.
My gut right now tells me that the problem set faded from something that was going to be very hard to something that is very easy. Except in division 2, it is probably going to be harder than usual.
Div2 250 - AlphabetPath (link to problem statement)
This indeed seems harder to me than your average division 2 easy. But there is a way to implement quickly. First of all, two cells (x1,y1) and (y1, y2) are adjacent if and only if abs(x1 - x2) + abs(y1 - y2) is exactly 1.
The constraints also say that there will always be exactly one instance of each letter.
What we can do as a solution is to iterate from 'A' to 'Z', find the character in the matrix, verify that it is adjacent to the previous one, and save its position so that when the next character verifies, it knows the position to verify.
Div2 500 / Div1 250 - CountingSeries (link to problem statement)
This problem started as a potentially dangerously tricky, think about it, there could be many evil cases if the constraints are loosened a little. In the first instance, all numbers were at most 10^12.
The idea in this case is that all the elements of the geometric progression less than or equal to upperBound can be enumerated rather quickly (There are only log(upperBound) of them). The total number of numbers that belong to the arithmetic progression and are smaller than upperBound can be computed in O(1) through a division. It is also easy to verify if a given number belongs to the arithmetic progression. So what we can do is enumerate the geometric progression and for each of the elements, verify if it belongs to the arithmetic progression, and count the ones that dont. Then add the elements of the arithmetic progression to the previous result for the final result.
I think that the problem will now not be very tricky and there will not be many challenges to it. We will see though.
Div2 1000 - Bricks31 (link to problem statement)
It is a standard dp with bitmasks problem. First, think of a recurrence F(h, previous). Where h is the number of brick layers to add and previous is the layer we have already decided. previous[i] is true if the previous layer had a part of a brick at position i. Initially, previous will be a size-w set of placed bricks.
For simplicity, we will represent previous not as a boolean array or set but as a integer representing a bitmask. The i-th bit of previous will be 1 if we consider previous[i] to be true.
To solve F(h,previous), consider all the 2w masks that can be placed on top of previous. Then for each mask NewMask of them, calculate F(h-1, NewMask) that is, the number of ways to fill h-1 layers of bricks on top of the new layer NewMask. You also need W(NewMask, previous), the total number of ways to place NewMask on top of previous. The result is the sum of F(h-1, NewMask) * W(NewMask, previous).
But this approach may be hard to implement (The W part is difficult). But there is a fix. Let us instead consider F(h, previous, x). This time x denotes the number of spaces in the current layer that were already decided. This time, previous[i] will hold the used bricks for both the current and the previous layer. When i < x, previous[i] contains the used positions in the current layer, otherwise, it contains the used positions in the previous layer.
For every position x, you can decide to add a brick of size 1, 2 or 3 or no brick at all. For no brick at all, the result becomes F(h, x+1, remove x-th bit of previous ). For one brick, first verify that previous[x] is 1. Then the total is F(h, x+1, previous). For a brick of length 3, verify that previous[x] and previous[x+2] are 1, the result is then F(h, x+1, previous (mark bit # x+1 as used) ).
The base case is when h=0, there is only one way to do it - the empty structure. A special case is F(h, w, previous), this is equal to F(h-1, 0, previous).
Hopefully the editorial will be clearer in explaining an easy solution for this problem.
Div1 500 - BricksN (link to problem statement)
Think about it, like in the previous problem, the state is dependent on the bricks bellow the current layer. However, it is no longer possible to place parts of a brick on top of empty air. Consider the sub-problem after we placed a pattern of bricks ###..##.# in the first layer: It is not possible to ever put together the first group of bricks with the second or the third.
So, we can solve for each of these islands separately. The result is then: F(3, h) * F(2, h) * F(1, h).
This yields an easy dynamic programming solution. Let F(w,h) be the function that solves the problem and let G(w) the total number of ways to have a set of continuous bricks of width w. Then as a solution for F(w,h) you can decide where to put the first empty space. Let the position of the first empty space be x. Then the solution for that case is : G(x)*F(x,h-1)*F(w - x - 1, h).
G(w) is easy to calculate. You can start the group of w contiguous positions with a brick of size 1, 2, ... or k. So, the solution is : G(w) = G(w-1) + G(w-2) + ... G(w- k).
I am not giving out details about the harder version of this problem because I still hope I can use the idea in a later match.
I actually made the images in this problem and bricks31 using plain old Inkscape, you got to admit the quality is great.
Div1 900 - AlphabetPaths (link to problem statement)
This one is actually very easy once you figure something out. There are only 21 possible letters. Let us estimate how long will a bruteforce solution take. If we start at a given cell, we will have at most 4 options for each consecutive letter. That is 4^21. 4^21 is large.
... However, 4^10 is not large.
Imagine you are located at a cell. And want to count the total number of paths such that the cell is the 11-th cell. This means that the cell will be a bridge connecting two paths of 10 cells adjacent to the picked cell. Let us say you have found one of those paths. There are only at most 4^10 of them, so for each of them, we will like to count the total number of other paths of 10 cells also adjacent to the picked cell that could be valid continuations for the picked path - this is possible if you save the bitmasks of letters used by each path and the total number of ways to do it.
In essence, this is just a meet in the middle problem.
A concern during development was if normal bruteforce with optimizations could work. We tried to raise the constraints as much as possible. I really doubt something other than meet in the middle will work. But we shall see.
The whole Latin alphabet stuff was something I did to camouflage the fact that there are only 21 letters. At first, I intended it to include alphabets of A to Z, but it was not really possible to use meet in the middle there. So I changed it to (A to U), but that looks silly. I googled for "alphabets with 21 letters" and lucky me, original Latin had 21 letters.
Update: Here you can find a slightly more detailed explanation, and code for this problem even though the post is about a general trick.
Predictions
I think that division 2 coders will complain about the match being too hard and division 1 coders about the match being too easy.
Really hope there are no technical issues (or issues caused by something I missed regarding the problems) during the match.
Addendum
Everything before this part is what I wrote before the coding phase. Now some thoughts:
- I messed out the images showing all the 84 structures. Apparently change blindness makes you unable to notice that there are some repeated structures until it is very late.
- It turns out the SRM was way harder than I thought... I am sorry for not including a > upperBound in the examples of 250.
No comments :
Post a Comment