sillycross's blog

By sillycross, 7 years ago, In English,

I doubt whether the standard solution for problem E is correct.

The problem is: when two center's distance is smaller than 2R, the two circles may still be separated on the grid matrix.

Consider the following case:

Circle 1: center (0,0) radius 14

Circle 2: center (20,19) radius 14

The eculid distance between center is , which is less than 28.

However, the 2 circles do not intersect on a grid matrix, since no integer coodinate falls on their intersection area. So the 2 circles are still valid solution.

But it seems that the standard solution did not consider this special case. I (and many others) got wa on test 20. After I changed the intersect checking to "center distance<=2R" it got accepted.

solution: http://codeforces.com/contest/363/submission/5067126 notice the quoted code between line 77 and 82. after removing these codes the solution got WA.

A possibly wrong test case for the std solution: http://paste.ubuntu.com/6399141/

Read more »

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

By sillycross, 8 years ago, In English,

I think I found a bug about hacking. I did 2 successful hacks during Codeforces Round #115, but after contest it showed there's only one hack. The other one is 'ignored'. But I think it should be a successful hack.

My hack:

38336 Apr 14, 2012 1:25:35 PM sillycross Skyly A — Robot Bicorn Attack Ignored

The victim's submission history:

00:13:50 Accepted [pretests] → 1532327

01:39:54 Accepted [final tests] → 1535677

And submission 1532327's status

By Skyly, contest: Codeforces Round #115, problem: (A) Robot Bicorn Attack, Hacked, #

Obviously the submission done in 00:13:50 was hacked by me ( I'm the only one who hacked this solution ) . But the hack was ignored.

I think it was caused by my another hack using the same input.

38343 Apr 14, 2012 1:30:08 PM sillycross helThazar A — Robot Bicorn Attack Successful hacking attempt

I knew that the codeforces judge would ignore same hacking inputs and only keep the last one. But it was obviously that hacking attempts of same inputs shouldn't be ignored when they were used for different victims. I think it should be a bug. This bug can be serious because when we found a very strong test data it's quite usual to use it to hack different victims. I hope this bug can be renovated soon.

Read more »

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