ajecc's blog

By ajecc, history, 3 years ago, In English

Can somebody explain how we can find the intersection of 2 line segments using only integer arithmetic (like this solution to a problem in a recent round 42626026)? I know how we can test if they intersect (with cross product), but I can't figure out how to find the exact point.

Read more »

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

By ajecc, history, 4 years ago, In English

Can someone help me with the following problem? : a farmer ties his goat outside of a building's fence, on the border of the fence. The whole area is filled with grass that the goat can eat. The fence is a convex polygon. Knowing the coordinates of the place the place the goat was tied to the fence, the length of the rope the goat is tied with and the coordinates of the polygon's vertices, calculate the surface of the place the goat can eat grass on, rounded to the nearest integer. (Number of vertices < 100 and they are given in anticlockwise order, coordinates in module < 10000, the coordinates are integers).

Read more »

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

By ajecc, history, 4 years ago, In English

You are given a graph and a number k. Output the biggest set of nodes such as every node has at least k adjacent nodes that are also in the set. (The solution should have a better complexity than O(n^2), n = number of nodes) Thanks!

Read more »

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

By ajecc, history, 4 years ago, In English

Hello! I was working on this problem: 126B - Password. I couldn't come up with a solution so I checked other people's sources. I came across this one that uses hashing: 847891. My question is: how does that solution work, when most values of the arrays p and hash are overflown? I don't see any %MOD operation, which makes this strange to me, as I am not very experimented with hashing.

Read more »

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

By ajecc, history, 4 years ago, In English

Ok, so I solved this problem: http://codeforces.com/contest/91/problem/A. The interesting thing is that I submitted 2 buggy solutions before: 27178776 and 27178719. They are exactly the same, but one is compiled on C++11 and the other on C++14. My question is: why is there a difference? Does it have to do with the way C++11 and C++14 handles the way a vector works when you access the vector.size()th element (which doesn't exist)?

Read more »

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