I and my friend jqdai0815 and vfleaking are going to virtual participate (single machine) the WF 2015 online on site.

It might be interesting to record our progress and commentary on the contest and problems here :)

--18:05(in GMT +8): We are still waiting for the problems to be available online :)

Meanwhile, PKU(Peking University) gets the overall first blood. Their team member contains two experienced coders which participated in WF 2013, I guess they will get a good result in this WF :)

It seems Problem A is quite easy, many teams solve it during the following two minutes :)

Forget to mention, there are 13 problems this year. I am wondering if it is all hard problems like last year, or some easier problems? The problem type will definitely affect the result of this fierce competition :)

--18:17 nearly 20 minutes passed, no one solve two problems, and we are still waiting for online problems :)

--18:21 It seems the pdf version is out, but we decide not to look at it since we want a virtual competition :)

--18:24 CMU submits F and got -1, Maybe F is the next problems to solve?

And Tsinghua get -1 on C, Zagreb gets -1 on F, I guess C and F will be easier than other problems :)

THU gets first blood on C, and FCEN get first blood on F.

Good start for THU!(I am from THU too), Hope they can keep up the good work :)

Princeton gets first blood on D. What are the members of Princeton this year?

Anyway...The problem is still not online...I decide that if it didn't come before 18:40, we are going to look at the problems first <_<.

"ACM ICPC World Finals 2015 problems to be added shortly after contest start", it seems I misunderstand the world "shortly".

ITMO and Toky solved D, now the problem being solved are A,C,D F, It should be 4 easy problems, I guess during the next 10 or 20 minutes, many teams will solve them too.

--18:40, the website doesn't have problem still, well, We decide to still wait without looking at the pdf version:(

University of Warsaw solved L, well, I think this year's problem will not be like last year, and the first place will end up 10 or 11 problems I guess.

Tokyo solved J, I think rng_58's team are on a good track, they still have more other easy problems to solve :)

PKU solved D and becomes #1, This team is really exciting today :)

Now, 7 teams solved 3 problems :)

Tokyo solved C and becomes #1 again, really good competition :), I'm excited too(Where is the problems to submit online \T_\T).

ITMO got 6 , while Tokyo and Moscow and 5.

They are the three best team in my opinion:) Thus the result is pretty reasonable.

It seems all CN teams solved 4 problems at most ,I hope CN teams can do better later :)

Tokyo now got 6, and back to #1.

Notice that after tourist start to writing C, ITMO got 4 problems in just 20 minutes, it is just insane...

Well, Since the problem is still not out on kattis, I decide to look at the pdf version first \T_\T.

Finally it starts! --19:39 19:53 the log in is broken, so we made a new account. And vfk got problem A. vfk is working on problem D. And he got D soon. I am working on problem F, it is a stupid problem. C is a stupid problem too. I got F and C in a roll.

So we have 4 problems now.

It seems J is a simple FFT, L is a simple Huffman, and H is some kind of math problem... We are working on them now. vfk got J right. dyh is working on H. I am going to code L later.

dyh got H, we have 6 now.

I got L. We have 7 now.

22:05 -vfk got I. We have 8 now.

dyh is coding E, umm, the rest of the problems is quite hard now, we need to be careful.

We got E, we have 9 now.

In the last hour we got K. Seems end up 10 problems <_<

...During the last moment, we are switching on 3 remaining problems B G M and got none of them, so sad T_T.

We got 10 problems and penalty 1066 in the end...

In the Round 2 of the hacker cup, I scored 0 points.

The default folder for my web browser is the one for Round 1(didn't change since last time), and I mistakenly submitted all the output and code for R1 and get 0 score at the end. Maybe because its 5am in China and I am at half-sleep mode.

It is very funny, but I am very sad now >_>...

UPD. I submitted them at gym, A is wrong,BC are right, D got TLE so I tested it by copying another one's accepted code, the output is right. So if I didn't make such silly mistake I would get 90 points. Whatever, I need to watch some anime, play some games to comfort myself T_T.

I am going to quit from Algorithm contests since I want to be a moe~moe~ theoretical computer scientist <_< . In memory of my algorithm competition days, I plan to collect those problems(remove some routine trivial problems) written by me and translate those Chinese ones into English, it might be interesting for all of you to solve :)

It might take some days to finish, I will first list some English problems :)

From Multi-University Training Contest 2013 and 2014

1. Life Game
2. Crime
3. Endless Spin (one of my favorite)
4. JZPTREE
5. Jinloid
6. The only survival
7. Hero’s assistant
8. Hero meet devil
9. NO ACM NO LIFE

A very old problem on SPOJ:

JZPGYZ

From 2014 ACM/ICPC Asia Regional Anshan Online and Onsite:

1. Biconnected
2. Square

Codeforces:

1. Contest 146
2. CF#172 C

Codechef:

1. Union on Tree
2. String Query

236A - Boy or Girl

It is a very simple problem, just count how many distinct chars in the input and output the correct answer.

236B - Easy Number Challenge

First of all, we can make a table of size a*b*c to store every number's d value. Then we can just brute force through every tripe to calculate the answer.

235A - LCM Challenge

It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if n is at most 3 and then we can simply output 1,2,6.

Now there are two cases: When n is odd, the answer is obviously n(n-1)(n-2). When n is even, we can still get at least (n-1)(n-2)(n-3), so these three numbers in the optimal answer would not be very small compared to n. So we can just iterate every 3 number triple in [n-50,n] and update the answer.

235B - Let's Play Osu!

Let us take a deep look at how this score is calculated. For an n long 'O' block, it contributes n² to the answer.

Let us reformat this problem a bit and consider the following alternative definition of the score: (1) For each two 'O' pair which there is no 'X' between them, they add 2 to the score. (2) For each 'O', it adds 1 to the score.

We claim that this new definition of the score is equivalent to the definition in the problem statement.

Proof of the claim: For an n long 'O' block, there are C_n² pairs of 'O' in it and n 'O' in it. Note that 2C_n² + n = n².

So now we work with the new definition of the score. For each event(i,j) (which means s[i] and s[j] are 'O', and there is no 'X' between them). If event(i,j) happens, it adds 2 to the score.

So we only need to sum up the probabilities of all events and multiply them by 2, and our task becomes how to calculate the sum of probabilities of all the event(i,j). Let P(i,j) be the probability of event(i,j).

We can see that P(i,j) can be computed by . Then we denote P(j) as the sum of all event(i,j) for i<j. We have dp(0)=0 and dp(j)=(dp(j-1)+p_j - 1)*p_j

235C - Cyclical Quest

This problem can be solved by many suffix structures. Probably using suffix automaton is the best way to solve it since suffix automaton is simple and clear.

Let us build a suffix automaton of the input string S, and consider the query string x.

Let us also build a string t as x concatenated with x dropping the last char. One can see that every consecutive sub-string of t with length |x| is a rotation of x.

Let us read the string t with suffix automaton we have build, and every time take the first char out and add a new char, add the answer by the number of string equal to this current sub-string of t (which is a rotation of x).

And one more thing, we should consider the repetend of x as well, check my solution here:2403375.

Check here if you are not familiar with suffix automaton :e-maxx's blog

235D - Graph Game

First of all, let us consider the simpler case of trees.

Let us use Event(A,B) to denote the following event "when we select A as the deleting point, B is connected to A".

Clearly, if Event(A,B) happens, it would add 1 to totolCost.

So we can just simply calculate the probability of every Event(A,B), and add them up.

Let us consider how to calculate the probability of Event(A,B).

Assume there are n vertices in the path between A and B, we claim that the probability is simply 1 / n.

Let us try to prove it using induction.

First let us assume there's a connected sub-graph of the tree containing both A and B, if the sub-graph only has n vertices, then the event happens only if we select vertex A, so the probability is 1 / n.

Otherwise, assume it has x vertices there is two cases: whether the selected vertex is on the path between A and B or not.

In the first case, the probability of Event(A,B) happen is 1 / x because if we don't select A, Event(A,B) will never happen.

In the second case, the sub-graph containing A,B has become smaller, so the probability is (x - n) / xn.

So add them up we can prove this statement.

Then we can solve the tree case by simply add up the inverse of every path's length in the tree.

And for the original case, there's at most 2 paths between A and B.

If there's only one path, then everything is the same with the tree case.

Otherwise, the path between A and B should pass the cycle in the graph.

Let us examine this case, you can see that there 2 types of vertex:

Vertex on the path of A to cycle or B to cycle, they should not be selected before A because once they're selected, A and B lost connectivity, let us call them X.

Vertex on the cycle, the two paths from A to B, each path contains a path in the cycle, let us call them Y and Z.

So there are two possibilities: X and Y are free when A is selected, X and Z are free when A is selected.

And we should subtract the case that X and Y, Z are all free when A is selected because it double-counts before.

So the probability is 1 / (X + Y + 1) + 1 / (X + Z + 1) - 1 / (X + Y + Z + 1).

Check Petr 's solution for the details: 2401228

And my C++ implementation: 2403938

235E - Number Challenge

Let us consider each prime in one step, the upper limit for a, b, c is recorded.

So if we fixed the power of 2 in each i, j, k like 2^x, 2^y, 2^z, then their upper limit becomes a / 2^x, b / 2^y, c / 2^z, and the power of 2 in their multiplication is just x+y+z.

Let us denote dp(a, b, c, p) for the answer to the original problem that i, j, k 's upper limit is a, b, c. And their can only use the prime factors which are not less than p.

Let the next prime to be q, so we can try to fix the power of p in i, j, k and get the new upper limit.

So we can do transform like this: dp(a, b, c, p) = sum of dp(a / p^x, b / p^y, c / p^z, q)·(x + y + z + 1)

Check my code here: 2404223

Also you can check rng_58 solution here: http://codeforces.me/blog/entry/5600

If you have any problems, you can ask here :)

Hi!

Codeforces Round #146 is going to be here soon. Round is prepared by YuukaKazami, MinakoKojima. I write problems for Div I and MinakoKojima write for Div II. Gerald did a great job in coordinating round preparing, and he also give some pretty good advise about problems. I'd like to express my gratitude to him. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Polygon system as well and Mary Belova (Delinur) for translating problems. Also thanks to donehl for testing the problems and making his comments about the problems.

Score distribution is 500-1000-1500-2000-2500 in both divisions.

Hope you enjoy the problems! =)

I apologize for the 10 minutes delay.I'm very sorry for the inconvenience I caused. So I'm writing a good editorial for compensation :)

The Editorial is here: Editorial

Congrats to winners!

Div1:

1.rng_58

2.Dmitry_Egorov

3.bjin

4.Petr

5.Egor

6.tourist

Div2:

1.RiKang

2.Caesar11

3.Gabaum

4.ilona

5.Bidhan

6.sm_hossein

First of all I wanna thanks contest organizer for their effort to make it REALLY a good competition ^_^.I would participate next year if I could ^_^

I wanna summarize my trip at VK cup ^_^.

On the first day I arrived at the hotel.I got very tired so I fall asleep >_<.

On the second day there's a AI-contest.It's very interesting!My Robot "DiaoSi"(In Chinese it means a man without money or luck or girlfriends or something) kill two cars in a shot in Round 1.It make me really excited.rudradevbasak's car impress me a lot.It seems just driven by human!

I'm a big fan of tourist,It's lucky for me to seems him in really world!(I fail in China National Team Selection Contest and has no chance to take part in IOI T_T).He's really handsome!

The contest problems is randomly-ordered and very interesting.

(It seems there'll be a online-version of this contest.So I will not talked about contest problems...)

I make a very silly mistake in Problem C.I use a.substr(at-3,at) to get the last 3 chars.But It should be a.substr(at-3,3) T_T..Fortunately I found it at the end of contest..But losing many points T_T.

s-quark take the lead for a long time.But sevenkplus overtook him by 2 successful challenges.At last tourist solve all the problems and take the lead.

But unfortunately tourist's A fail T_T.So sevenkplus take home 30,000. s-quark take home 20,000 $.They're my close friends ^_^.

sevenkplus is only 16-years old and will represent China for this year's IOI.I'm looking forward his nice results at IOI ^_^.

s-quark is also a very talented student.He's a little older than me and has celebrated his 17th birthday recently.He also make onsite in GCJ Round 3(rank 7-th,But he can't take part onsite round because age-limitation T_T).

Before ST I ranked 11-th,the first who don't have price T_T.But some people fail on some problem and I become 6-th after ST.take home 1000$ ^_^.

They also give a cool laptop computer to everyone.I can't wait to use it ^_^.

(-To be continued...It's late now T_T).

I'm very happy ^_^

lost it very quickly T_T