Competitions » Main CodeFu Competitons » CodeFu 2023 » Qualification Results

Qualification Results

These are the final qualification results.
The first 32 competitors will qualify for the finals.
In case of non eligible competitors or competitors who can't compete in the finals, the following competitors (from 33th position onwards) will take their place in the finals.

jakovmitrovski's solution for 500: City Connector, written in Java, submitted on 07.05.2023 13:30:51

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CityConnector {

    Node[] nodes;
    Node[] nodes2;

    Node[] merged;

    int []component;


    int[] generate(int []generator, int n, int routes) {
        long seed = ((long)generator[1] * (long)generator[0] + (long)generator[2]) % generator[3];

        int []arr = new int[routes];

        for(int i = 0; i < routes; i++) {
            arr[i] = (int)(seed % n);
            seed = ((long)generator[1] * seed + (long) generator[2]) % generator[3];
        }

        return arr;
    }

    class Node {
        int node;
        List<Node> neighbours;

        public Node(int node) {
            this.node = node;
            this.neighbours = new ArrayList<>();
        }
    }

    boolean []visited;

    List<Integer> red = new ArrayList<>();

    void dfs(int node) {
        visited[node] = true;

        for(int i=0; i<nodes[node].neighbours.size(); i++) {
            if(!visited[nodes[node].neighbours.get(i).node]) {
                dfs(nodes[node].neighbours.get(i).node);
            }
        }
        red.add(node);
    }

    void dfs2(int node, int comp) {
        visited[node] = true;

        component[node] = comp;

        for(int i=0; i<nodes2[node].neighbours.size(); i++) {
            if(!visited[nodes2[node].neighbours.get(i).node]) {
                dfs2(nodes2[node].neighbours.get(i).node, comp);
            }
        }
    }

    int path = 0;

    void pathLen(int st, int en, int depth) {
        visited[st] = true;

        if (st == en) {
            path = Math.max(path, depth);
            return;
        }

        for(int i=0; i<merged[st].neighbours.size(); i++) {
            if(!visited[merged[st].neighbours.get(i).node]) {
                pathLen(merged[st].neighbours.get(i).node, en, depth + 1);
            }
        }
    }

    boolean conn;

    void connected(int st, int en) {
        visited[st] = true;

        if (st == en) {
            conn = true;
            return;
        }

        for(int i=0; i<merged[st].neighbours.size(); i++) {
            if(!visited[merged[st].neighbours.get(i).node]) {
                connected(merged[st].neighbours.get(i).node, en);
            }
        }
    }

    public int expandCity(int stations, int routes, int[] sourceGenerator, int[] destinationGenerator) {

        int []source = generate(sourceGenerator, stations, routes);
        int []destination = generate(destinationGenerator, stations, routes);

        nodes = new Node[stations];
        nodes2 = new Node[stations];
        merged = new Node[stations];

        for (int i = 0; i < stations; i++) {
            nodes[i] = new Node(i);
            nodes2[i] = new Node(i);
        }

        for (int i = 0; i < routes; i++) {
            nodes[source[i]].neighbours.add(nodes[destination[i]]);
            nodes2[destination[i]].neighbours.add(nodes2[source[i]]);
        }

//        for (int i=0; i<routes; i++)
//            System.out.println(source[i] + " " + destination[i]);

        visited = new boolean[stations];

        for (int i = 0; i < stations; i++) {
            if(!visited[i]) {
                dfs(i);
            }
        }

        visited = new boolean[stations];

        component = new int[stations];

        int num = 0;

        Arrays.fill(component, -1);

        for(int i=red.size() - 1; i>=0; i--) {
            if (!visited[red.get(i)]) {
                dfs2(red.get(i), num);
                num++;
            }
        }

        if (num == 1) return 0;

        for(int i=0; i<num; i++) {
            merged[i] = new Node(i);
        }

        for (int i=0; i<routes; i++) {
            if (component[source[i]] != component[destination[i]]) {
                merged[component[source[i]]].neighbours.add(merged[component[destination[i]]]);
            }
        }

        int max = 0;

        conn = false;

//        for (int i=0; i<num; i++)
//            for (int j=0; j<merged[i].neighbours.size(); j++)
//                System.out.println(i + " " + merged[i].neighbours.get(j).node);


        for (int i=0; i<num; i++) {
            for (int j=0; j<num; j++) {
                if (i != j) {

                    visited = new boolean[num];

                    connected(i, j);

//                    if (i == 0 && j == 2) {
//                        System.out.println(conn);
//                    }

                    if (conn) {
                        conn = false;
                        visited = new boolean[num];
                        connected(j, i);
                        if (!conn) {
                            visited = new boolean[num];
                            pathLen(i, j, 0);
                            max = Math.max(max, path);
                            path = 0;
                        }
                    }

                    conn = false;
                }
            }
        }

        return num - max;
    }

//    public static void main(String[] args) {
//        CityConnector cityConnector = new CityConnector();
//        System.out.println(cityConnector.expandCity(4, 6, new int[]{8718,2597,52637,1179897011}, new int[]{37929,7713,29088,1117485611}));
//    }
}

Test cases result

#	Test Case input	Expected	Received	Status
1.	701, 2802, {23250,30412,7350,1371200953} , {28724,56221,57530,1945258832}	24	24	Correct
2.	5171, 26369, {23528,54377,36419,59366781 9}, {45625,40752,9561,633430904}	61	62	Wrong
3.	2213, 10393, {40294,38537,60488,50170457 9}, {47436,31838,44394,634851394}	41	43	Wrong
4.	1063, 4458, {56008,40141,59354,876476667 }, {6565,62504,54412,1297355029}	28	29	Wrong
5.	4013, 19254, {61107,37143,45879,42837879 8}, {43163,59202,26971,1512117396}	51	51	Correct
6.	4561, 22802, {60940,15614,2125,102209822 0}, {21211,19898,20735,1730809471}	60	61	Wrong
7.	2437, 11435, {60105,63870,31092,15401842 54}, {7818,32529,41858,822494267}	41	42	Wrong
8.	3989, 19918, {28645,7549,59317,724932182 }, {36762,32536,41537,812912559}	51	53	Wrong
9.	2707, 12974, {58329,17351,14934,10502457 21}, {8737,55999,30922,581692873}	44	47	Wrong
10.	3943, 18918, {40095,53283,24391,14835472 92}, {40172,62782,21402,1210137185}	54	54	Correct
11.	2999, 14968, {1355,36213,61233,948250571 }, {18419,61706,4957,1163988043}	51	51	Correct
12.	5197, 25445, {51798,12071,57003,45029924 7}, {45808,44274,65283,682554181}	69	70	Wrong
13.	1033, 4435, {34499,9919,33460,1530505374 }, {45085,15793,25850,1082321990}	27	28	Wrong
14.	43, 106, {54735,27899,27115,971162752}, {28726,970,11303,1502150875}	3	3	Correct
15.	3881, 19014, {32953,38722,32349,14892696 48}, {3794,42473,35968,1390620508}	55	56	Wrong
16.	5693, 27318, {44939,28320,8810,90131057} , {64231,26699,31450,822871068}	68	70	Wrong
17.	5051, 25757, {40149,13547,30877,43715109 6}, {55656,44321,59335,588202205}	65	67	Wrong
18.	1657, 7604, {674,37856,37537,1850892378} , {9515,25239,34477,1717147641}	36	36	Correct
19.	5081, 25910, {49918,35771,54654,17313688 05}, {22732,6654,24159,666842253}	65	67	Wrong
20.	2657, 12999, {59622,10053,31976,45843206 7}, {52208,47355,53505,1109507855}	47	47	Correct
21.	5867, 28728, {40695,33279,38722,86338678 2}, {54858,46657,23812,1774336487}	72	72	Correct
22.	2309, 11058, {27127,38073,27778,15786747 02}, {38539,39650,9681,491415520}	41	41	Correct
23.	2693, 13187, {43183,17233,43778,84287536 4}, {8328,8701,20936,1823720233}	47	47	Correct
24.	3671, 18719, {18293,17918,28775,34339101 7}, {23856,37120,21949,1548167507}	51	51	Correct
25.	307, 1124, {1440,61093,29771,793167112}, {15930,6685,42604,1961111792}	12	14	Wrong
26.	997, 4370, {41268,16889,25839,913619708} , {53187,5160,10016,1035223157}	24	24	Correct
27.	2347, 10778, {60503,27535,40918,67801576 7}, {46278,8195,2786,1894656122}	44	46	Wrong
28.	3187, 16232, {10447,60953,54225,12839989 15}, {62499,14273,51068,1633452528}	46	47	Wrong
29.	2741, 13154, {60168,59366,29494,82694775 7}, {22525,6969,40961,69979072}	43	43	Correct
30.	1583, 6958, {23243,14743,52997,666780709 }, {1619,25519,42023,168706311}	32	33	Wrong
31.	1483, 6370, {19025,36391,15028,114196879 7}, {13512,34161,29040,1016185778}	32	32	Correct
32.	5741, 28128, {30292,26040,43627,82228007 1}, {16041,56959,40391,1200911006}	70	71	Wrong
33.	1373, 6445, {3827,8971,64401,1400973878} , {56654,42362,59265,720400982}	30	31	Wrong
34.	5507, 27514, {20656,23794,31303,62742688 6}, {44658,31329,27296,282741451}	70	71	Wrong
35.	709, 2818, {17799,4085,12536,1966622666} , {4623,26618,20470,1368856049}	23	23	Correct
36.	5861, 29888, {5009,3995,25146,1857210821 }, {35026,49958,27312,1083979788}	71	72	Wrong
37.	373, 1523, {39707,12223,50475,1559723943 }, {50871,60002,4003,219848524}	14	16	Wrong
38.	4801, 23522, {30724,20085,30351,15039952 67}, {8886,3575,7263,1948963245}	64	65	Wrong
39.	3253, 15281, {44638,33548,59139,37977510 0}, {9133,209,34374,673442663}	53	55	Wrong
40.	3923, 18822, {1758,30463,34753,124644347 1}, {59728,37004,57471,396098371}	52	53	Wrong
41.	2861, 13730, {24544,62832,36183,63891516 4}, {21434,61725,40379,1816992661}	46	48	Wrong
42.	4783, 23428, {61028,54618,56988,67689951 }, {19042,44560,14319,2128352154}	60	61	Wrong
43.	1097, 4701, {51123,45015,13892,181843891 9}, {32201,29804,48337,569458898}	28	28	Correct
44.	199, 740, {14599,28054,30171,413354736}, {57142,53948,12497,1871887008}	10	11	Wrong
45.	4813, 23575, {2233,18194,29704,122185610 9}, {1440,46948,64031,1120975776}	65	67	Wrong
46.	2903, 14796, {24889,43525,1704,874093101 }, {61907,10933,11295,87302768}	46	42	Wrong
47.	349, 1344, {39054,1219,23803,684406491}, {47882,2559,49204,72225128}	13	14	Wrong
48.	4177, 21281, {31351,24142,26978,26532542 3}, {23838,16915,19642,285938954}	54	52	Wrong
49.	3677, 18731, {24723,12037,35376,32237317 6}, {47670,48694,23183,2026169411}	54	53	Wrong
50.	3593, 17238, {43568,49066,53868,20398411 48}, {44587,26333,61301,252606482}	53	48	Wrong
51.	5581, 27902, {11401,59205,11756,30869960 7}, {1995,58865,753,1468943962}	60	56	Wrong
52.	3001, 14702, {25740,3325,61469,509245679 }, {21878,50969,36488,1900808989}	44	41	Wrong
53.	739, 3230, {29481,4864,57617,979590846}, {56586,48623,41790,833960464}	21	23	Wrong
54.	4793, 24435, {21595,38906,12934,15848649 71}, {50966,21537,26126,1274308094}	64	59	Wrong
55.	677, 2895, {52577,23968,55660,2133636231 }, {21345,23670,22311,1629299813}	18	18	Correct
56.	149, 606, {59791,7737,53988,1704972313}, {39902,31958,49692,1200139206}	7	6	Wrong
57.	4027, 19712, {22500,41846,60762,20564794 06}, {26692,34111,17906,816609933}	58	58	Correct
58.	3169, 16134, {47078,53719,2008,185535053 0}, {19459,39051,13285,271564691}	46	43	Wrong
59.	103, 356, {63396,35654,25112,442839843}, {24207,34730,46620,1379428914}	4	6	Wrong
60.	1747, 8018, {64349,44426,37203,153517145 0}, {5117,34611,50839,1814123292}	34	35	Wrong
61.	4799, 23968, {60676,304,33681,447174295} , {20899,63253,22345,1781552034}	62	60	Wrong
62.	4703, 23506, {335,20865,1388,101283074}, {33977,11239,64251,1092172620}	58	49	Wrong
63.	1621, 7616, {53691,12574,61210,150081538 6}, {63875,59025,50293,1023802839}	34	33	Wrong
64.	1549, 6794, {23484,1086,12301,1050078579 }, {46763,3991,4079,46512064}	30	33	Wrong
65.	4201, 21422, {63475,1490,14322,700479830 }, {7682,35180,50132,744081989}	57	59	Wrong
66.	1153, 5181, {7324,57260,4068,267851505}, {18238,24030,18529,1575686549}	27	30	Wrong
67.	421, 1598, {53573,21470,17803,432455644} , {34772,50649,63478,727687663}	13	17	Wrong
68.	34, 33, {0,1,1,68}, {3,1,2,68}	19	19	Correct
69.	50, 49, {0,1,1,100}, {3,1,2,100}	27	27	Correct
70.	60, 59, {0,1,1,120}, {3,1,2,120}	48	48	Correct
71.	33, 32, {0,1,1,66}, {3,1,2,66}	5	5	Correct
72.	68, 67, {0,1,1,136}, {3,1,2,136}	52	52	Correct
73.	29, 28, {0,1,1,58}, {3,1,2,58}	2	2	Correct
74.	35, 34, {0,1,1,70}, {3,1,2,70}	6	6	Correct
75.	54, 53, {0,1,1,108}, {3,1,2,108}	30	30	Correct
76.	23, 22, {0,1,1,46}, {3,1,2,46}	3	3	Correct
77.	58, 57, {0,1,1,116}, {3,1,2,116}	30	30	Correct
78.	52, 51, {0,1,1,104}, {3,1,2,104}	39	39	Correct
79.	31, 30, {0,1,1,62}, {3,1,2,62}	7	7	Correct
80.	619, 2702, {46859,13703,22861,1762779236 }, {28563,33725,17042,776065396}	20	20	Correct
81.	4, 6, {8718,2597,52637,1179897011}, {379 29,7713,29088,1117485611}	1	1	Correct
82.	4, 3, {58365,4180,41167,1568895621}, {18 278,41689,14091,583269780}	2	2	Correct
83.	1583, 6958, {52488,46676,8125,536091155} , {51996,18992,32534,927171131}	33	34	Wrong
84.	809, 3458, {340,53331,4969,429850568}, { 38592,22138,23782,1391547605}	23	24	Wrong
85.	3943, 19312, {23400,9993,34284,710318413 }, {16942,32984,35474,1529568368}	53	55	Wrong
86.	1913, 9365, {29378,46395,42096,312708465 }, {56434,38076,15353,1453677070}	35	31	Wrong
87.	103, 346, {63396,35654,25112,442839843}, {24207,34730,46620,1379428914}	4	7	Wrong
88.	63, 62, {0,1,1,63}, {2,1,2,63}	13	13	Correct
89.	61, 60, {0,1,1,61}, {2,1,2,61}	2	2	Correct
90.	51, 50, {0,1,1,51}, {2,1,2,51}	8	8	Correct
91.	55, 54, {0,1,1,55}, {2,1,2,55}	5	5	Correct
92.	13, 12, {0,1,1,13}, {2,1,2,13}	2	2	Correct
93.	67, 66, {0,1,1,67}, {2,1,2,67}	2	2	Correct
94.	15, 14, {0,1,1,15}, {2,1,2,15}	5	5	Correct
95.	45, 44, {0,1,1,45}, {2,1,2,45}	8	8	Correct
96.	19, 18, {0,1,1,19}, {2,1,2,19}	2	2	Correct
97.	37, 36, {0,1,1,37}, {2,1,2,37}	2	2	Correct
98.	4253, 21256, {15523,443,24184,1417604697 }, {23330,60438,33320,1532423938}	56	56	Correct
99.	2909, 13358, {47825,13363,3911,373025094 }, {50500,19599,63305,1648971916}	49	51	Wrong
100.	349, 1378, {40367,22478,29509,1174273089 }, {28468,38137,6213,830444482}	15	15	Correct