Challenge Overview
CHALLENGE OVERVIEW
Welcome to SRM Editorial Challenge! You can now write an Editorial for the SRM and get featured on the blog, Win a Topcoder Editor T Shirt and yes Cash Prize too.
DETAILED REQUIREMENTS
In this challenge you are required to write an editorial for the SRM 711 problem TreeMovingDiv2 . Your submission should adhere to the submission guidelines mentioned below.
1)
3)
4)
PRIZES
---Topcoder Editor T-shirt. If your editorial is published
---Additional cash prizes, once your count of published editorials reaches 10. Please refer below.
---First 10 editorials published, a crash prize of $50.
---Next 15 editorials published, a crash prize of $100.
Once your count of published editorials reaches 25 we will reset the count to 0.
DETAILED REQUIREMENTS
In this challenge you are required to write an editorial for the SRM 711 problem TreeMovingDiv2 . Your submission should adhere to the submission guidelines mentioned below.
Problem Statement
You are given m trees. The trees are labeled T(0) through T(m-1). Each tree contains n vertices labeled 0 through n-1. A cyclic rotation of edges is the following procedure:
- In each tree you choose one of its edges. Let e(i) be the edge chosen in the tree T(i).
You remove the chosen edge from the tree, producing a graph with n vertices and only n-2 edges.
For each valid i, you add the edge e(i) to the tree T(i+1). Also, you add the edge e(m-1) to the tree T(0). For example, if e(0) was an edge that connected vertices 4 and 7 in T(0), the graph T(1) will now get a new edge that connects its vertices 4 and 7.
The procedure was successful if and only if each T(i) is a tree again.
X[0] = c[i]
for k = 1 to n-2:
X[k] = (a[i] * X[k - 1] + b[i]) modulo 1,000,000,007
and then we use that sequence to generate the edges of the tree:
for j = 0 to n-2:
u[j] = (roots[i] + j + 1) modulo n
v[j] = (roots[i] + (X[j] modulo (j + 1))) modulo n
add the edge between u[j] and v[j] to the tree T(i)
Limits
Time limit (s):
2.000
Memory limit (MB):
512
Notes
- The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of the allowed size within the given limits.
Constraints
- n will be between 2 and 50, inclusive.
- roots will contain between 2 and 50 elements, inclusive.
- a and roots will contain the same number of elements.
- b and roots will contain the same number of elements.
- c and roots will contain the same number of elements.
- Each element of roots will be between 0 and n - 1, inclusive.
- Each element of a will be between 1 and 1,000,000,006, inclusive.
- Each element of b will be between 0 and 1,000,000,006, inclusive.
- Each element of c will be between 0 and 1,000,000,006, inclusive.
Examples
0)
3
{0, 2}
{1, 2}
{1, 0}
{3, 5}
Returns: 2
There are two trees, each of them contains 3 vertices. The tree T(0) is generated as follows:
- X[0] = c[0] = 3
X[1] = (a[0] * X[0] + b[0]) modulo 1,000,000,007 = 4
u[0] = (roots[0] + 1) modulo n = 1
v[0] = (roots[0] + (X[0] modulo 1)) modulo n = 0
u[1] = (roots[0] + 2) modulo n = 2
v[1] = (roots[0] + (X[1] modulo 2)) modulo n = 0
The tree T(1) contains the edges 0-2 and 1-2.
There are two ways to do a successful cyclic rotation of edges: we can either choose the edge 0-2 in each tree, or we can choose the edge 0-1 in T(0) and the edge 1-2 in T(1).1)
3
{0, 0, 1}
{6, 1, 3}
{6, 5, 5}
{2, 5, 9}
Returns: 2
T(0) contains edges 1-0 and 2-0.
T(1) contains edges 1-0 and 2-0.
T(2) contains edges 2-1 and 0-1.
2)
5
{0, 1, 1, 1, 2}
{7, 4, 7, 9, 2}
{8, 3, 9, 5, 3}
{6, 0, 1, 5, 9}
Returns: 22
3)
2
{1, 0, 0}
{122064284, 9662111, 120616497}
{20137061, 408976122, 494878172}
{242061783, 603049107, 805670429}
Returns: 1
Watch out for integer overflow when generating the temporary sequence X.
4)
15
{11, 3, 13, 5, 0, 3, 0, 8, 9, 4, 9, 7, 5, 12, 12, 11, 12, 2, 6, 5, 13, 13, 11, 8, 14, 9, 2, 0, 3, 11, 10, 12, 10, 11, 11, 12, 13, 7, 12, 11, 2, 14, 8, 3, 6, 6, 4, 13, 5, 8}
{983816220, 620877501, 728957664, 719453482, 891241034, 959047323, 459235325, 188837384, 749336264, 40650017, 404049008, 121578182, 640967952, 444329307, 181115164, 697849277, 12923013, 711014676, 308063158, 403714366, 341206103, 674610097, 743172147, 27978413, 95548595, 93823839, 844476902, 863583697, 568069127, 618319911, 659846531, 341309147, 735202433, 531047579, 967335611, 311192666, 753647731, 36420180, 609571991, 208600401, 915548304, 926479460, 672275772, 545217041, 864561330, 32472050, 852336473, 144521601, 383750815, 616511468}
{715457951, 308091233, 686233659, 523365634, 260145657, 96581518, 754153775, 622990522, 78662953, 689973864, 609423534, 534351235, 56822117, 899080526, 236413795, 747521954, 249656307, 790813221, 238598034, 203856426, 170015231, 791645278, 991710627, 747864180, 331241135, 416320805, 820623220, 811261319, 154661650, 914880513, 270905767, 954448019, 261442212, 954262444, 293791600, 493225233, 67542211, 911866345, 567575019, 95716070, 410883122, 337767450, 375732581, 616839717, 416849487, 140196829, 200763187, 51759408, 992789421, 882490836}
{650915191, 363659051, 226659197, 706291662, 748630395, 163284394, 663006670, 2890697, 639793395, 728890798, 570088430, 967259303, 101778889, 249725396, 968816738, 276471315, 905010209, 467925249, 798793109, 857289233, 494026470, 476417587, 98570430, 596160845, 211373787, 188742439, 364805067, 757845257, 317224756, 74104796, 455729968, 78933290, 769895010, 476555278, 45379277, 957039727, 395817921, 447349376, 629724490, 287334171, 227424105, 603337884, 467060652, 254067677, 237332026, 976429932, 93075762, 960441433, 132935737, 671265490}
Returns: 755767349
Watch out for integer overflow while calculating the answer.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
PRIZES
---Topcoder Editor T-shirt. If your editorial is published
---Additional cash prizes, once your count of published editorials reaches 10. Please refer below.
---First 10 editorials published, a crash prize of $50.
---Next 15 editorials published, a crash prize of $100.
Once your count of published editorials reaches 25 we will reset the count to 0.
Final Submission Guidelines
---The submission should be a detailed explanation of the solution so that even the new members are able to understand.---You should also mention the alternative solutions if there are any.
---You have to make yourself available to reply to queries and suggestions in the discussion forum of the SRM.
---The editorial should contain the code for the solution.
---You may attach links to the algorithms explanation and any other relevant resources to make your editorial more understandable.
---Relevant pictures and illustrations are highly recommended.
---You can refer to the following editorials to take inspiration from : https://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
---The editorial should be submitted in a text, doc, docx or odt format.