Topcoder SRM 734 is scheduled to start at 21:00 UTC -4, May 16, 2018.

Featured Problem Writer: Vasyl[alphacom] [Profile](http://www.topcoder.com/members/Vasyl[alphacom])

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Don’t know how to compete in Topcoder SRMs?

Topcoder Java Applet — You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide)

Hope to see most of you competing! All the best!

The writer is Vasyl[alphacom]? That's good, I'm really waiting for interesting tasks!

By the way, the time in this blog and in the timeanddate link is different, isn't it?

Updated! :)

Video solution to Div II P1 — TheRoundCityDiv2: https://youtu.be/RzobVOY4Qb8

Video solution to Div II P2 — TheSquareCityDiv2: https://youtu.be/zwYi5y8GJu4

How to solve Div 1 300?

WLOG we can just consider

x,y> 0. A coordinate (x,y) is visible if and onlyxandyare relatively prime. So for eachxcoordinate, we want to compute the number ofys that are relatively prime toxin the range .We can use inclusion-exclusion to count everything that shares at least one factor with

xand subtract these from the range. First we count all multiples ofpwherepis some prime factor ofx. But this double-counts multiples ofpq, so we subtract all multiples ofpq. And then we add back multiples ofpqs, and subtract multiples ofpqst, and so on. So the total runtime is aroundWhere ω(

x) is the number of distinct prime factors ofx. One piece of number-theoretic intuition is that ω(x) grows extremely slowly (max_{x ≤ 1000000}{ω(x)} = 7), and most elements in the range only have ≤ 3 distinct prime factors. So this is fast enough in practice. (You can just run the maximal case to make sure.)The Div2 contest was not good. It didn't have unique problems.

250 — google search "lattice points within a circle"

500 — brute force(low constraints)

1000 — standard dfs/dp travel in a grid with some conditions

I saw these Div2 problems, and I thought it's okay. Here's my feedback:

250 — Div2 250 should be (usually) easier than CF Div2 A. Therefore, if they want to publish the simple problem, it's inevitable. And the importance in Div2 250 is to implement a program. No reason to complain.

500 — I think its difficulty fits Div2 500. Although there is no "innovative" idea in this problem, it's Div2 and not hardest therefore it's okay. (One example of "innovative idea" in Div2 Medium is, SRM 726 Div2 Medium — TurtleGame, but the ratio of correct submission by participants were desperately low.)

1000 — It's standard for red coders, but it's not standard for Div2 peoples. So you should go to Div1.

1) 250 is not easier than Div2A but okay, its hard to make very easy problems :P

2) I didn't say problem was easy but just like you said it was not innovative.

3) I thought travel inside grid is standard/common. These types of problems even have tutorials like third problem here and here. We just take some additional parameters in dfs to check for the conditions. That's all. About the Div1 thing, I hope this could happen.

Yes, so your issue about Div2 250 and Div2 500 is solved :) Now we should talk about Div2 1000.

Seeing rate of accepted people by number of participants, it is definitely "easy Div2 Hard" but not too easy. It's kind of a variation of "classic" problems, but I think it is normal in computer science world because most problems are continuance (or steps) of classic thinking. But hoping to see next SRM Div2 Hard to be interesting :)

By the way, in similar (?) topic, I wrote a topcoder forum article about division cutoff and problem difficulty placement. I want all of your opinion. Please reply in this forum if you can :)

Can someone explain the Div1 Medium (CardCounter) solution please?