determinism's blog

By determinism, history, 8 years ago,

I am looking for CNOI (Chinese National Olympiad in Informatics) problems with creative, elegant solutions. I would be very glad if you could give me some suggestions.

By the way, is it possible to find editorials to these problems on the internet?

• +43

 » 8 years ago, # | ← Rev. 2 →   +57
•  » » 8 years ago, # ^ | ← Rev. 2 →   +5 Thank you very much.
•  » » » 8 years ago, # ^ |   0 "Thank you REALLY much." I didn't even find it on Google but my English is suck anyway so I'm not sure it's wrong :P
•  » » » » 8 years ago, # ^ |   +5 Everybody makes mistakes :P
 » 8 years ago, # |   0 Does anyone know how to solve this: http://wcipeg.com/problem/noi08p3 ?My linear programming solution passes but I don't think it's the "correct" solution...
•  » » 8 years ago, # ^ |   +5 In fact it is a network flow problem, so linear programming is also correct.
•  » » » 8 years ago, # ^ |   +5 Can you explain what the network is? I can't think of anything that doesn't allow you to hire half a worker, which can't be right...
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +5 Write down all the inequalities for each day, like: type1 + type2 + ... >= Ai. Add a free variable to each of them: type1 + type2 + ... - Bi = Ai. Now subtract all consecutive equations, each variable will occur exactly twice. Add an edge to network for each of them. Add an edge from the source to each positive equation, and an edge from each negative equation to the target.Here's my code: void MAIN(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d", a+i); int s = N - 1, t = N - 2; for(int i = 1; i <= n + 1; i ++){ if(a[i]-a[i-1] < 0) mfmc.add_edge(s, i, a[i-1]-a[i], 0); else mfmc.add_edge(i, t, a[i] - a[i-1], 0); } for(int i = 1; i <= n; i ++){ mfmc.add_edge(i, i+1, 1<<30, 0); } while(m --){ int l, r, c; scanf("%d%d%d", &l, &r, &c); mfmc.add_edge(r+1, l, 1<<30, c); } cout << mfmc.mincost(s, t) << endl; } 
•  » » » » » 8 years ago, # ^ |   +10 This is beautiful :) Thanks!
•  » » » » » 8 years ago, # ^ |   +5 Can u plz explain how this actually works? I mean how are the constraints in LP converted into edge capacities.
 » 8 years ago, # |   0 You can find almost all of the NOI problems here: http://www.lydsy.com/JudgeOnline/problemset.php?search=[noi Certainly,those are in Chinese.