Newtech66's blog

By Newtech66, history, 13 months ago, In English

Basically the title of the post. Well, I suppose "solution->problem" is a way, but I'm not particularly good at using it. "problem->solution" is the way I prefer, but the issue is, oftentimes, I'm not skilled enough to solve the problem I just made. Nor can I tell if the problem is unsolvable (in polynomial time). How do you do it?

Read more »

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

By Newtech66, history, 18 months ago, In English

In newer problems on CodeForces and other sites, I usually see multi-test inputs that say something like "it is guaranteed that sum of $$$n$$$ over all testcases does not exceed XXXXX".

I am unable to figure out how to implement such a generator in Polygon. Can someone tell me how exactly I should go about this?

Read more »

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

By Newtech66, history, 20 months ago, In English

The problem:

Assume there are $$$n$$$ circles on the plane. The $$$i^{th}$$$ circle has an initial radius $$$r_i$$$ $$$(r_i \geq 0)$$$. We are allowed to increase or decrease the radius of the $$$i^{th}$$$ circle by $$$1$$$ unit at a cost $$$c_i$$$ $$$(c_i > 0)$$$. Let us make a graph such that each circle is a node, and there is an undirected edge between two circles $$$C_i$$$ and $$$C_j$$$ if their intersection is not empty (just to be clear, the cases are: they touch internally/externally, they intersect at two points, one lies inside the other).

Find the minimum cost to make the graph connected.

Source:

Trying to think of new and interesting problems and then creating this problem which I can't solve at all. The inspiration here was from radio stations. Every radio station has a coverage radius, and if we make the network connected, a message can travel between any two radio stations.

I have given up on this problem. I would appreciate it if someone can enlighten me on how to solve this problem or with any restrictions on it (eg. "$$$r_i=0$$$", "All $$$c_i$$$ are equal", etc).

Time complexity required:

Anything works, I haven't even been able to figure out an approach.

Read more »

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

By Newtech66, history, 2 years ago, In English

The problems:

Magic Portals

Surprise Birthday

Roaming

My thoughts:

Magic Portals
Surprise Birthday
Roaming

Please help me in getting a solution to each of these problems.

Note: Contest ended a long time ago so don't worry about possible cheating.

Read more »

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

By Newtech66, 3 years ago, In English

>bumping this post for first and last time because I never got an answer

There is an intruder in your system who wishes to steal as much information as he can. Your system can be represented as an undirected graph, with each node having an information value (IV). Now, you were terribly unprepared for this. Your only option is to delete nodes. You have time enough to delete at most 2 nodes. Luckily, the algorithm of the intruder has a flaw. It cannot visit a previously visited node. It steals the information of whatever node it visits. Assuming that the algorithm always tries to maximize the IV it can get, give the maximum possible IV you can save.

Note: Formally the algorithm seeks the path of maximum weight. The sum of the weights of the unvisited nodes is what you have saved. The weights of the deleted nodes are unavailable to both you and the algorithm. When a node is deleted, all paths connected to it are also removed.

A variant: Now you are given that the algorithm starts the path with a given vertex that you cannot delete.

There are no constraints, I want the best solution. Please notify any corrections or flaws in the problem statement. It is guaranteed that the constraints allow a solution.

Read more »

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