Peteris's blog

On PIEs
By Peteris, 14 years ago, In English

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.

Full text and comments »

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

CF #72 Ruby issue
By Peteris, 14 years ago, In English

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}

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

  19.   t = k / (n - i)
  20.   k -= t * (n - i)

  22.   j = 0
  23.   while k > 0
  24.     if a[j] >= b[i]
  25.       a[j] -= 1
  26.       k -= 1
  27.     end
  28.     j += 1
  29.   end

  31.   ans = ""
  32.   for k in j...n
  33.     if a[k] > t + s
  34.       ans += (k + 1).to_s + " "
  35.     end
  36.   end
  37.   for k in 0...j
  38.     if a[k] > t + s
  39.       ans += (k + 1).to_s + " "
  40.     end
  41.   end
  42.   puts ans.strip
  43. 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
Answer
Checker Log
wrong answer Output contains longer sequence [length = 1], but answer contains 0 elements

Any Ruby gurus have a clue?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

Formatting code
By Peteris, 14 years ago, In English

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;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

Searching codeforces
By Peteris, 15 years ago, In English

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://mirror.codeforces.com/search?query=yourquery, where yourquery is the tag you're looking for.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

Mirror for problem statements
By Peteris, 15 years ago, In English
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?

Full text and comments »

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

Beta Round #7 Report
By Peteris, 15 years ago, In English

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.

Full text and comments »

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

Codeforces #7
By Peteris, 15 years ago, In English
See you tommorow ;).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

First (test) blog post and self introduction
By Peteris, 15 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it