AFN's blog

By AFN, history, 4 years ago, In English

Hi everyone!

I'm really facing problems in when to use modular inverse. I know that you should use it when calculating the following

(a / b)%p = (a * bp - 2)%p [Only when p is prime]

I know there is a case when subtracting, but I don't know how you do it exactly, can you tell me how? And are there any other cases?

Thanks in advance.

Read more »

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

By AFN, history, 4 years ago, In English

Hello Codeforces community.

It's been a long time since I last solved a problem on CF, so I decided I'd solve some Div. 2 As and Bs before I start solving Cs.

Anyway, I was solving problem 29B - Traffic Lights, that's when I saw WA on test 12 after submitting it. What's weird isn't the WA in particular, it's the reason; "Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\b00a58c7139058a693e243e272a449d7\check-aa5f5d80dec38086488721f39ffc5878\run\output.fd0138e687.txt.".

For more information look at my submission below

27794085

As CF doesn't let you send the same code twice, I just added a small comment in my code and re-sent it. Surprise, AC.

You can find my submission with the same code but with an added comment below

27794123

Isn't this considered a fatal problem? Or is it just because it is an old problem so there are issues?

Imagine having a wrong answer verdict like this in a rated contest!

Read more »

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

By AFN, history, 4 years ago, In English

To all those who participated in round 405:

Have you noticed that your rating hasn't changed in your handle but had changed on rating changes and your graph?

For example, my rating has become 1593 after the last contest but is still shown 1621.

Is everyone experiencing this problem?

Read more »

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

By AFN, history, 5 years ago, In English

Hey guys I wanted to share with you something I discovered.

I was checking contests I took part in last year and stumbled into round 308 Div2. Problem D: This

This problem could be solved by simple O(n^3) by just picking all triplets and see if they make a triangle.

Well last year I calculated m1 = (y[k] — y[j]) / (x[k] — x[j]) and calculated m2 = (y[j] — y[i]) / (x[j] — x[i]) as doubles and if (m1 == m2) then it's triangle.

Looking at the constraints n <= 2000 so this answer should pass in the problem's time limit which is 4 seconds. But I got TLE.

This year while checking my previous solution, I decided to just convert the equation like this:

=> m1 = m2

=> (y[k] — y[j]) / (x[k] — x[j]) = (y[j] — y[i]) / (x[j] — x[i])

=> (y[k] — y[j]) * (x[j] — x[i]) = (y[j] — y[i]) * (x[k] — x[j])

So now both l1 and l2 could be calculated as integers, I did this and AC. Wow.

Seems like double division in C++ takes time, while multiplication as integers is faster, that's why I got AC.

Previous (TLE) Submission: Submission 18887929

Current (AC) Submission: Submission 18887986

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

By AFN, history, 5 years ago, In English

Hi Codeforces community. I recently learned the trie algorithm and I'm trying to solve DICT problem form SPOJ. http://www.spoj.com/problems/DICT/ I'm getting WA for an unknown reason. Here is a link to my code. http://ideone.com/FxUaVp Any help appreciated.

Read more »

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