## Sunday, 30 May 2010

### SIMC report (1): challenge

http://www.highsch.nus.edu.sg/SIMC2010/Challenge%20Question%20pdf.htm
Firstly I would like to talk about this problem first since this will be the main propose for us to go to Singapore~
1)Basic analysis and definition
We now simplify the expressions: for X----O with length L, the market share of Coffee Bean (O) will be L/2. Sum of every line segment between two closest Starbucks shop/Cofee Bean shop will be the total share of the whole map.
2)strategy and algorithm
What is the difference of strategy and algorithm? In this problem it's just the same, but dirrerent in score. We have outlined a several strategy (not absolute rule), but we can't obtain enough score here. The main reason will be the difference in complexity and the ensurance of optimal solution.
i)Disperse without overlapping
Proof: Consider X--O1-----O2, XO1= k units, XO2=L units, then market share will be L-k/2 units.
Therefore as O1O2 disperse (L-k increases), our market share increases.
Proof by a 4-junction road. Consider a CB shop near to a cross junction while it market share to the three road will be a,b,c units respectively. If CB shop is 1 units near to the 4 junction road, the market to each road increases 0.5 each which is benificial to CB shop.
iii)Blocking Starbucks shop
Proof: consider the model in (i) again: minimize k to 1 (k≠0, k is non-negative integer), we maximize l(x)=L-k/2.
That's our work to find out the optimal solution.
Greedy algorithm
Marginal influence of a lattice is defined as the increase in market share when a new shop is added there.
Method I: Put the shops in the highest marginal influence.
Method II: Put one shop in the optimal place, re-calculate the marginal influence and to place again.
Obviously Method II is better since optimal three ≠ best combination.
However, we can't show that method II is optimal since it still just a combination of optimal shops, but not an optimal combination.
"I know your method helps to find a better solution. But how can you find such a solution. I mean, is it a modified trial and error?"
Modified trial and error is not avoidable at all. Even a full trial and error will be acceptable. We will that according to our strategy, a few choices will be left as so that we can try all of them.
"How can you determine the optimal solution among them?"
this one is stupid, just by trial and error and comparason.
"Blocking Starbucks is unfeasible. They still have another way to control their markey share. What's the main effect of this strategy?"
First we define "weak" and "strong" of a control of a shop on a particular street. It will be relative concept that is proportional to the distance to the closest shop. Placing a new shop in a "weaker" segments will have a higher market influence.
If we block them is the same direction, the opposite-blocked direction will be "far" from Starbucks so that Even the CB shop is controlling some area somehow "weak",  Then a large piece of area will be in the contrl of CB.
We don't have much to discuss with the solution of (1b), it's just a direct application of our strategy.
4 junction road + blocking the SB on the LHS. The second one located just below the bottom-right SB.
Hmmm, about the City Hall map it's a true hard one. The map is complex and there're far too much combination for us to call it "we 'have fully tried all"....
Let's finish the report for Question 1 here.