Peteris's blog

By Peteris, 9 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.

Read more »

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

By Peteris, 9 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}

  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
Answer
 
Checker Log
wrong answer Output contains longer sequence [length = 1], but answer contains 0 elements

Any Ruby gurus have a clue?

Read more »

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

By Peteris, 9 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;
}

Read more »

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

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

Read more »

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

By Peteris, 10 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?

Read more »

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

By Peteris, 10 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.

Read more »

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

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

Read more »

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

By Peteris, 10 years ago, In English,

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

Read more »

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