INOI 2020 was far easier than last year!I think the cutoff is going to be 200 for class 12! But sadly enough my computer hanged today and I spotted the constraint 1<=k<=3, 20 mins after wasting time on a 2D dp solution involving dp! Hence I endend up getting only 132!! I should have attempted the tiling problem first!
Please sort it and add the totalling function
It’s not mine
How many people get selected from 12th?
I guess 200 or 135 will be the cutoff for all classes
Test Data and Question is available here: https://exam.codechef.com/download/INOI2020/LiveData.zip
What is the password?
Apparently for the first question, if you try to make 2 DFS calls for each component of the graph - 1 to determine which node will serve as the root and 1 to calculate strength of that component with respect to this node, the program gives you a TLE in 2 cases of subtask 2.
What’s the right logic then ?
Root of the tree can be determined by the minimum/maximum value node according to the parity of the number of vertices of the tree.
My approach was to run DFS on the graph to seperate its connected components out. Then, on each connected component run a DFS to determine its strength.
strength_even = strength of even sized connected components
strength_odd = strength of odd sized connected components
Print strength_even and strength_odd
This gave AC(100 pts) on pretests. Hope it passes system tests.
cutoff will probably be 200 for classes 10,11 and 12 and 132/115 for classes 9 and below
No, it didn’t give TLE for my code. I ran 2DFS only. Maybe your code was long.
For the first problem. I first took the inputs of all the connections, simultaneously making a structure I defined “group” which had variables for total employees, minimum_val employee, and max_val employee. As taking the inputs, I would merge 2 groups if both the employees already belonged to some group. After this, if the number of employees was even, I would start with the minimum employee, I would push it to a queue, followed by all it’s subordinates(If I know it’s on the top, all others are its subordinates, and with this same logic, I can know the manager of each employee, so I can know which employees are the subordinates and which is the manager. Then, I would run a BFS, and for each level i would multiply the total employees on that level with the value 1 for lev. 1, 2 for lev. 2 and so on.
this gave me AC for the first sub-task, AC for the first, second and last test cases for the second sub-task. One thing I noticed was that except for the second test case of the second sub-task, all the ACs I got were where there were only either odd or even groups. I didn’t even get TLE for the other cases, WA. I know this is pretty big, but could someone tell me what I did wrong here?
does that make a difference?
That can’t possible be true. I literally spent over an hour trying to optimise my code which did exactly that:
For each component, 1 DFS to find root node and type of department. 1 DFS to find strength with respect to this root nodes.
Net result = 2 DFS for each component of the graph.
I even went on to replace all my array indices with pointers, use faster I/O in C++ and use global variables to prevent re-declaration time.
Bottom line is - My code was optimised to the absolute limits and using the same logic as you say you have used, it gave a TLE on cases 5 and 6 of the second subtask.
What’s even funnier is that when I ran the code on my local machine and timed it using the Linux time command, sub tasks 5 and 6 ran in around 1.7-1.8 seconds on an average.
@shlok_1933, I think you said your code too gave TLE in 2 subtasks right? Did you use the same logic?
I feel terrible because if I could have used that one hour on the second question, I too could have got a 200. I’ve seen the second question before too, I think something similar came in INMO 2018 if I’m not wrong ?
@aryansanghi How did you get your program to AC in the first question ? There has to have been some difference in logic right ?
I was also for some reason getting a TLE in the first problem on test cases 5 and 6. I was running a simple DFS and a BFS. The code was pretty short and I wasted a lot of time on optimizing my code. I changed and removed every redundant thing I could find. What really surprised me was the uncertainty of the issue. I submitted my code once, got a TLE on 4 test cases, literally submitted the same exact code and got a TLE on only 2 test cases (and AC on the rest) and this was pretty random-ish. I met other people who used 2 DFS and 1 BFS and for some reason their code passed the test cases. What can be the issue? My computer’s internet went down for a while (although the staff ficed it in no time) but can this be due to that? idk I wasted a lot of time on the first problem trying to figure it out and … idk I am just sad and disappointed.
Send code please
I first did the graph one with dfs and as I had completed the paper in half time I even did with bfs. I got didn’t get tle even once…its highly likely there is some line in your code like redeclaring arrays or something like that cz of which you got tle.
and also logic is same run bfs/dfs two time once to calculate roots and then again to calculate sum of levels.
I did with bfs twice aswell.