The 250, 600, 900 distribution was threatening this match to repeat the pattern of SRM 490. So I knew I had to be fast in this problem, and tried hard to do it... It didn't work.
Ok... so we always have 6 faces in the dice. We want to count the number of ways to assign the faces such that the sum of all opposite faces is equal and greater than or equal to K and the faces are different numbers from 1 to N.
Err, wait, how are two dices different exactly? The statement said that they are equal if you can rotate one to become the other. Well, that was a little confusing to me. What really helped was to notice that the first example had N=6, K=7 (normal 6 faces dice) and the result was 2.
Why two? Well, there are 3 pairs of numbers that give 7 as result, so there are C(3,3)=1 ways to pick the pairs, then according to word of God, there are two ways to assign these pairs to the dice. I decided to trust the problem setter on this.
So with fixed sum, we can count the number t of available pairs that give such sum, then 2*C(t, 3) is the number of ways to have dice that have opposite faces that sum sum.
Now we can just iterate from sum=K to 2*N (minimum and maximum sum value possible), and add up the totals.
Finding the number of pairs is easy, we can just iterate starting from x=1 , the opposite face must be (sum-x), so (sum-x > x) (because if that was not the case, we already counted this pair) and also (1 <= sum-x <= N). We just need to count the total values of x that follow those runs. This takes O(N) steps. The iteration for the sum value takes another O(N) steps. So the total complexity is O(N*N). The solution is then "simple" , except for calculating C(t, 3) . For some silly reason I used Pascal's triangle. Which introduced a silly bug, I had a [2001][3] array when I needed a [2001][4] array. Lame lame. Instead, it is better to just use t*(t-1)*(t-2) / 6 (that's what you get from manually calculating C(t,3).
long long theCount(int N, int K)
{
long long ways = 0;
//iterate through all possible face sums:
for (int s=K; s<=N+N; s++) {
long long t=0;
//count the number of face pairs that yield s as sum:
for (int x=1; (s-x>x) && (x<=N); x++) {
if(s-x<=N) {
t++;
}
}
if(t>=3) {
// add C(t,3)*2 to the result, it neatly translates to:
ways += (t*(t-1)*(t-2)) / 3;
}
}
return ways;
}
PrefixTree
I was wrong, unlike SRM 490, this medium turned out to be approachable without mass implementation issues. It was also in my opinion, beautiful , will elaborate later.
Update: Explanation for div1 600
Hard problem (whatever the name)
I had enough time to open it, but was clueless. During the challenge phase I found out it could have been used with min-cost max flow and binary search, that's crazy.
Challenge phase
This should underline neal_wu 's awesomeness. Before the challenge phase, I noticed there was a 600-pointer submission by a blue coder. So I rushed to open it quickly at the start of the challenge phase, and just as I finished reading the first three lines, it was already challenged by neal_wu. He later said he quickly noticed the guy wasn't picking all the subsets so he just gave it a random large challenge.
Rating and issues
Well, I had a chance to see for a second what my rating would become if this match is rated: 2035 ! That would mean I recovered from the losses of last match. Unfortunately, it appears that it won't be rated due to issues during the challenge phase :(.
0 comments:
Post a Comment