Hi everyone!
I'm happy to invite you to join the online mirror for 2019 ICPC Malaysian National Contest (for the first time Malaysian National contest will be added to codeforces GYM).
The contest will be held on Monday, 27 May 2019.
You will have 11 problems and 5 hours to solve them.
The contest was intended for teams, but I believe it is more interesting for (Div. 1) coders if they participate individually as they will get to try all the problems.
The chief judge for the contest was asdacap. I will add the complete list for all the problem setters and which problem they created after the contest.
Thanks to Mohammad_Yasser and BENDERO for the help in preparing and testing the problems.
UPD I want to apologize for not responding to any clarification during the contest. I got an emergency 25 minutes after the contest started and I had no access to any computer for the whole day (I had to drive my father to the hospital). I'm sorry again for any contestant who asked a clarification and didn't get a response.
You can access the complete contest data from this repo, you will find the official statement, the test data and the setter solution for every problem.
The official scoreboard can be accessed from here
Nice I never really knew this contest existed, has it been going for many years?
I am not sure how long it have been going. I joined 2018 & 2019 as a contestant and asdacap (the chief judge for this year) was a contestant back in 2015. But I don't know when was the first national tbh.
I see I think I've seen like one problem from 2010 of this contest but then I thought it didn't exist anymore, so was quite surprised to see this ^_^
I believe it's just because they don't archive their work well. It wasn't an easy task to convince them to add the contest to codeforces gym.
Registration is now open. The round starts in less than 6 hours.
I asked a clarification about 35 minutes before end of the contest. But, unfortunately there was no response!
How to solve H and F? Also, it would be great if you guys publish an editorial for the contest!
For problem H I tried your solution and it didn't work. It keeps taking wrong answer on test 2
this my code if you want to check it :code
did you check if the point in polygon segments?
Yes I did. I'll check your code thanks
Actually, problem F appeared before in hebron-code-jam. Here is the link
not only F and J also
What is the case 5 of D ?
I also really curious about it. I hope there is not some missing place of problem statement or incorrect testdata.
You can access the complete contest data from here
I didn't pass the problem yet (seems like there is a index out of bound in my code), but I passed the case 5, seems like the statement is incorrect, link in this line you are comparing $$$a <= b$$$, but the statement says it should be $$$a <= b'$$$ right ?
D — Test case 6 is this test really right ? M = 11511 but there is only 1875 lines
All test cases from 3 to 8 have N instructions instead of M
In G, isn't possible to construct a case where taking the modulo during the calculations will lead to a wrong answer ? Like, endpoint A needs MOD to run and endpoint B needs 100 to run, if you take the mod the max will be B, but the real max is A.
Test cases for D are invalid. I have used some assertion and find out that some j, k are nagative in test case 6.
Test case 6 is invalid, it should be M (= 11511) queries instead of N (=1874). https://github.com/Sohieeb/2019-icpc-malaysia-national-contest/blob/master/D%20ali-the-multibillionaire/data/secret/06.in
Statement of E says: "The next T integer are the durations of the events" at Input description but it should be The next N integers
What's is the idea behind the DP of problem F can someone explain Please
Assuming that if we're traversing the id of the soldiers linearly from $$$1$$$ to $$$n$$$, for each soldier (of any line) with id $$$i$$$, we'll only match them with soldiers having id $$$j$$$ that $$$j < i$$$.
We can see that, only $$$e$$$ nearest previous soldiers should be taken into account, thus we'll need $$$2^e$$$ states to see that which of them has been matched with another soldier yet.
Then, the DP states would be of the type $$$dp(i, j, k)$$$, denoting the number of ways considering $$$i$$$ first soldiers, with the mask of $$$e$$$ rightmost soldiers (including the $$$i$$$-th one him/her-self) for the first line and the second line being $$$j$$$ and $$$k$$$, respectively.
For each bitmask, the $$$x$$$-th most significant bit will be $$$1$$$ if soldier with id $$$i - x$$$ has been matched.
For simplicity, if $$$i - x < 1$$$, the bit will have value $$$1$$$ by default.
Base case would be $$$dp(0, 2^e - 1, 2^e - 1) = 1$$$. The idea for the recurring function is quite trivial (though implementing it, at least to me, is so not).
Final answer would be the value of $$$dp(n, 2^e - 1, 2^e - 1)$$$ (since all soldiers should be matched).
Memory complexity will be $$$\mathcal{O}(n \times 2^{e+1})$$$ (or $$$\mathcal{O}(2^{e+1})$$$ if reducing the first dimension).
Time complexity will be $$$\mathcal{O}(n \times 2^{e+1} \times e^2)$$$.
Each soldier has at most $$$9$$$ choices, so you actually only need a $$$dp(n, 2^{2*e - 1} - 1)$$$
neko_nyaaaaaaaaaaaaaaaaa Can you explain a bit more? I'm unable to the transitions.
Honestly saying, this doesn't really look like a National contest to me.
Half of the problems are incredibly easy, a few harder ones are just... trivial (like H for example, you can apply the convex hull function (which I guess all serious teams should have that in their team notebooks) directly into the set of sensors).
And to top it all off, the problem statements were confusing at points. From this point, I understand the need of participants for clarification. Won't really blame the setters for not answering, but if only the statements themselves were prepared better beforehand, such trouble would be less likely to happen.
Well, that's it of my criticism. Still wish to see you guys in future contests (in better quality, I'm looking forward to).
How to solve E?
I have spend 4 hours on problem D. And later found out the DataSet was invalid. Testcase 6 & 7 is not valid. I would request you to correct it as soon as you get time. aka.Sohieb