### tmwilliamlin168's blog

By tmwilliamlin168, history, 7 months ago,

I actually don't know too much about the difficulty of the problems, so the stream will end either when I solve the first 150 problems (all problems excluding the "Additional Problems") or when I have solved problems for 12 hours.

I will try to use no prewritten templates, but maybe some Wikipedia?

The stream is planned to start at 6/14 UTC 12:00am.

Hopefully everything will go well.

• +276

By tmwilliamlin168, history, 9 months ago,

For fans of Avatar: The Last Airbender https://youtu.be/xiDEsX0_MGE

Spoiler

Note: Benq is a nice person and would never create an alt

• +174

By tmwilliamlin168, history, 3 years ago,

Hello,

I have dual citizenship (Taiwan and USA), and I currently study in an American high school located in Taiwan. I've already participated in the regional contest about 7 weeks ago and did pretty well, so I qualified for the national contest.

So now I'm practicing as much as I can for the national contest, but recently I was told that I could qualify for the training camp but not the national team for Taiwan.

I searched online for IOI rules and found this link on the IOI-2017 site: http://www.ioinformatics.org/rules/reg17.pdf. Here are some parts of it that stood out:

"A Contestant is a student who was enrolled in a school at a level not higher than secondary education, in the Country they are representing, for the majority of the period 1 September to 31 December in the year before IOI’n. Students who are studying abroad may represent the Country of their nationality."

Not only am I studying in Taiwan, I also have Taiwan citizenship, so I definitely fit this criterion.

"The main objectives to be accomplished by the IOI are:

• To discover, encourage, bring together, challenge, and give recognition to young people who are exceptionally talented in the field of informatics;

• To foster friendly international relationships among computer scientists and informatics educators;

• To bring the discipline of informatics to the attention of young people;

• To promote the organisation of informatics competitions for students at schools for secondary education;

• To encourage countries to organise a future IOI in their country."

Later, I asked for clarification about why I was ineligible, which doesn't support the objectives shown above:

"The national teams are supposed to show that Taiwanese education is superior to other education systems. If a student from a foreign school represents Taiwan in an international olympiad, then it defeats the purpose. Thus, you are ineligible to represent Taiwan in international olympiads."

1. Other countries, like USA, don't care about things like the statement above.
2. The statement above only applies if the contestants perform well. Else, they should invite someone "with a different education system" (I don't know why it matters) to take the blame for not performing well.
3. Which person at IOI would notice which school I came from?
4. Which person at IOI who even noticed which school I came from would bother to know that my school provides American education?
5. Which person at IOI who even noticed which school I came from and that my school provides American education would change their views about Taiwan?
6. Why can't they credit my results (IF they are even good) to the training that I received in the training camp in Taiwan?
7. Of course "Taiwanese education" and "American education" prepares all students for international olympiads (for example for informatics, by teaching topics like Dynamic Programming Optimizations or Heavy-Light Decomposition in school), and it's not the contestants' own hard work. Thus, the results for each country accurately reflects how successful the education system in that country is.

I don't really have that much experience or knowledge in everything mentioned above. Maybe IOI set a "loose bound" for the eligible contestants, and each country can set its own "tighter bound", so I came here to ask, what are your thoughts?

Hopefully, this can be a precedent that will be explained for all countries and contestants in the future.

• +242

By tmwilliamlin168, history, 3 years ago,

I've been thinking for one month and I still don't know how to solve this problem:

There is a park of size (A<=100)x(B<=100) (consider it as a grid), with (1, 1) as the top-left corner. There are C<=1000 trees on the park, all of which have distinct locations. You want to place as many VIP lounges on the park as possible, such that every VIP lounge is adjacent to a tree on its top, bottom, left, or right. But because of privacy issues, a VIP lounge cannot be adjacent to another VIP lounge (including diagonally). Note that you cannot place a VIP lounge on a tree.

For example, consider the following park of size 9x7:

The "T"s represent the trees, the grey shaded areas represent possible locations for VIP lounges. If there were to be a VIP lounge on where the "V" is located, then the "x"s represent the locations where there cannot be VIP lounges.

Time limit: 1s

Samples

Sample 1:

Input:
T__
___
_T_

Output:
3

TV_
___
VTV


Sample 2:

Input:
______
_T____
__T___
____T_
______

Output:
5

______
VTV___
__T_V_
__V_T_
____V_


My thoughts:

Finding the maximum independent set of a bipartite graph can be done in polynomial time. Create a graph in which the possible VIP lounge placements are nodes and there are edges between 2 nodes if the 2 VIP lounges are adjacent. The maximum independent set of this graph is the answer. Notice that this graph is quadripartite (all combinations of x, y mod 2). Maybe there is also a way to find the maximum independent set of a quadripartite graph efficiently.

Or maybe I'm thinking too much and there is a greedy solution.