amateurcoder's blog

By amateurcoder, history, 8 years ago, In English

Problem link: Light OJ 1392.

Please give it a read. If I understood correctly, given R, T, N, it asks to find number of pairs (r, t) with 0 ≤ r < R, 0 ≤ t < T such that there exists integers a1, ..., ar whose sum is t and each of the numbers ai is between 1 and N (inclusive). Constraints are 1 ≤ R ≤ 108, 1 ≤ T ≤ 4 * 108, 2 ≤ N ≤ 20.

But then for a fixed r, all t between r and Nr should be reachable (others are not reachable because each of the r variables is at least 1 and at most N). So I ran a brute force (to check), but they don't match the sample.

Code: here.

Interesting enough, the output of the brute force for each sample is exactly 26 more than actual answer. Where did I go wrong?

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Ok, you assumed the situation the second team will be given, wouldn't have to abide by any rules. For example, the r = 2 and t = 1, is just not a valid situation because the team has to score at least one point per game. So saying that the team scored 1 point in 2 games doesn't make sense. So these situations can't be given to the second team. You are overcounting these situations. I wrote an actual and two brute solutions for this problem. But all of them give 1 more than the sample. I really don't know what is going wrong with my brute force. Can you check my brute force code and check for any mistake ? Brute Force code with comments

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    I've just got accepted in the problem. Apparently the setter's solution does not include the case Tint = T and Rint = R. So the correct constraint is 1 ≤ Tint < T and 1 ≤ Rint < R.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thanks, Alpha_Q. I've got AC now. I had to take care of another thing to get AC though. The judge data contains cases where R < T and also cases where R > T*n. I assumed that Judge data will contain only valid situations for the first team. So my code was generating negative outputs for these cases. I had to check for these cases at the beginning and print 0 for them to get AC. Btw Alpha_Q, is your solution O(1) ? I solved it using

Spoiler
»
8 years ago, # |
Rev. 6   Vote: I like it +3 Vote: I do not like it

Yes, my solution is .

 
SPOILER AHEAD!