### Peteris's blog

By Peteris, 9 years ago, ,

Hello,

This popped in my head as an interesting problem to know the answer for. I could work this out myself, but I'm hoping someone has it off the top of their head or is more motivated :).

The usual form of the inclusion-exclusion principle or PIE is as follows

Clearly, there are also expressions of the following form

And of this form

Are there closed forms for (bij), (cij) of which especially the latter, I'm sure, could be useful in some problems.

• +8

By Peteris, 9 years ago, ,

I wrote the following solution in CF #72 for Problem B in Ruby:

1. n, k = gets.split.map{|_|_.to_i}
2. a = gets.split.map{|_|_.to_i}

3. b = a.sort
4. if (a.length == 1 ? a[0] : a.inject{|x,y| x + y}) <= k
5.   puts -1
6. else
7.   i = 0
8.   s = 0
9.   while (b[i] - s) * (n - i) <= k
10.     k -= (b[i] - s) * (n - i)
11.     s = b[i]
12.     i += 1
13.   end
14.   while b[i] - s == 0
15.     i += 1
16.   end

17.   t = k / (n - i)
18.   k -= t * (n - i)

19.   j = 0
20.   while k > 0
21.     if a[j] >= b[i]
22.       a[j] -= 1
23.       k -= 1
24.     end
25.     j += 1
26.   end

27.   ans = ""
28.   for k in j...n
29.     if a[k] > t + s
30.       ans += (k + 1).to_s + " "
31.     end
32.   end
33.   for k in 0...j
34.     if a[k] > t + s
35.       ans += (k + 1).to_s + " "
36.     end
37.   end
38.   puts ans.strip
39. end

It worked fine on my computer, but on the server, it fails for case 5:

Test: #5, time: 80 ms., memory: 3408 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Input
1 1
1

Output
-1


Checker Log
wrong answer Output contains longer sequence [length = 1], but answer contains 0 elements

Any Ruby gurus have a clue?

• 0

By Peteris, 9 years ago, ,

What is the best way to embed source code in Codeforces currently? One way is by using pre tags:

int main()
{
for (int i = 0; i < n; ++i)
printf("testing %lf%%\n", (i + .5) * 100 / n);
return 0;
}


• 0

By Peteris, 9 years ago, ,

Due to the rapidly accumulating user content, a natural question to ask: what is the current idiom of looking for blog posts and comments containing a given query? I couldn't find a search field for this anywhere on the site albeit there is one for handles. The site is, however, searchable in Google, but it isn't nearly as convenient as a built-in solution would be. How about it?

P.S. A way to search for tags is to use the url http://codeforces.com/search?query=yourquery, where yourquery is the tag you're looking for.

• 0

By Peteris, 10 years ago, ,
Next time something like this happens, it would be nice to have the problem statements available elsewhere. In this contest, an user was generous enough to provide pastes of some of the problems in TopCoder. It was helpful as I couldn't access the problems on a regular basis even at the end of the contest. Would it be possible to provide a mirror of the problem statements at the beginning (or 5 minutes after the beginning) of a contest in case the server is unresponsive or simply slow?

• +2

By Peteris, 10 years ago, ,

My first contest here has left a positive impression. There were some technical difficulties in the beginning, but the administrators successfully got rid of them. The server was quite snappy throughout and the problem statements were well written in my opinion.

On the solving side, I didn't do anything more than glance at problems D and E. Spent a lot of time debugging B, but couldn't find a failing testcase. Not even after generating random ones and comparing with a friend's correct solution. Problem C was also an implementation problem, yet I lost two penalty points there by 1) forgetting about 64-bit integers; 2) using %lld instead of %I64d in printf. Not to mention the time spent trying to figure out what (else) had went wrong.

Overall, still a very good format. 2 hours is probably short enough to devote my time to and the problems seemed to be well varied in terms of difficulty. I hope that I can clear the first three next time.

• +4

By Peteris, 10 years ago, ,
See you tommorow ;).

• 0

By Peteris, 10 years ago, ,

Looking forward to taking part in a Codeforces round. Lacking some spare time to do so in the moment.