dalex's blog

Gym contest — Samara SAU Qualification Contest for ACM ICPC 2015-2016
By dalex, 9 years ago, translation, In English

Hi all!

On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.

The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.

And here is the full list of our previous contests:

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

Comments Comments (25)
| Write comment?
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

ummmm..... gym contest :D

tnx dalex :D

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Reminder: the contest starts in 10 minutes.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you write solutions on C++ it regularly happens than input reading through std::cin appears to be slow because of the large input size. Certainly is more correct in such cases to write data reading more effectively — at least using scanf. But if the testing system uses GNU C++ (checked on MinGW 4.4.1, but I think it works on other versions too), and you don't want to rewrite input reading, it is possible to improve performance by only one line placed in the beginning of the program: ios_base::sync_with_stdio(0).

On my example where it was required to find the sum of one million integers, it has accelerated the program in 4.5 times. Tried to do the same test on MS Visual C ++ 9.0 — but it hasn't accelerated the reading.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A and H?

In H, my team were thinking of drawing all lines connecting points P1, P2 and origin. Then, the original circle is divided into 6 arcs and then applying ternary search on each arc about where the new circle should touch the arc. For evaluating maximum radius if new circle is touching at certain point on the arc, we can apply binary search on the radius of new circle.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    H: Show that the largest circle always touches the boundary of the garden. Binary search the radius. Now for a fixed radius r we know that the answer lies on the circumference of the circle with center (0, 0) and radius R - r, where R is the radius of the garden.

    So we are only interested in the polar angle of the answer. Notice that if this angle is atan2(y1, x1) + PI, we get the most distant point from (x1, y1) we can get. Find such delta that angles from atan2(y1, x1) + PI - delta to atan2(y1, x1) + PI + delta are distant enough from (x1, y1), and the rest of the angles are not. You can do it with another binary search or with acos, but don't forget that sometimes the whole circle is good and delta = PI, and sometimes even atan2(y1, x1) + PI is not good enough.

    Now we have two ranges of angles. Those that are good for (x1, y1) and those that are good for (x2, y2). If the ranges have at least one common angle, this radius is good, else it isn't.

    A: For each guy, calculate how much he owes minus how much he is owed. For some guys the number will be positive, for some guys negative. The sum is, of course, zero. Greedily connect the positive guys with the negative ones.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I finally upsolved H, and it turned out to be very easy. Solution above is written on drugs, so this is the normal solution.

    Solution of H

    I'm surprised many high rated people couldn't solve it. People should learn that "geometry" doesn't mean "hard".

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to G?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how To solve problem K?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem B? Thanks you :D

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use map to keep how many times each pattern appears.

    Make sure you ignore the judge who includes more than 15 or less than 8 tasks

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J and L ?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I solve problem C, please?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Solution of C
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve A?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to slove B and L ?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    The problem L can be solved using extended euclidean. You will divide it into 3 cases.

    1. $$$n*x = m*y$$$ -> answer is $$$LCM(n, m)$$$

    2. $$$n*x + 1 = m*y$$$ -> solve: $$$m*y - n*x = 1$$$

    3. $$$n*x = m*y + 1$$$ -> solve: $$$n*x - m*y = 1$$$

    You need to treat individually when $$$n = 1$$$ or $$$m = 1$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem L solution

→ Reply