Yesterday is a great day.., i coded my thesis quickly and realize that i have a time to solve problems at night 
. Of course, i won’t let it go away. Well, i think i become addicted to Codeforces now, since there are good quality problems with various difficulty. So, i went there, at this past contest! Here is me at standing page :
Standings
Problem A :
It is a nice problem (i think). Given W, the weight of watermelon bought by the boys, we have to determine whether the watermelon can be divided into 2 parts with each of them having even number of kilos, or not. At first, brute force came up in my mind, but then i found a really nice solution for this problem. The first observation is, assume the watermelon with weight w can be divided into 2 parts, so, w = 2x + 2y = 2(x + y), because each part must have even value. From the first observation, we can see that if w can be divided into 2 parts, then w must be even value. Then, it’s easy to see that 2x + 2y must be >= 4, because the lowest positive even number is 2, so 2 + 2 = 4. Here is my implementation :
#include <cstdio>
using namespace std;
int n;
int main()
{
while(scanf("%d", &n) != EOF)
printf(n % 2 == 0 && n > 2 ? "YES\n" : "NO\n");
return 0;
}
Problem B :
There are several approaches to solve this problem, but i used to solve this problem with Dynamic Programming, since i can’t proof other approaches like Greedy, etc. Post on comment if you have any questions about my DP.. . So, without doubt, here is my implementation for this problem :
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int d, sumTime, path[30];
bool dp[30][241], vis[30][241];
pair<int, int> tme[30];
bool doit(int pos, int t)
{
if(pos == d)
{
if(t == 0)
return true;
else
return false;
}
bool &ret = dp[pos][t];
if(!vis[pos][t])
{
vis[pos][t] = true;
ret = false;
for(int i = tme[pos].first; i <= tme[pos].second; ++i)
{
bool check = false;
if(t >= i)
check = doit(pos + 1, t - i);
if(check)
path[pos] = i;
ret |= check;
}
}
return ret;
}
int main()
{
while(scanf("%d %d", &d, &sumTime) != EOF)
{
memset(vis, false, sizeof(vis));
for(int i = 0; i < d; ++i)
scanf("%d %d", &tme[i].first, &tme[i].second);
for(int i = tme[0].first; i <= tme[0].second; ++i)
{
bool check = false;
if(sumTime >= i)
check = doit(1, sumTime - i);
if(check)
path[0] = i;
}
if(path[0] >= tme[0].first && path[0] <= tme[0].second)
{
printf("YES\n%d", path[0]);
for(int i = 1; i < d; ++i)
printf(" %d", path[i]);
}
else
printf("NO");
printf("\n");
}
return 0;
}
Problem C :
From the first time i read the problem statement, i know it can be solved with map. I implemented it quickly and got AC at first time submit. Here is my implementation :
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;
int n;
string s;
map<string, int> mp;
int main()
{
while(scanf("%d", &n) != EOF)
{
mp.clear();
getline(cin, s);
for(int i = 0; i < n; ++i)
{
getline(cin, s);
if(!mp[s])
{
++mp[s];
printf("OK\n");
}
else
{
printf("%s%d\n", s.c_str(), mp[s]);
++mp[s];
}
}
}
return 0;
}
Problem D :
I think this is the hardest problem compared to the other problems. At this problem i have to find the answer for maximum chain and i have to print the “path” of the answer. I just thought a simple way, because this problem is similar to Longest Increasing Subsequence problem. Printing path was quite easy job here. I got WA 2 times because i tried to proof Greedy solution for this problem. At first i was sure that my Greedy was true, but after submitting the solution, i got WA and i can’t found the couter example to disprove my solution. So, i turned out to think about DP to solve this problem. Here is my implementation :
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct env
{
int w, h, id;
bool operator < (const env &e) const
{
if(w < e.w || w == e.w && h < e.h)
return true;
return false;
}
};
int n, w, h, dp[5000], path[5000];
env e[5000];
int main()
{
while(scanf("%d %d %d", &n, &w, &h) != EOF)
{
int cnt = 0;
for(int i = 0; i < n; ++i)
{
env tem;
scanf("%d %d", &tem.w, &tem.h);
if(tem.w > w && tem.h > h)
{
e[cnt].w = tem.w;
e[cnt].h = tem.h;
e[cnt].id = i + 1;
++cnt;
}
}
sort(e, e + cnt);
if(cnt > 0)
{
for(int i = 0; i < cnt; ++i)
{
dp[i] = 1;
path[i] = i;
for(int j = 0; j < i; ++j)
if(e[j].w < e[i].w && e[j].h < e[i].h && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
path[i] = j;
}
}
int res = 1, tip = 0;
for(int i = 0; i < cnt; ++i)
if(res < dp[i])
{
res = dp[i];
tip = i;
}
vector<int> resPath;
resPath.push_back(e[tip].id);
while(path[tip] != tip)
{
resPath.push_back(e[path[tip]].id);
tip = path[tip];
}
printf("%d\n%d", res, resPath[resPath.size() - 1]);
for(int i = resPath.size() - 2; i >= 0; --i)
printf(" %d", resPath[i]);
}
else
printf("0");
printf("\n");
}
return 0;
}
Feel free to ask anything here.. 
Best Regards,
Wilbert Liu
