baukaman's blog

By baukaman, 11 years ago, In English

Hardly worked on the following problem(statement in russian, registration is required) but without any success, help plz:

On positive axis (x>0,y>0) Given N blue triangles and M red points. Triangles have one property: they share common vertex at [0,0].

For each triangle we must determine is there at least on red point inside it.

Constraints:
- coordinates are integers between (0,10^9]
- N<=10^5
- M<=10^5
- TL = 2sec

I understand some sort of optimization needed : sweep line or segment tree, but I couldn't figure it out

Do you know how to solve or link to the similiar problems. I would really appreciate.

Thanks in advance.

Full text and comments »

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

By baukaman, 11 years ago, In English

Hello Codeforces community!

I would like to raise a question about masters degree. Do we really need it? Some people claim that we need it only if we're planning to be a teacher at universities or to continue the science path.

For me it is choise between time and diploma[which I don't know will it be of some use in any way]. If I'm going to apply I will contribute 6pm-10pm time every working day , 9 am-3pm on Saturdays, during 1 year, but with diploma in the end. [+ participation to ACM, but I doubt it, since I'm noob]

On the other hand, I may benefit more on my own studying\contesting\projecting\resting etc.

Who of us graduated masters degree, please share your experience. Is it worth of appllying or not. Short period is left and I'm about to make my decision. Need your help\advice.

Thanks in advance!

Full text and comments »

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

By baukaman, 11 years ago, In English

This problem is a very beautiful one. Thanks to kattis we can solve it. Direct link to the problem. The problem statement is easy.

I got WA on test 2. My approach is: take number(initially equal to 1) multply it to current prime or next prime. (which we keep track of). Number of this operations is bounded. (~ 3000000 possibilities). And we can apply some greedy. In doing above we ensure that previous primes count is not less than current. So in factorization we will have more 2's than 3, more 3's than 5 etc.

Once we have some combinations of primes we use formula: S! / (s1! * s2! *s3! *...*sk! ) for example number of different permutationos of number 2*2*2*3*3 is 5!/(3!*2!).

finally, answer. We are given 1000 numbers to handle. We just memorise it in some set and try to find the answers.

Please help me out from this situation or describe your approach.My code can be found here.

Big Thanks in advance.

Full text and comments »

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