Today, at 6 PM MSK (3 PM UTC)

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 176 |

6 | maroonrk | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 23:57:06 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I'm having problems with registration (It says that registration is by invitation only despite the fact I have automatically advanced to the Round 2). Any ideas how to fix this?

I think admins just forgot to add byes to advancers pool

how bad!!!

Same here.

Hey where has cgy4ever gone?

Damn , my classmate wrote that stupidness :D idk wht's going on there so sry .

`I'll be correcting the issue with those who have byes. Those compeittors will be automatically registered for this round.`

— said TopCoderWe just fixed it: "All competitors with a bye have been automatically registered, our apologies for the trouble. For everyone else competing today, be sure you register at least fifteen minutes before the match begins, thanks!"

WEB ARENA IS DAMN TOO SLOW -_-

I can't login now. I could several hours ago.

Sorry, you cannot perform this operation because you are not assigned to this room. The likely cause is that you did not successfuly register for the match during the registration period.But I am registered...

Surprisingly my randomized solution for A passed.

I shuffled the array 1000 times and check if if possible to fix the first element and apply GCD or LCM using DP.

Unfortunately it was not enough to advance, my browser got frozen while testing sample cases.

I would like to know a deterministic solution.

Ugh. I failed 500 on slightly exceeding the memory limit (so slightly that changing long long to int in 4 places would've fixed it).

How to solve the first question?

Unfortunately most of passing 500's solutions were ugly (including mine).

Admins said the intended solution was meed-in-the-middle, but I just googled how to count the number of cliques (http://cs.stackexchange.com/questions/9209/finding-all-cliques-of-a-graph).

tourist's solution looks good

Why this code is TL on topcoder? 400pt

http://pastebin.com/1wxnCQhM

Would have pulled of successful last second submission. Did not change min->max in two lines during last sec updates. Two things 1. The excitement of a successful last sec submission would have been great. 2. Generally frustrated for missing because of typing miss!

My solution on 500 passes if fix stupid bug in 134ms.

Solution is following. We can count sum for each edge independently. For one edge answer is equal to ({Number of cliques with a} + {Number of cliques with b} + 1 — {Number of cliques total}). So the solution is to find number of cliques in graph except each vertex. It's well known, that dp on subsets, works in time 2

^{n / 2}if don't count same mask twice, and choose to get or not to get smallest vertex each time. If use same cache, it's works even faster, than n*2^{n/2} (i think even in 2^{n/2} time, but I can prove, only n/2*2^{n} visited states).Would you mind elaborating that DP which counts cliques a little?

dp[S] = count of cliques, which are subset of S

Let's v be vertex in S.

, where N(v) is set of neighbors.

If always get as

vvertex with minimal id, there isO(2^{n / 2}) states reachable. Ifvis less thann/ 2, there are less than 2^{n / 2}branches, ifvis more, there are less than 2^{n / 2}states total. Order of vertices is imortant. For example, choose random vertex each time is bad (but choose random order one time is ok, of course).I did it in other way. Divide vertices on two equal parts. For first part precalculate for every subset

Ais it clique or not, and if it is clique calculate mask of vertices in second part which is connected with all vertices inA(both could be done by & incident masks of vertices inA). For second part calculate for every subset is it clique. Then calculate convolution of this array. For each queryS, we look for subsetsAofSin first part and ifA-clique add number of subsets in second part which is clique and incident toA.the same problem, but i have zero execution time on little test

According to the following, system calls like

`clock()`

are not accounted for the reported "Execution time", but are accounted for the timeout, and for some reason the call to`clock()`

is slow on TopCoder: http://apps.topcoder.com/forums/?module=Thread&threadID=507280&start=0&mc=9#511776thanks for link!

Same story here :(

I think problem 400 was nice for people who like

`if`

s a lot. I'm not sure I like`if`

s quite so much :(You can also solve the 400 by checking if any pair or triplet of numbers can reach the target (also handling the case where n=1 correctly).

I solved it by bfs on reachable states. Every number 2

^{i}3^{j}is a pairi,j. There 9 different types of pairs (first and second coordinate could be <,=,> then int). It could be proven that every type of pair could be useful not more than twice. Then I made search on this 3^{9}states.I had the same approach. How to prove it?

Consider about 10 cases =) I haven't done it during round, and for sure submited 4^9 states solution.