vdmedragon's blog

By vdmedragon, history, 16 months ago, In English

Admin, I got this issue while submitting code to the problem 234C:

`Participant's output`
`Jury's answer`
`Checker comment`
`Can't find file K:\ramdisk\codeforces61\c53dd23c96013b2e9c8583ab8f05edda\check-d10a4d6b1acf8dcc90e929292a422e5f\run\output.txt [invokerId=9b4df16fc0ab37520967f1d97d3e17aa, location=203279210] (1).`

https://codeforces.com/contest/234/submission/112246561

For other problems, it is ok.

Please help to resolve this issue.

Read more »

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

By vdmedragon, 12 years ago, In English
Condition to verify if a point C in a segment [A,B]

(C.x-A.x)*(A.y-B.y)=(C.y-A.y)*(A.x-B.x) (1)

min(A.x,B.x) <= C.x <= max(A.x,B.x) (2)
min(A.y,B.y) <= C.y <= max(A.y,B.y) (3)

I forget to check (2),(3); only remember 1. (AC if i remember)

vihrov: Another way: if we have a segment AB and a point C, then C is in AB iff AC + CB = AB.

Condition to check angle (AB,AC) <= 90.
- Using AB*AB+AC*AC>BC*BC
- Using atan2 : it may lead to error of precision (I found it during contest).

dAFTc0d3rEasier way to check sign of cos

( AB, BC ) = | AB | * | BC | * cos( angleABC )

| AB | * | BC |  > 0 

So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y




Read more »

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

By vdmedragon, 12 years ago, In English


Mathematic formulation for E ( instead of guessing patterns and coding from scratch )

Read more »

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

By vdmedragon, 12 years ago, In English
1. Easy but need to careful.

2. One can easily stuck with the question the algorithm O(N*K*K*K) is TLE, so i think about bruto-force solution & some tricks to reduce a factor K: filling the table and using accumulative sum, it helps reduce the complexity to O(N*K*K) and AC.

3. Ok, they require to calculate the number of (A,B,C) with 1<=A,B,C<=N && A!=B*C && d(A)=d(d(B)*d(C)).

so for each number A from 1 to N, i calculate the number of pairs (B,C) which d(d(B)*d(C))=d(A); and minus the number of divisors of A.

However, wrong initialization leads to WA. It needs to correct one line of the code.  After correct it, it passes in 80mss.

But a bruto-force to calculate the numbers of divisor of a number x  (go from 1 to y=sqrt(x)) can leads to TLE? I check with N=1000000 and it runs about 2,3s or more in my computer (dual core T2300). SO i use "multiplicative property" to calculate these numbers but it is needed or not?
 
4,5. Have not read the statements because it must be harder than C.

Solution for E: http://graal.ens-lyon.fr/~yrobert/algo/coins2.ps

Read more »

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

By vdmedragon, 12 years ago, In English

Current rating: 1524.

1. You must be carefully, typically I rare create "test cases", just write and submit the source code (I have a lot of WAs in some judge online). This time A,B are passed with 1 submission. It makes me feel comfortable.

2. You need to wait the judge evaluate your submission.  I submitted C problem, I saw green (Accepted - 0s) and I changed to problem D, but late, i checked the standing board I saw (-1), so I need to verify my code (it showed 30ms). One experience.

3. Problem D, I think it is easier to think about  recursive DP than iterative DP and coding recursive DP is also easy too.

Two stuffs which can help you solve this problem:

4. Problem E, time out because of D.

Read more »

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