Codeforces Round #292 (Div. 1)

果然人一個不能兼顧太多事

增強其它方面時就荒廢coding的事了

趁還有記憶還是先寫1-2篇

這次是標題黨...因為其實我只是做了Div. 2 的C跟D,  而沒有做A跟B...

所以等於做了Div. 1的A跟B吧

(其實是Virtual Participate時按錯了...CF把Div. 2 跟Div. 1 的順序換了=.=)

這場的E,,,哦我是說Div. 1的C  我最後還是沒做到, 因為要用一個我還沒深究, 倒是發現了一個常用的技巧...等等再說一下吧

Codeforces Round #292 (Div. 1)

題目: http://codeforces.com/contest/516/problems

A: (Math, Greedy)

起初不知道選了Div. 1看了題目想了想已經覺得怎麼這場D2 的A好像難了點

才發現其實是D1的A...倒也不是真的很難, 如果只是要做到的話

但要證明就有點難...

題目是說有一個Function F(X), 是把X的每一個digit 作factorial 再相乘

例如 F(135) = 1! * 3! * 5! = 720

求最大的Y使F(Y) = F(X) , X為input

Y不能有0或者1作為digit

細心研究一下sample, 不難發現 4! = 4*3! = 2!*2!*3!....

所以一個"4" 就可以變成"322" 了

這樣想來, 每一個digit應該都可以這樣變成另一堆數字吧?

然後只要Greedily 地由大到小的排就ok了
比較中伏的是 9!,  開頭直覺地單數不能再拆了...但其實是"質數"不能再拆, 9是可以拆的

9! = 9*8*7! = 9 * 2! *2! *2! * 7! = 3 * 3 * 2! * 2! * 2! * 7!= 3! * 3! * 2! * 7!

所以"9"是能變為"7332"的

基本就這樣replace input的每一個digit就ok了

反倒是證明可以這樣拆是有點難 (以上都是直感就做了, 我想大部分人都是這樣過的吧)

看看Editorial 

We can prove the following lemma:

For any positive integer x, if it can be written as the form (2!)c2 * (3!)c3 * (5!)c5 * (7!)c7, there will be only one unique way.

Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!)a2 * (3!)a3 * (5!)a5 * (7!)a7and (2!)b2 * (3!)b3 * (5!)b5 * (7!)b7.

We find the largest i such that ai ≠ bi, Then we know there exists at least one prime number whose factor is different in the two ways.

But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.

所以簡單地說, 由於Prime Factorization 是unique的關係, 由2!, 3!, 5!, 7!組成的合成方法只有一種, 所以不用想它是否最大的問題

 B: (Graph, Greedy)

這題真是傷心的一題...看到tile cover相關的題目, 又由於近來在重看Discrete Math的notes
自然就想到去tile coverage的invariant...誰知完全沒有關係...
(其實也是有的, 但就只有知道tile coverage是一個perfect bipartite matching就可以了)

題目很直接, 問能不能UNIQUELY cover board by tiles, 如果不能cover或多於一種方法則print no solution, 不然就直接print solution

本身的想法是想先用invariant判定input的狀態能否cover
但發現糾結的問題是在於不能判定是否unique的情況...
開頭以為是一種detect cycle的變型題, 但怎想也有點問題...

所以就把思想逆轉一下, 反正unique solution的話就只有一種方法cover吧(不是廢話)
那麼就直接simulate cover的過程, greedy的cover吧

詳細地說就是以degree為BFS順序的key, degree 為1的才push進queue
不然的話就把degree減1, 這是O(E)可以完成的事
一路BFS就一路順著方向排tile

完成BFS要是沒有空位的話就是有SOLUTION了, 不然就是沒有SOLUTION
但還是不肯定是否UNIQUE的SOLUTION

這時Editorial又再次有一個想法:
要是圖不止一個solution的話, 那麼肯定有一個sub-graph是全部node的degree >= 2
這個其實跟自己開頭想的有cycle的情況很接近...
但經過幾場的Codeforces發現, 其實很多時候注意degree會方便很多...
回到題目上, 由於全部node 都 >= 2 這些node在BFS時根本不會進queue, 就是說根本不會cover到, 所以已經包括這個case了...

這題算是有點難...我自己是完全想錯方向去了...

C: (RMQ)

再利申, 這題沒做到, 做法倒是想過一下
這題要用上傳說中的Range Minimum Query!
一直都沒詳細研究這個東西, 也搞不清楚它跟Segment Tree, BIT之間的關係...
經過這題後, 好像明白多了一點...RMQ重點應該在於找出Index (位置)
不像Segment Tree或BIT都是在找Value (值)
兩者像的地方都是在於執行在"Segment"上的...但各自想找的東西好像不同...
遲點再研究下

話說這題也是optimize一些東西的題目
這兒發現了一個好像很多題目都會隱藏的一個特性...

假設題目要Maximize F(x)吧
要是可以把F(x) 寫成 G(x)+P(x),
那麼其實可以逐個擊破!
Maximize F(x) = Max(G(x)) + Max(P(x))

這個其實不是什麼難懂的東西, 就是經常沒留意...
以前中學物理也是X跟Y分開算這樣子的吧
聽Marcus說過以前他幫中大ACM中過一道題目, 好像在2D Grid找最近的廁所之類的
也是用這個技巧: X跟Y的方向是互不相干的

回來說CF的這一題, 題目要求的是
Minimize (d1 + d2 + ... + dy - 1 + 2 * hy) + (2 * hx - (d1 + d2 + ... + dx - 1))
看到了吧, 這根本是G(x)跟P(x)的樣式, 可以分開各自找Minimal的
而且這題只是在這個基礎上, 在找每一部分的Minimal時要用上RMQ而已...好像是

這個技巧我不太記得了, 但真的有印象不少題目也有隱藏, 記起來好了