Topcoder Single Round Match 677

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
36:03:00
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя chrome

Topcoder Single Round Match 677

Автор chrome, 9 лет назад, По-русски

Всем привет!

Сегодня ~~Завтра~~ в 20:00 MSK состоится Topcoder SRM 677.

Предлагаю обсудить задачи здесь после контеста.

topcoder, announcement, 677, srm, chrome

+118

chrome
9 лет назад
33

Комментарии (33)

Написать комментарий?

Abinash

9 лет назад, # |

← Rev. 2 →

+44

chrome is back !

→ Ответить

xennygrimmato

9 лет назад, # |

+10

Looking at the Topcoder Dashboard, it seems like Topcoder is making an attempt to improve user experience for good! The "Launch Arena" button also directly redirects to the web arena, instead of asking me to download an application.

→ Ответить

DmitriyH

9 лет назад, # ^ |

-6

Is it possible to use something like KawigiEdit in WebArena to generate C++ source stub with tests?

→ Ответить

xennygrimmato

9 лет назад, # ^ |

← Rev. 2 →

I am not sure if stable plugins are available for the Web Arena yet. This blogpost from Jan 2015 gives an impression that they're still testing some plugins.

The web arena is open-source and available on Github, if anyone wants to contribute. I think they have some support for calling arena functions to generate code skeletons in various languages.

EDIT: This commit (#c380ff) seems to have added support for the Web Arena Plugin API.

→ Ответить

DmitriyH

9 лет назад, # ^ |

I didn't imply a plugin for Web Arena.
It would be enough for me to have any utility, which converts text problem statement into C++ source file template with class definition, tests and expected results check.

→ Ответить

dthreatz

9 лет назад, # |

Bumping this, since it starts in about 12 hours from now.

→ Ответить

kshj78

9 лет назад, # |

← Rev. 2 →

+13

Печально...

→ Ответить

Lara_Croft

9 лет назад, # |

I see. Your job here is to remind us about topcoder contests.

→ Ответить

EasyCoding

9 лет назад, # ^ |

+38

→ Ответить

ltaravilse

9 лет назад, # |

I can't open the Arena, anyone is experiencing the same issue?

→ Ответить

tweety

9 лет назад, # ^ |

-16

If only topcoder contests were made on Codeforces platform

→ Ответить

DmitriyH

9 лет назад, # |

+13

What about Web Arena? Did someone use in recent matches? Were any bugs?

→ Ответить

dush1729

9 лет назад, # |

← Rev. 2 →

This will be my first match on TopCoder. I have few doubts.

Will submission points decrease if my solution fails to compile or doesn't pass batch test?
If i don't submit any problem's code then also my rating will be affected?

→ Ответить

ballon

9 лет назад, # ^ |

← Rev. 2 →

+17

No.
Yes, but you should open at least one problem statement.

→ Ответить

saurabhverma

9 лет назад, # |

+11

How to do div1 500?

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

+17

DP[v][i][j] — probability that diameter of subtree rooted at v will be i and longest path from v to leaf of this subtree will be j.

When you are merging two trees — you try both possible values for added edge; new deepest vertex is trivial, new diameter of subtree is either diameter of some of two old parts or path connecting deepest vertices in two parts (depending on which one is longer).

→ Ответить

kingofnumbers

9 лет назад, # ^ |

I coded this idea but I got TLE since it's 50*100^4 steps, do you merge dp[v][i][j] and dp[child][i][j] in faster than 100^4?

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

← Rev. 2 →

It's not more than 100^4. In fact constant behind it is also small. And I've just checked it in practice room, my solution runs in 0.005 seconds.

You only need to implement your knapsack in not-so-careless way. At least do all cycles up to largest possible value at this moment, not up to 100.

P.S. Actually I have no idea about number of reachable states here, maybe it works even in O(N^3), looking at running time of my code. However, for knapsack in general it will be N^4.

→ Ответить

kingofnumbers

9 лет назад, # ^ |

I don't know what do you mean by not-so-careless, and I'm doing cycles up to largest possible value, but it's still very big number 100^4 * 50 equal to 5 *10^9, so it's hard to pass even with a lot of constant optimization

here's my code http://pastebin.com/th0fb1KV which got TLE

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

Instead of bounding values for both subtrees by size1+size2 or max(size1,size2) (which obviously gives you N^5 on chain graph), you have to bound values for first subtree by size1 and values for second subtree by size2. Here is a code.

→ Ответить

kingofnumbers

9 лет назад, # ^ |

that magic if (dp[v][i][j]>1e-20) made my code very fast!!! but your code is fast even without it!

I also had a bug that I am iterating to mx[nd]*2 which can become 200 (note that in my code mx[nd] is already multiplied by 2) so I changed it to min(100,mx[nd]*2)

I will look through your code to know why it's fast

thank you

→ Ответить

kingofnumbers

9 лет назад, # ^ |

by the way this solution doesn't have the official intended complexity!

→ Ответить

tanphatls987

9 лет назад, # ^ |

Maintain another array depth[v]-maximum depth in subtree v.In DP[v][i][j] you can see that i can only go from depth[v] to min(depth[v]*4,2*(n-1)) and j go from depth[v] to 2*depth[v].So we can cut off many unused states.I got AC that way.

→ Ответить

kingofnumbers

9 лет назад, # ^ |

I did what you said, I got AC but it barely fit the TL (running time is 1.8 s) also I had a bug in my code which made it running more steps and even going outside array bound

thanks

→ Ответить

aid

9 лет назад, # ^ |

First for each subtree and each d between 0 and n calculate probability that subtrees depth will be at most d. Then choose center of graph and length of diameter. There are 2 cases: center is on vertex, or center is on edge. In first case depth of tree should be half of diameter and there should be at least 2 subtrees with that depth. In second case each end of our edge should have fixed depth, which depends on the position of center on edge and edge length.

→ Ответить

mmaxio

9 лет назад, # |

+11

Where is instant post-match editorial when you need it the most? ;_;

→ Ответить

Abinash

9 лет назад, # |

How to solve div2 Hard ?

→ Ответить

ketanhwr

9 лет назад, # ^ |

I had a weird DP solution for Div2 900

Let dp(i,j) denote the length of smallest palindromic path between node-i and node-j

Note that dp(i,j) = -1 if there is no pair (u,v) such that (u,i) and (v,j) are valid edges and label on (u,i) is equal to label on (v,j).

The base cases will be:

dp(i,j) = 0 if i==j (trivial)

dp(i,j) = 1 if (i,j) have an edge between them.

Now we can loop over all pairs (u,v) such that (u,i) and (v,j) are valid edges and label on (u,i) is equal to label on (v,j). Our answer for dp(i,j) will be 2+min(dp(u,v)) for all (u,v)

Our final answer will be dp(0,1). Sample Code: Link

→ Ответить

Abinash

9 лет назад, # ^ |

I don't think it's a DP solution ! But the idea is really cool !

→ Ответить

Lewin

9 лет назад, # |

+59

cgy4ever is the writer of this round. It seems he may be busy now, so I'll post solutions for him.

Here is code:

div2: http://pastebin.com/sgnpradR

div1: http://pastebin.com/PLHbRYF9

some hints:

div2 easy: just do what's described in the statement.
div2 med: 2 approaches 1) The string has length at most 40. Brute force 40^4 tuples of positions that the 4 strings can take on. 2) Try all orders of concatenating the string together (how do you merge two strings?)
div2 hard: Make a new graph where new vertices are a pair of original vertices. What are the edges in this new graph?
div1 easy: 2 approaches 1) Fix the number of multiply by 2 operations. Now, we can proceed greedily. 2) Work backwards (i.e. operations are divide by 2 or subtract 1).
div1 med: 2 approaches: 1) Root the tree arbitrarily. Compute prob(tree has diameter <= x) using a dp based on longest path to leaf. 2) Find the probability that the graph has a particular center and diameter. The center can either be a vertex or at the middle of an edge.
div1 hard: First, any strongly connected tournament graph has a hamiltonian cycle. Find any such one. Then, we can do bubble sort (see code for more details). (Tricky case for div1 hard. A cycle 0->1->...->29->0. All other edges go from bigger numbers to smaller numbers.)

→ Ответить