vdmedragon's blog

By vdmedragon, history, 3 years ago,

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.

• +8

By vdmedragon, 14 years ago,
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).

Easier 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

• +2

By vdmedragon, 14 years ago,

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

• +2

By vdmedragon, 14 years ago,
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
• 0

By vdmedragon, 14 years ago,

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.
• 0