aka.Sohieb's blog

By aka.Sohieb, history, 4 weeks ago, ,

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 Boiiii 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

• +11

 » 3 weeks ago, # |   +3 Nice I never really knew this contest existed, has it been going for many years?
•  » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   0 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 ^_^
•  » » » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   +5 Registration is now open. The round starts in less than 6 hours.
 » 3 weeks ago, # |   0 I asked a clarification about 35 minutes before end of the contest. But, unfortunately there was no response!
 » 3 weeks ago, # |   0 How to solve H and F? Also, it would be great if you guys publish an editorial for the contest!
•  » » 3 weeks ago, # ^ |   +13 for problem H all you need to get convex Hull of the n points then for every point in m you need to check if this point is in side the convex or not (their is an algorithm to do that) so this problem is stander geometric problem for problem F you can solve it using dp using two parameter the student you have to connect and a mask with length 2*e+1 to check if next or previous student is connected or not
•  » » » 8 days ago, # ^ |   0 For problem H I tried your solution and it didn't work. It keeps taking wrong answer on test 2
•  » » » » 8 days ago, # ^ |   0 this my code if you want to check it :code did you check if the point in polygon segments?
•  » » » » » 8 days ago, # ^ |   0 Yes I did. I'll check your code thanks
•  » » 3 weeks ago, # ^ |   +13 Actually, problem F appeared before in hebron-code-jam. Here is the link
•  » » » 3 weeks ago, # ^ |   +16 not only F and J also
 » 3 weeks ago, # | ← Rev. 2 →   +13 What is the case 5 of D ?
•  » » 3 weeks ago, # ^ |   +13 I also really curious about it. I hope there is not some missing place of problem statement or incorrect testdata.
•  » » 3 weeks ago, # ^ |   0 You can access the complete contest data from here
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 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 ?
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +16 D — Test case 6 is this test really right ? M = 11511 but there is only 1875 lines
•  » » » » 3 weeks ago, # ^ |   0 All test cases from 3 to 8 have N instructions instead of M
•  » » » 3 weeks ago, # ^ |   +19 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.
 » 3 weeks ago, # |   0 Test cases for D are invalid. I have used some assertion and find out that some j, k are nagative in test case 6.
•  » » 3 weeks ago, # ^ |   +8 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
 » 3 weeks ago, # |   0 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
 » 3 weeks ago, # |   0 What's is the idea behind the DP of problem F can someone explain Please
•  » » 3 weeks ago, # ^ |   -8 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)$.
•  » » » 3 weeks ago, # ^ |   0 thank you so much
•  » » » 3 weeks ago, # ^ |   0 Each soldier has at most $9$ choices, so you actually only need a $dp(n, 2^{2*e - 1} - 1)$
 » 3 weeks ago, # | ← Rev. 3 →   +5 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).
 » 3 weeks ago, # |   0 How to solve E?
•  » » 3 weeks ago, # ^ |   0 I used Knapsack to find the subset with max sum and then generated all subsets with that sum and reported the subset in which the first slememt occurs earliest