DarthPrince is PrinceOfPersia.
Also hi Monika :)

Hilarious story behind this handle

On a difficulty scale ^^

And div2 first question was Eleven...

was it a mystry??

What's need announcement for it. it will occur unexpectedly. :D :D

Why are all comment sections on here filled with inane crap?

Damn, codeforces is the last place on earth where I expected to learn this, but it is kinda a fun fact. The more you know.

All official Codeforces rounds are rated by default. They would have mentioned it, if it is unrated because of any reason.

Maybe Unrated...

I don't think it can be anyone other than Eleven. Correct me if im wrong.

A reason other than Stranger Things itself!?

I hate you!

This is shit

Yes it's not shit. And that is because unlike many stories that feature kids, Stranger Things would not work if they replaced the kids with adults. For the story to turn out as it does, it is necessary for the protagonists to be kids. As summarized by Jared on Wisecrack (video spoiler alert),

"..the kids don't save the day despite being kids, they save the day because they were kids.."

,

why did you comment that here?

Any way you can access the map by another map

map<map<int,int>,map<int,int>> M;
map<int,int> S;
M[S][0] = 1;
cout << M[S][0];

Да

preparing a robust version of HLD :D

I came here to comment this, now I’m leaving.

Wait for it....

I am also waiting for the same.. Hope for the nice problemset. As expected from princeofpersia

its not tough its tof !

"Игра проходит на ориентированном ациклическом графе"

its DAG :/

DAG (Directed acyclic graph)

no

i thought C was easier.. maybe im not good at graph problems :)

maybe

Div1B was straightforward, Div1A was pretty tricky and I needed to think about it for few minutes and decided to go with a bet that seems fine to me but I didn't prove it carefully :x

yes , but both traditional

Because it is a classic game theory problem.

Use Dynamic Programming

dp[100][100][26][2] The 2 is for turn Emulate the whole situations. O(N^3C) time complexity where N is # of vtx, C is # of alphabets

I used an array state[A][B][x] to store all the possible situations, where A is the position to move first, B is the position to move second, and x is the limitation(i.e. only edges whose weight >= x can be used). Then all these nodes form a game tree. then update each node in topology-sort order, i mean, from leaves to root and make sure you visit all children nodes before you visit a node itself. Then the problem is simple. if there exists a child of a node is "first move to lose" then this node should be "first move to win", otherwise "first move to lose". All you need will be state[i][j][0].

I'm still waiting for system test, hopefully I'll pass :P

UPD:It passed now XD

now i understand it. thanks for all help!

for C: you will count which starts with ith character let number of ( : a, ? : b, ) : c if c>a+b, then it means if we change all ?s to ), it is impossible so, it is always impossible!(for example, (?))) is always impossible!)

similary, we can think something like a>b+c, (for example, (((?) )

Hope my comment helped you..

For D, since you can get every possible state, just see the states that each state can go to, if any of them is winning, then the current state is winning, losing otherwise.

Also, it has appeared on topcoder: https://community.topcoder.com/stat?c=problem_statement&pm=13369

No idea, but I have a hack for your code: ())?

Another similar problem is from XV Open Cup (2014-2015) GP of China.

Problem I: http://opencup.ru/files/ocf/gp10/problems1-e.pdf

CF discussion: http://codeforces.me/blog/entry/16701

yes

For each starting position, calculate the upper/lower bound for each ending position. You may reduce the time complexity if you do that in left to right. If the upper goes negative, you should stop. Otherwise, just check that upper >=0 which means there are some good solutions. (No matter what they are)

+1 (spent 1.5 hours on ), thought I found a small mistake which I couldn't fix.

Same story.

I tried to solve for all length ≤ K separately with hash and for strings having length > K with centroid decomposition but I didn't even came to writing second part. I'm not even sure my solution is enough to get accepted.

You're a pupil, what rating are you trying to save? :p

Yup!

I wonder how long he takes to login :P

You can use topsort. Than start back from the nodes and calculate next dp values : dp[current_player][previous_character][first_node][second_node].

Notice that the value for k = 0 is the number of spanning trees of the complement of the input tree. This can be computed by the matrix-tree theorem (https://en.wikipedia.org/wiki/Kirchhoff's_theorem).

Using https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem#Explicit_enumeration_of_spanning_trees, we can know that if we compute the determinant of the Laplacian matrix of a complete graph with weight X for edges in the input tree, and Y for the other edges, we get a polynomial where the coefficient of X^aY^b gives us the number of spanning trees of the complete graph with a edges inside the input tree, and b edges outside (Since spanning trees have n - 1 edges, a + b = n - 1). We can compute this polynomial by interpolation.

Because we need to evaluate in n points, and the cost of each evaluation is O(n³) (or better with faster algorithms for computing determinants), the complexity is O(n⁴)