Recently (not so recently) I was the problem setter of one SRM. When I was developing the problems I had the idea of creating the following problem:

Given N points on a cartesian plane, two players plays the following game in alternate rounds:

• The player of each round must choose two points and draw a segment of line between them as long as this segment of line doesn't intersect with any segment created before.

• The player who can not draw a segment of line anymore loses the game.

• Given that both players plays optimally, who is the winner?

This problem is almost the same as the Div2Hard from SRM624 ( http://community.topcoder.com/stat?c=problem_statement&pm=13204&rd=15857 ), but now we don't have the restriction that the points must be part of a convex polygon. I've asked lots of amazing coders (including target coders) but no one found a solution yet or proved that this problem is unsolvable in polynomial time.

The best solution I could come up with is the most naive one (O(2^N)). My question here is if it's possible to solve this problem with a better solution or even prove that it's indeed unsolvable.

Hey Guys!

I'm the SRM 624's problem setter and I'm very glad to invite you all to participate. It's my first time as a topcoder problem setter, let's hope it's not the last :D

The contest is going to take part tomorrow (maybe today, it really depends on which part of the world you're right now): http://community.topcoder.com/tc?module=MatchDetails&rd=15857

Time and Date: http://www.timeanddate.com/worldclock/fixedtime.html?&day=12&month=06&year=2014&hour=11&min=00&sec=0&p1=179

Hope you guys have fun and enjoy it.

Wish you all good luck!

P.S: Let's discuss problems after the contest!

P.S2: Tomorrow is also the World Cup Opening, so we can discuss it here either! :D

**P.S3: Editorial (incomplete): http://apps.topcoder.com/forums/?module=Thread&threadID=821638&start=0&mc=1#1888704 **

All of us heard about the tension in Russia with US and Europe, does anyknow knows if this can in anyway affect the ACM-ICPC finals this year? Is there any chance that the finals moves to another country?

Hey everyone, I'm solving one of the problems from IOI 2012 ( Ideal City ). I think I've got the whole idea, but my code seems to have some bug as it's not giving the expected output for some cases. I'm not so sure but my guess is that the bug is on the function to calculate the sum between every pair of nodes on a tree, so what I'm asking is if someone knows a specific problem where I can test my function to calculate the sum between every pair of nodes on a tree. If no one knows it, it'd be just good if someone gives me implementation for this specific problem so I can check if mine is correct or near it.

Thanks!

Does anyone knows what's the best or an acceptable algorithm to find the number of Minimum Spanning Trees in a weighted graph ? I found a paper that solves it using Kirchhoff Theorem, but I couldn't understand it.

**PS: After some tries I finally got this problem. But thanks to everyone that read it. Some hints for those who haven't solved it yet: 1 — First solve the simple version: How many spanning trees does a graph have ? 2 — Search for Kirchhoff Theorem in Wikipedia 3 — Think about what happens when we have a group of disjoint components sharing the same edge weight. **

Does anyone knows how to solve this problem ? http://cepc08.ii.uni.wroc.pl/cards.pdf

I've been trying to solve this problem, got some ideas but none of those ideas has really worked. Can anyone give me a hint ?

Hey, does anyone knows how to solve this problem ?

I'm doing some sort of Dynamic Programming on Trees, assuming that the answer when M > 2 is always the 'same'. So my DP is the follow:

• DP[ has_fruit ][ node ][ K ]: What's the minimum answer when the subtree rooted at 'node' has exactly K nodes on the first group and the 'node' K has a fruit on it or doesn't have a fruit on it.

So I go down recursively on the tree calculating it for every node from the leaves to the root. And to compute DP[ has_fruit ][ node ][ K ], I'm using another DP that is very similar to the Knapsack DP.

Well, I'm sick and tired of getting WA's, so I decided to ask if anyone of you have already solved this one. My code: http://pastie.org/private/6gl337rrzkue0cxzokda

Does anyone knows some Hard Math Problems for ICPC Training ? And if it's possible I'd like some links or some books where I can improve my Math Skills for ICPC.

Does anyone knows how to solve this problem ?

"Given a string of size N ( 1 <= N <= 3 * 10^5 ), count how many pairs of positions (i,j) exists such that there's a way to form a palindromic string rearranging the characters from position 'i' to position 'j'"

Is there any group for IOI 2013 participants ? It'd be great to meet other contestants.

**Edit: As no one answered me, and also the official IOI 2013 page at Facebook told me that there isn't a group, I've created one. Here's the link: https://www.facebook.com/groups/362768537158225/ **

Does anyone knows how to solve this problem:

Given two integers N,K ( 1 <= N,K <= 2^32 ) what's the answer for:

modulo (2^32)

edit: Sorry, I made a mistaken. The answer should be modulo 2^32, not 2^32 — 1 as I've written before.

Given four integers N,M,x,y ( 1 <= x,y,N,M <= 10^9 ), what's the minimum value of T such that:

T ≡ x mod N

T ≡ y mod M

Can somebody help me?