2015.7.3 ~ 2015.7.23 problem solving

This is my problem solving log during my IOI training camp.

It will not cover all of my camp problem, I will just list some interesting ones.

Since I'm lazy enough to install Korean IME in Ubuntu, this log will be written in English. 

Day 1

Game Strategy (WF 2014)

https://www.acmicpc.net/problem/10053

think backward.

Buffed Buffet (WF 2014)

https://www.acmicpc.net/problem/10051

Didn't have enough time to read the statements, will solve it later.

Surveliance (WF 2014)

https://www.acmicpc.net/problem/10060

Use sparse table, beware corner cases. Didn't coded yet.

Metal Processing Plant (WF 2014)

https://www.acmicpc.net/problem/10056

I was close to the solution, but failed to get AC in virtual contest.

wlog D(A) <= D(B), when D(A) and D(B) is fixed, we can figure out such configuration is possible using 2SAT. It's time complexity is O(N^2).

when D(B) is fixed, we can use binary search for D(A), It makes O(N^2lgN) query for 2SAT. total complexity is O(N^4lgN) which gets TLE.

to get model O(N^3lgN) complexity, observe that D(A) only have O(N) important states. this is because, edge with more than D(A) costs can't be in same set. those problems are easily solved with disjoint set, and we can prove that disjoint set will not union more than O(N) times (with simillar mechanism of MST). if disjoint set is same, results for D(B) will also be same.

Day 2

Critical 3-Path (Daejeon 2012)

https://www.acmicpc.net/problem/8890

simple O(N^4) algorithm, should we call it "tritonic tour"? making dummy node will make coding far easier.

Day 3

Fair Photography (US Open 2014)

https://www.acmicpc.net/problem/10030

I heard model solution is O(K^2N), but I have ABSOLUTELY no idea :(

Cow Optics (US Open 2014)

https://www.acmicpc.net/problem/10031

Transform this problem into segment intersection problem. Beware of corner cases! Segment intersection Problem can solved in O(NlgN) w/ Binary Indexed Tree. Simillar problem is in WF 2012.

Day 4

Machine Works (WF 2011)

https://www.acmicpc.net/problem/4220

O(N^2) dp is simple. To optimize use Convex Hull Trick. But since the slope is not monotonic, we should use dynamic variant.

Trapped In The Haybales (US Open 2015)

https://www.acmicpc.net/problem/10760

I couldn't solve this problem in the actual contest. (I attended US Open 15)

consider the haybale i, j. We can't jump to another haybales iff |Pi - Pj| <= Min(Hi, Hj).

So, sort the haybales and insert into std::map in decrasing height order. Only seek the haybales near the inserting haybales, and remember if they are unjumpable.

Day 5

No Change (USACO 2013.11 Gold)

https://www.acmicpc.net/problem/9569

define dp[bit] -> maximally coverable purchase number with given cost bitset. it is calculatable in O(KlgN) time using binary search. total complexity is O(2^K * KlgN)

Line of Sight (USACO 2013.11 Gold)

https://www.acmicpc.net/problem/9568

I thought the solution, but it was quite hard to code and it actually got WA. Maybe my algorithm is completely wrong, but I'm not sure.

My instructor gave very nice solution to this problem. Two cows can see each other iff two cows have common viewable segment in the silo. using atan / acos / asin we can calculate viewable segment in radians. now calculating intersecting number is easy.

Vacation Planning (USACO 2013.12 Gold)

https://www.acmicpc.net/problem/9866

int dist[30][105]; void fill(int* t){memset(dist,0x3f,sizeof(dist));} fill(dist[0]);

this fills the whole dist array into 0x3f! I got many WA due to this :(

Optimal Milking (USACO 2013.12 Gold)

https://www.acmicpc.net/problem/9867

Reminds the dynamic variant of Maximum contiguous sum with segment trees. This problem can be solved with simillar mechanism. Very interesting.

The Bessie Shuffle (USACO 2013.12 Gold)

https://www.acmicpc.net/problem/9868

Think backward. Using sparse table yields O((M+Q)lgN) sln. can be solved in linear time (just like ioi11 garden), but sparse table solution is more elegant.

Day 6

I solved CEOI 2015. Can't remember exact problem name.

Problem 3 : We can separate edges to tree edge and non tree edges, observe that only O(N) non-tree edges are important. thus saving only 2N-2 edges are enough. After all I used LCA to print bridges, but it is useless because linear time bridge finding just works :)

Problem 2 : simple O(N^2) dp simillar to IOI08 linear garden. use toggling.

Problem 1 : After a long time I found the relation between "shortest paths and potemkin cycle" - which yields O(M^2) algorithm. I failed to come up with more faster solution.

Day 7

Ski Course Design (USACO 2014.01 Gold)

https://www.acmicpc.net/problem/9877

disjoint set variant. BOI 2012 peaks?

Day 8

All problems are from JAG.

Cube Coloring

https://www.acmicpc.net/problem/10624

thinking about convolutions make things easier.

Revenge of Minimum Cost Flow

https://www.acmicpc.net/problem/10639

The cost functions are convex. so picking only one shortest path just works. but sadly one cost function are concave, so beware the cases. I couldn't come up with any observation in the virtual contests, and I was very impressed with those solutions!

The J-th Number

https://www.acmicpc.net/problem/10641

thinking about sqrt decomposition screws things up. simply think that first queries are lines at height v and [a,b]. building range tree yields O(Qlg^2N). I used range tree + binary search to get O(Qlg^3N) which passes - but optimization is not that hard. ainta used persistent segment tree. I think I should learn that :)

Day 9

Key to Knowledge

https://www.acmicpc.net/problem/10329

idk why but it's quite hard to come up with such solution. divide into half and use binary search.

GC-Ratio

https://www.acmicpc.net/problem/8925

I came up with O(NlgNlg(1/eps)) solution and used geometric tricks to get O(NlgN). Actually, using maximum contiguous sum yields O(Nlg(1/eps)) solution. I was stupid :(

Digi Comp II

https://www.acmicpc.net/problem/10521

Reminds the simillar problem from JOI. just topological sort.

Citadel Construction

https://www.acmicpc.net/problem/10321

convex hull

Triangles (CEOI 2009)

https://www.acmicpc.net/problem/3323

wtf

Day 11

Rings (IOI 2012)

http://oj.uz/problems/view/IOI12_rings

We can call a component "chain" iff

* It has no vertex with degree >= 3

* (vertex with degree 2) != (size of component)

when counting criticals ->

 * if (vertex with degree 2) == (size of component) return size of component.

 * if (veretx with degree 3 exists) erase that vertex and neighboring vertex. now find that vertices are critical

 * if(vertex with degree 4+ exists) erase that vertex and find if that vertex is critical

 * otherwise return n

this can be optimized with building 4 disjoint sets.

Saveit (IOI 2010)

http://oj.uz/problems/view/IOI10_saveit

I got absolutely no idea on that problem so I heard the solution. The solution is storing 1 BFS tree, and saving (HN) difference value - difference value is only -1, 0, 1.

Day 12

Supper (IOI 2012)

http://oj.uz/problems/view/IOI12_supper

Implementation of optimal solution will give O(NlgK) bits.

to optimize, send this information for O(N) times :

"You can delete this value after this GetRequest() call".

this value doesn't contain the value C[i]. And you can find that O(N) is not enough - you need O(N+K) calls. Still, this can get AC.

Day 13+

집에 왔는데 귀찮으니 여기서부터는 날짜 정리 안하고 푼 거 중에 기억남는거 몇개만 올림

돌아보니까 푼게 별로없네

그리고 한글 되니까 한글로 씀

Editor (BOI 2015)

https://www.acmicpc.net/problem/10779

Do Use Persistent Segtree

CEOI 2015 Day 2

Problem 1 : 개노잼

Problem 2 : 씹노잼

Problem 3 : 득점이랑 투자시간이랑 비례함

Day 1만 푸세요

KOI 2015

Prob 1,2 : 합 30분컷

Prob 3 : 위아래 나눠서 점화식 세웠고 57점은 한시간 걸렸는데 백점 풀이가 나올듯 안나올듯 하다가 여기서 시간 다날림. 심지어 난 5시간 대횐줄 알았는데 4시간이야 ㅋㅋㅋ 말리기 좋은 문제라고 생각. 그냥 점화식 생각할때 위아래 안나누면 쉽다고 함 what the fck..

Prob 4 : 이 문제 진짜 15분 정도밖에 시간 안냈었는데 10점 짜고 던짐. 풀이 들어보니까 3번 57점 내고 던졌으면 68점이 가능했을거 같은데, (코딩이 어렵다고 하는데 난 공감하지 못하겠고) 뭐 고민 안하고 풀이 들었으니 모르는 일이지. 안드로메다를 느끼고 싶으면 M^2lgM 분할 정복을 생각해보세여

총점 267로 간신히 대상 점수를 웃돔 (1점차 ㅋㅋㅋㅋㅋㅋㅋ) 대회때 이러지 말자

Rail (IOI 2014)

http://oj.uz/problems/view/IOI14_rail

56점은 어렵지 않게 냈는데 100점 풀이를 생각하면서 inchworm 비스무리한 생각으로 접근했고 결국 풀지 못했음. 정해는 그냥 location을 배열에 저장해두고 중복호출 줄이는건데 진짜 그 배열 저장 한줄에 내가 바보가 되버림

Holiday (IOI 2014)

http://oj.uz/problems/view/IOI14_holiday

단조성을 관찰하면 주어진 집합에서 가장 큰 K개의 원소를 묻는 쿼리가 O(NlgN) 번 주어지는 형태로 문제를 바꿀 수 있다. 난 Merge Sort Tree 써서 각 쿼리를 O(lg^2N)에 처리했고 O(Nlg^3N). Merge Sort Tree가 존나 빠르다는 생각을 자꾸 하게 되는게 이게 O(Nlg^2N)과 거의 비슷한 속도로 돈다. O(Nlg^2N)은 그냥 세그먼트 트리 쓰는데 또 내가 다시 한번 바보가 됐더라.

Training (IOI 2007)

http://wcipeg.com/problem/ioi0723

몇가지 관찰을 한 후 트리 DP를 이쁘게 돌리면 된다 사이클이 안 겹친다 류의 관찰인데 암튼 뭐 잘 하면 됨

Pork barrel (CERC 2014)

https://www.acmicpc.net/problem/10511

간선 정렬 후 작은 순으로 동적으로 MST를 갖고 있는다. 링크컷 같은건 별로 필요 없고 그냥 손으로 잘 하면 O(NM) 뜸. 이런 걸 갖고 있다고 칠때 어떠한 간선 T에 대해서 T'를 "가중치가 T보다는 작고 T'보다 크거나 같은 간선 집합 중, T의 양 끝 점이 연결되게 하는 가장 큰 T'] 라고 정의하면 (존나 어렵게 말하네 ㅡㅡ) 이후 들어오는 쿼리는 그냥 이러한 페어들 중 만족하는 애들의 가중치 합을 갖고 있게 하면 된다. 머지소트 트리 쓰면 이건 쿼리당 로그제곱에 되고, 머지소트 트리는 존나 짱쎄기 때문에 O(NM) 공간 복잡도의 다른 풀이들보다 훨씬 적은 memory footprint로 작동한다 머지소트 트리 짱짱맨 (성애자가 된건가..)

Parades (CERC 2014)

https://www.acmicpc.net/problem/10502

edge disjoint한 path 집합을 최대화하는 문제인데 트리 dp 짜는거 까지는 쉬운데 시간 맞추기가 영 힘들다. O(NM)보다 빠른 아이디어만 있으면 손이 많이 가기는 하는데 어렵지는 않다. 그 아이디어가 안나오면 뭐..

Outer Space Invaders (CERC 2014)

https://www.acmicpc.net/problem/10513

가중치 큰 순서대로 하고 나이브하게 하면 O(n^4)다. 크누스 같은게 되는 진 모르겠는데 아무튼 조금 이상한 걸 증명하면 그런거 없이 O(n^3)에 됨. icpc 문제는 TC 개수는 좆도 안알려주면서 시간은 쳐 빡빡하게 넣는게 항상 마음에 안들었었는데 아무튼 O(n^3)도 효율적으로 구현해야지 AC먹는다 그냥그렇다고..

장비 (Daejeon 2011)

https://www.acmicpc.net/problem/8903

재밌는 dp. 어렵진 않은듯

Codeforces Round 313

http://codeforces.com/contest/559

개.노.잼.셋.

난 웰노운 꿀빨고 68등 해서 100점 오름. 재미와 레이팅을 등가교환.

Bookcase (NWERC 2006)

https://www.acmicpc.net/problem/2000

높이인지 두께인지 순으로 정렬하고 냅색을 이쁘게 돌리면 된다. 손이 좀 많이감. dp[x][bag1][bag2][bag3] -> 높이의 변화지점이라는 식으로 잡고 냅색을 돌린다고 생각하면 이해가 될라나? 당연히 bag3은 인자에 안넣어도 됨 예상했겠지만.

괄호 (BOI 2012)

https://www.acmicpc.net/problem/3345

[] is a lie

원숭이 (KOI 2012)

https://www.acmicpc.net/problem/2516

맞았는데 왜맞았는지 모르겠어.. 모두 한 우리로 몰아넣고 안되는 애들은 bfs하면서 계속 바꿔줌. 틀릴 일은 없을거 같고 왜 한번 본 노드를 다시 보지 않는지는 잘 모르겠다 누가 증명했으니까 맞았겠지