CodeChef April Challenge

About June

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

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恤入手!

Avatar_small
cleaning companies 说:
2019年10月14日 12:30

All of our qualified team is mainly trained to hold a qualified environment while in the cleaning process that will serve any cleaning demands in various ways. Out of buildings so that you can hotel conveniences to places to eat and locations, we cover a number of commercial homes with state-of-the-art cleaning up methods plus dedicated staff in making your space or room look unique and innovative.

Avatar_small
mv home inspections 说:
2020年4月18日 18:31

A new moisture evaluation is over looking pertaining to leaking pipe joints and drains. Exterior conditions that can bring about moisture breach are searched for and also proper fresh air for attics, crawl space spaces, crawl spots and homes are regarded as well. Moisture problems in numerous spaces could go unseen for many years. This wait is identification raises the difficulty plus the cost throughout correcting these kind of issues.

Avatar_small
uk cleaning director 说:
2020年4月18日 18:32

Anyone can take advantage of the comfort of an clean along with well retained home. Home cleaning is often a necessity and a lot of people can't seem to keep their residence cleans as a result of their stressful schedules. Homes must be cleaned regularly to ensure unpleasant odours and vermin infestations to get prevented.

Avatar_small
mentholatum home 说:
2020年4月18日 18:32

When you desire the appropriate home you can definitely find yourself through an endless string of selections. House as well as condo? Suburban as well as city centre? But there exists one certain choice that will bothers a great deal of first-time consumers. Should I get a starter property or possibly a home for you to last for a considerably long time?

Avatar_small
I sell pittsburgh ho 说:
2020年4月18日 18:32

The perfect solution is to distinguish the reason your household sitting available for so very long. Is generally there anything wrong while using home? Would it be something you've got done, or didn't done that may be affecting the property available? You must be worrying precisely to fix pretty much everything and drill down deeper to find out the real cause of the household sitting available for so very long.

Avatar_small
wanamassa reale stat 说:
2020年4月18日 18:33

Residence equity will be the difference relating to the fair market place value in the property plus the sum from all of the loans resistant to the property. By way of example, if a home is worthy of $250, 000 and you will find there's first along with second home finance loan totaling $200, 000, the exact property has $50, 000 throughout equity. Having equity as part of your property is crucial so as to have a new cushion when the market demonstrates declining value when you are holding the exact property.

Avatar_small
north bama real esta 说:
2020年4月18日 18:33

A lot of investors are powered down by real estate property because they just don't have some time or inclination for being landlords along with property professionals, both of which are in reality, a occupation in them selves. If your investor is often a rehabber as well as wholesaler, real estate property becomes more of an business in lieu of an expenditure.

Avatar_small
maid service dubai 说:
2020年5月05日 01:11

It is important to consider is that your choice of maid in honor speech should really be brief. I recommend that it ought to be no much more than 10 a short time long. The chief focus belonging to the wedding day certainly is the bride and even groom. You might play a key element part in the day but it is important to keep this component to your chores short in order that the other speeches will be made while that there are no delay with the celebrations.

Avatar_small
house painting servi 说:
2020年5月05日 01:11

The camp coat will re-activate as well as begin to roll unusual, resulting at a textured effect that should not start looking good. If it does happen it would mean ones own Oxford decorator will likely need to sand downward the fence and hold on till that paint contains dried, so as a result of rushing you certainly will in certainty make the responsibility take a bit longer.


登录 *


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