aka.Sohieb's blog

[GYM] 2019 ICPC Malaysian National Contest
By aka.Sohieb, history, 5 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice I never really knew this contest existed, has it been going for many years?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ^_^

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Registration is now open. The round starts in less than 6 hours.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I asked a clarification about 35 minutes before end of the contest. But, unfortunately there was no response!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H and F? Also, it would be great if you guys publish an editorial for the contest!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    • 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
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For problem H I tried your solution and it didn't work. It keeps taking wrong answer on test 2

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        this my code if you want to check it :code
        did you check if the point in polygon segments?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes I did. I'll check your code thanks

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Actually, problem F appeared before in hebron-code-jam. Here is the link

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

What is the case 5 of D ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I also really curious about it. I hope there is not some missing place of problem statement or incorrect testdata.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can access the complete contest data from here

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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 ?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +16 Vote: I do not like it

      D — Test case 6 is this test really right ? M = 11511 but there is only 1875 lines

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        All test cases from 3 to 8 have N instructions instead of M

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test cases for D are invalid. I have used some assertion and find out that some j, k are nagative in test case 6.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's is the idea behind the DP of problem F can someone explain Please

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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)$$$.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply