IOI Training #3

Is there anyone who wants to tell their ideas?

Let me start it:
Problem 1:
Honestly, I have found the formula but I don't understand it, so I skip it.
If you got the formula for Q(n)..
where Q(n)= number of square-free<=n..

You can do binary search to get the answer.

Problem 2:
It is quite hard to implement. Find the outer cycles, then eliminate it find again some outer cycles in previous cycle. Subtract the related outer area with cycled found inside it.. do till no cycles =_="

Problem 3:
It's BIT(Binary Indexed Tree).
You can start learning BIT by solving MATSUM and z-green..

My algorithm is as follow:
my index:1- based(start from 1)

1. sort by name
2. for i=1..n
tmp=query to find numbers of names<name-i(after sorted) and in front of name-i (before sorted).
save tmp to variable a[position of string n before sorted]
update the ith sorted names.

3. print a from 1..n

Thanks to friends who post their ideas.

for task 2, Is there some trouble with statements or tests? I can't believe my solution don't pass any tests, and no one! Can anybody explain me?

can I know ur idea?

Problem 1:
100% same problem was on topcoder , and here is the explanation how to solve it:
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm190

any hints for task 3?

BIT

I haven't tested any of these so use with caution :)

Problem 2:
First get rid of nodes with degree 1 together with the only edge that is connected to them.
Now you have to start peeling off cycles. Start with most horizontal fence going out of the lowest tree. Follow the trees and at every tree choose the fence which forms smallest angle with previous fence in clockwise(negative) direction.
When you make a cycle you can compute the area: http://en.wikipedia.org/wiki/Polygon_area#Area_and_centroid
Remove starting edge and any other unnecessary edges or new trees with degree 1 and repeat.

Problem 3:
Why do you need BIT here?
Inserting names one by one into some balancing binary tree (for example AVL) should work. All you have to do is maintain sizes of subtrees for each node in the tree.