CodeChef April Challenge

About June

qwer posted @ 2014年6月20日 16:48 in CodeChef with tags codechef June Sereja and Arcs , 7032 阅读

CodeChef June14

 Problems:

Name Code Successful Submission Accuracy
Chef and SubarraySolved CHEFZOT 5554 34.66
Guessing GameSolved GUESS 4397 23.11
Forgot PasswordSolved FORGETPW 2579 10.4
Chef and Digit JumpsSolved DIGJUMP 1484 7.74
Maxim and ProgressionsSolved MAXPR 729 11.58
Chef and FunctionsSolved FUNC 626 3.16
Little Elephant and BlocksSolved LEBLOCKS 300 15.58
Two CompaniesSolved TWOCOMP 141 8.37
DARTS501Solved DARTS 86 2.62
Sereja and ArcsSolved SEAARC 36 3.66
 

 Board:

Rank Country User Score
1 mugurelionut 10
2 sokian 9.94
3 kevinsogo 9.932
4 notimesea 9.915
5 wangyisong1996 9.912
6 avolchek 9.895
7 xllend3 9.822
8 stolis 9.75
9 zcc598066456 9.742
10 zhouyuchen 9.697
 

前面的几道题都比较水,一行题解:

Chef and Subarray

最长连续非零串,扫一遍即可
 

Guessing Game

输入输出

Forgot Password

模拟题

Chef and Digit Jumps

可以发现跳的次数不会太多,暴力

Maxim and Progressions

dp[i][j]表示以i结尾,公差为j的个数

Chef and Functions

__Shi 据说是打表+乱搞。。

Little Elephant and Blocks

不同数字分开计算,枚举两个串中间有几个数,背包求个数

Two Companies

预处理两条链是否会相交,最大点权独立集,最小割
 
 
比较有意思的题:

Sereja and Arcs:

刚看到题的时候感觉没有思路,实在想不出nlog(n)的算法。在实践证明后,发现可以nsqrt(n)log(n)做。

将颜色分成两个集合A,B。A中的颜色对应点数大于sqrt(n),B中的颜色对应点数小于sqrt(n),那么答案就是A中两种颜色相交的个数(1)+B中两种点数相交的个数(2)+A中一种颜色和B中一种颜色相交的个数(3),分开计算。

(1):可知元素个数小于sqrt(n),那么枚举两种颜色分别是什么,单独提出,o(n)扫一遍。

(2):对于集合内每种颜色列举出每一条边,排序后树状数组维护。

(3):B集合内每种颜色列举出每一条边,对于每一条边,在A中的每一种颜色中都算一遍。

不靠谱的复杂度分析:

(1):Σ(Ai+Aj)=Σ(Ai)*Size(A)<nsqrt(n)

(2):Σ(Ai*Ai)*log(Σ(Ai*Ai))=Σ((n/Size(b))*(n/Size(b)))*log(Σ(Ai*Ai))=n*n/Size(b)*log(n*n/Size(b))<nsqrt(n)log(n(sqrt(n)))

(3):经过计算得到复杂度是n^2级别,机智地把块的大小调到3*sqrt(n)即可过。原因大概是把一部分B中的元素移到A中,然后就没有卡掉。。

DARTS501

challenge

Orz __Shi - > http://shizhouxing.is-programmer.com/
Avatar_small
__Shi 说:
2014年6月20日 16:50

跪随手T恤入手!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter