Topcoder Single Round Match 677

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

До соревнования
Codeforces Round (Div. 2)
5 дней

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

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

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

Всё →

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

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Всё →

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

→ Прямой эфир

Детальнее →

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

Topcoder Single Round Match 677

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

Всем привет!

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

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

topcoder, announcement, 677, srm, chrome

+118

chrome
10 лет назад
33

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

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

Abinash

10 лет назад, скрыть # |

← Rev. 2 →

+44

chrome is back !

→ Ответить

xennygrimmato

10 лет назад, скрыть # |

+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

10 лет назад, скрыть # ^ |

-6

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

→ Ответить

xennygrimmato

10 лет назад, скрыть # ^ |

← 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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # |

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

→ Ответить

kshj78

10 лет назад, скрыть # |

← Rev. 2 →

+13

Печально...

→ Ответить

Lara_Croft

10 лет назад, скрыть # |

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

→ Ответить

EasyCoding

10 лет назад, скрыть # ^ |

+38

→ Ответить

ltaravilse

10 лет назад, скрыть # |

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

→ Ответить

tweety

10 лет назад, скрыть # ^ |

-16

If only topcoder contests were made on Codeforces platform

→ Ответить

DmitriyH

10 лет назад, скрыть # |

+13

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

→ Ответить

dush1729

10 лет назад, скрыть # |

← 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

10 лет назад, скрыть # ^ |

← Rev. 2 →

+17

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

→ Ответить

saurabhverma

10 лет назад, скрыть # |

+11

How to do div1 500?

→ Ответить

I_love_Tanya_Romanova

10 лет назад, скрыть # ^ |

+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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

← 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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

→ Ответить

tanphatls987

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # |

+11

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

→ Ответить

Abinash

10 лет назад, скрыть # |

How to solve div2 Hard ?

→ Ответить

ketanhwr

10 лет назад, скрыть # ^ |

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

10 лет назад, скрыть # ^ |

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

→ Ответить

Lewin

10 лет назад, скрыть # |

+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.)

→ Ответить