Recent actions

Problem B 63ms solution :) In each group of friends,if the group is legal,all points should be connected directly between any pair, so just check if the power of point is equal to the groupsize-1 You may form groups by using union-find set Here's my c++ solution qwq http://codeforces.com/contest/791/submission/25794980

so good

Got it. There was a mistake in DFS.

Accepted Python code: http://codeforces.com/contest/791/submission/25642361

hey folks.... i attended VK cup Round 1 div 2 contest.... before contest my rating was 713 and after the contest i gained +134 Rating Points... and my new rating should be 847 but in my profile it is not shown 847 but shown my previous rating 713... :( :( so i want to why this is happened please someone explain please....

g++ -E and C++ online code formatter to attack it!

I think it's fine. If I thought it's unprofessional, I wouldn't prepare such a problem.

I solved 1 problem in this contest and in my "contests" section it's showing +68 and new rating 1034. But in my profile it's showing my previous rating, 966 :(

Errichto Do you really think it's unprofessional to mention the sponsor name in the statement or that's just to match the problem requirments? If yes, why?

What is your CD logic?

Why is it that the graph and the max ratings have been updated but the present rating has not yet been updated?

It's a bit like saying that 771D - Bear and Company was about strings — there was a string on the input but it doesn't mean much. I would say that the Tree Jumps is a dp + number theory problem.

Btw. you're saying that almost everybody solved at most 3 problems, so for them 2/3 tasks were about graphs. It would be true if they solved exactly 3 problems, not "at most 3".

771A - Bear and Friendship Condition and 771C - Bear and Tree Jumps? It was about 24 teams than solved more than 3 tasks on VK Cup 2017 - Round 1. So, for most of participants 2/3 tasks was graphs.

It seems, that Div2C has some duplicate tests in the final test set, most likely due to multiple hacks with same values or something similar.

More exactly, tests #41 and #55 as well as #42 and #45 are the same. I guess this is some sort of bug? Probably not only for this problem?

wasn't there only one graph problem (Friendship Condition)?

Thank you

Thank you

Ahhhhh finally pass problem E. Just a tiny bug in my reference of Half Plane Intersection, which has been used to solve ten or more problems. TAT....

I got it, what has happened is, that after the overflow the value has become equals to m. I thought probablity of this is too less. My bad luck. :(

It seems like the max rating and the rating graph has been updated, but the actual rating shown in the profile has not.

for ans to be "YES" there should be (x*(x-1))/2 edges, which would be of the order 10^10 but m < 150000 hence the ans will be "NO"

But why?

Most likely, you were disqualified.

Hello.All my submissions are not evaluated yet. They are showing 'skipped' in my profile. Can I get to know the reason behind this?

@Errichto This question is regarding problem B of div 2.

This code in Python generated TLE while the same logic implemented in C++ passed all testcases.

Python: http://codeforces.com/contest/791/submission/25622032 C++: http://codeforces.com/contest/791/submission/25628098

Can anyone help me with this?

Why ? take the example of a tree with 10^5 vertices . Therefore edges are 10^5 — 1

Someone is cheating by using that as second account.

Edit:

Obviously this guy:

http://codeforces.com/contest/791/submission/25623078

http://codeforces.com/contest/791/submission/25623055

Compare the tokens used.

but then the number of edges required would be > 150000 so the ans anyway has to be "NO"

actually the number of nodes present in a connected component can be of the order 10^5. So if x=10^5 and it is int then (x*(x-1))/2 will overflow. This is the reason why u got WA

HOW could someone do that !!!

In Div 2 B, I used the fact that each in each connected component there should be an edge between each pair of vertices. Hence the number of edges given should be equal to — summation x*(x-1)/2 for each connected component, where x = size of the connected component. I used int and got a WA and when I replaced it with long long it got Accepted. Now my question is if the answer has to be "YES " then sum should be <= 150000 (since that is the range of M in the question) so int should suffice then why did I get a WA?

It also can be solved using centroid decomposition.

look through defines

Yep that was the problem.. Python recursion stack size is small..

Sorry my bad.. will take it out..

Ahh yes your right! Python stack depth is only around 1000. The correct answer here offers a lot of light. Thanks a lot!..

wtf

is it machine link?

Happiness is getting into the darker shade of blue:)

Created or updated the text

What a pleasure to solve some really original and less typing problems.

Maybe stack overflow?

А попроще?

Buggy Div2.D !! :D

python stack size of quite less. RE is because of Recursion depth limit reach.Similar BFS solution will pass.

Dont paste full code in comments, instead paste link to the code

Но. если у кого то место<=400 , определяется плагиаризм тебе повезло!

Could some good soul who knows python please explain why this code gave runtime error in pretest 11 which has n=m=150000?. This isn't the first I've got such an error doing DFS in python. I really want to know as I'm finding it impossible to figure out on my own.

Hah, I wouldn't ever think that there is ambiguity in my comment =)
I meant the problems are superb, like luxury 5 star hotels =)


I see what's the problem — in different browsers these stars look differently.
In my main browser they are of gold-yellow color.

Just go on updating the parent node from it's children node. All the nodes in children's subtree will reach parent node in just prevDistance+1.

As it turns out, I screwed up in the same place

if x < 26:
    return 'A' + chr(x+ord('a'))
else:
    return 'B' + chr(x+ord('a'))

¯_(ツ)_/¯

no

He meant 5 star rating I guess.

Well, I had some frustrating bugs.

If I took 401 place but 399 place was taken by two people, will I participate in the 2 round?

Tnx for the not copied contest :D

When are we able to solve the problems on problemset?

Watch out for Aaaaaaaaaaa, which is 11 characters, any name longer than 10 character is not allowed. I got WA on first try because of this.

also your output on the judge is

A A A A A A Aa Aa

I was doing this, but I couldnt figure out how to get the distances for the paths that go through the father node.

its*

It seems that there is more than one O(n2) solution that got AC. I tried really hard to prepare tests in this problem but I didn't succeed. I'm sorry for that.

You basically root the tree in any node and do two DP/DFS passes:

First, compute the solution for all subtrees — you can easily do that by storing number of nodes in distance d mod k from the root in current subtree. The solution is then the sum of jumping distances in all children + number of nodes in distance d mod k == k-1 in all children.

In the second pass, you just need to compute remaining distances using DP values in parent of every node: sum of distances above the node = sum of distances above its parent + sum of distances in all parent's children except for the current node + the same trick with modulo (index hell inc.)

On task D, div 1, my solution in O(n2) got AC, weak tests :\

An example on which I get TLE: n = 3·105, ti, j = (i+j % 2 ? -j : j+1)

Link to solution

Yep, or n = 92684 and m = 148290... System test 29 |-(

When the system testing begins?

Your solution gives this output "A A A A Aa Aaa Aaaa Aaaa" on my computer which is wrong

Nothing is wrong.

"rated"?

EDIT: If you didn't like problems, I will be glad to hear what exactly was bad for you. Maybe I can avoid it in the future.

Its too vulgar :-P..

I don't know about Div1, but Div2 set of problems deserves ⭐⭐⭐⭐⭐

No

what's wrong with this output A A A Aa Aaa Aaaa Aaaaa Aaaaa in pretest 1 problem c Div2

How to solve div2 C?

NO

But the fact is that ( 65538 * 65537 / 2 ) % 2^31 = 98305.

There were those who used int instead long long.

The editorial is ready but it will be imported only after the system testing. Sorry for the inconvenience.

And I'm glad you liked the problems.

No, it was just a dp on tree problem. For a node add the answer for its subtree and then add answer for all its siblings. For this you just need to store at each node frequency of nodes in subtree with distance%5.

hack test for problem A (VK Cup): n = 65538 m = 98305 and any edges which unite all 65536 vertices in one component.

let x be number of vertices in component

let y be number of edges in component

Who wrote if (x * (x - 1) / 2 != y) puts("NO") and used int32, failed on this test.

Oops.

IMO the problems are a little harder than usual, but are very nice. How to solve Div1 D?

Usually after the system tests.

What is the answer for this test case?

The first letter of each name should be uppercase, while the other letters should be lowercase

while (x) {
    cout << char('A' + (x % 26));
    x /= 26;
}

¯_(ツ)_/¯

Is div 2 D supposed to be a lazy propagation segment tree after doing dfs ordering?

When will be rating updated ?

When u have coded the solution to easy problem in a contest and the computer crashes and never reloads till the end of the contest.

I guess he meant div1C.

Div1D pretest 9?

O(n) solution: 25615179

Edit: I see, you were asking about a different problem.

Centroid decomposition is overkill. Just do extremely tedious subtree DP.

Still don't understand. Could you elaborate, please?

I am the god of hacking (Problem A in VK Cup)

I had 3 successful hacks on DIV 2B

4 4
1 2
2 3
1 4
3 4

answer is NO

Tried using centroid decomposition.... Still got a TLE on pretest 9... I guess I need some optimization

Agreed.

Suspicious

You should solve problem for one vertex and solve for other vertexes using answer of a parent.

Div 2 Problem D is a nice Problem :D

Someone explain his solution please :D

Do you know how to solve it?

submit C 10 seconds before the end of the contest, waiting.. waiting...

Contest is over !! submission not there

good job servers, this website is so laggy these days

RIP RATINGS...

My brain after solving Div1-B.

How to solve Div 1 C. (unofficial) ?

That's frustrating... a lot of solutions for B in my room were wrong -- mine included -- and I couldn't hack anything at the end of the contest =|