ACM-ICPC 2013 Jakarta – Problems and Analysis Algorithm, Event, Programming Add comments Nov 082013 H. Horrible Quiz Author: Irvan Jahja (link to problem H) This write-up WILL BE written by Risan. However, he’s quite busy at this moment, so the write-up for this problem is delayed. Let’s see who will be the first to have a free time to finish this write-up, me or Risan. 1st page A. Number Assignment B. Network Packet Ordering C. The Busiest City D. Power Plant E. Railroad F. Pasti Pas! G. Emergency Handling H. Horrible Quiz I. Coins on a Ring J. Alien Abduction Again My Note Questionnaire Feedback Others Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 12 Responses to “ACM-ICPC 2013 Jakarta – Problems and Analysis” iqbal says: November 8, 2013 at 10:06 am are you sure there isn’t mod operation ? and this : j = j + 1, why it isn’t j = j-1 ? Reply suhendry says: November 8, 2013 at 1:23 pm Ah, you’re right, it should be j =j – 1 (updated). MOD operation is not needed, What we really need is whether a two substrings have a same hash value or not, not the hash value itself. There are only addition and multiplication operators, so overflowing the result doesn’t matter. Reply iqbal says: November 8, 2013 at 10:17 am ^that comment above is for pasti pas Reply baguzzzaji says: November 22, 2013 at 7:07 am Halo Mr. Suhendry. Saya ingin sekali bisa berkompetisi di ACM ICPC. Saya Mahasiswa tingkat 2 di salah satu perguruan tinggi di bandung. Tapi skill koding saya tidak terlalu bagus. algoritma sorting saja masih bingung. Gimana ya kiat nya untuk belajar algoritma yg baik dan benar agar bisa nanti suatu saat ke ACM ICPC? Reply Izhari Ishak Aksa says: January 9, 2014 at 5:10 pm How to determine which prime number should be used? I tried some prime numbers and the result is not as expected. Reply suhendry says: January 9, 2014 at 5:16 pm (Problem F). Just use large prime number (larger is better, its chance to collide is smaller). I used 1000003 and it’s fine. Reply Izhari Ishak Aksa says: January 9, 2014 at 5:32 pm I have implemented it and submitted on Live Archive, but got WA 😀 Is there something wrong with my implementation? Could you please check it? http://pastebin.com/ECJX9yEa Reply suhendry says: January 9, 2014 at 10:56 pm I didn’t read your code, but it failed the first sample input: PASTIPAS. Reply Izhari Ishak Aksa says: January 10, 2014 at 2:21 pm Yes and it works if I do MOD operation, but still WA on Live Archive. Does your solution with above algorithm still work on LA? Maybe you/others have added more test cases to break that hash function? Or my implementation wrong? Reply suhendry says: January 11, 2014 at 12:35 pm I’m the one who send the data to LA and I’m pretty sure LA’s admin was quite busy to do any changes on the dataset. BTW, I’ve just noticed an error in F’s pseudocode. There is one line which is wrong. Try to figure that out! 🙂 hint: pay attention to the rolling hash (when you do the multiplication with prime number); you might want to check other resources on rolling hash. Reply Izhari Ishak Aksa says: January 9, 2014 at 5:12 pm ^ problem F Pasti Pas! Reply Sadia Atique says: November 5, 2014 at 11:41 am Problem H can be solved by Dynamic Programming,here I find two states,one is index of the current question,another is wrong answers used/left so far, and then minimize the answer. But this solution does not work,though sample test case gives correct output. I saw another boolean state in some accepted codes in HUST, which tries both minimizing and maximizing. Can you please explain why another state is needed here? Reply Leave a Reply Cancel reply Your Comment You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> Name (required) E-mail (required) URI Notify me of follow-up comments by email. Notify me of new posts by email.