ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1779. The Great Team

Who can give me some hints?
Posted by adrian 9 Oct 2010 18:38
I thought it for a long time,but I still do not know how to do it.
Hint
Posted by vgu 9 Oct 2010 20:36
1) If we know the degree of the vertices, we can determine: is such graph exist.
2) Write a full search. You will quickly find an answer. You can sent this code and get AC or look at the answer and found a pattern.
Re: Hint
Posted by svr 9 Oct 2010 22:11
1)Havel-Hakimi algorithm
2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0
realizable for each n
P.S. In timus there is a problem about full search:
monkey aplly full search on keyboard. When it create theorem.

Edited by author 09.10.2010 22:30
Re: Hint
Posted by luckysundog 23 Oct 2011 01:21
svr, your hypothesis is true. It's obvious if we draw the adjacency matrix of these graphs (for even N):

N = 4:
0 0 0 1
0 0 1 1
0 1 0 0
1 1 0 0

N = 6:
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
0 0 1 0 0 0
0 1 1 0 0 0
1 1 1 0 0 0

N = 8:
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0