### r3gz3n's blog

By r3gz3n, history, 3 years ago, ,

Hi everyone,

Are you preparing for ACM International Collegiate Programming Contest (ICPC) ?

As we all know that ICPC is about to start. I am glad to invite all the college students to take part in HackerEarth Collegiate Cup on Sep 03, 10:00 AM IST. It will add up in the practice for ACM-ICPC. This is a team contest where teams must consist of exactly 3 members and all members must be enrolled in a degree program at the same institution.

The contest will have 4 rounds:

A. Qualifier Round: It will be an online contest. All the teams who solve at least one problem will qualify to the next round. It will be a 24 hours contest which will have 3 problems.

B. First Elimination: It will be an online contest of 3 hours having 5 problems. Top 3 teams from each institution who have solved at least one problem will move to the next round.

C. Second Elimination: It will be an online contest of 5 hours having 10 problems. Top 15 Indian teams each from different college will qualify for the final onsite round and top 15 Global teams each from different college will be eligible for prizes in the online Mirror round.

D1. Final Round (Onsite): This will be an onsite round in which the 15 Indian teams selected from second elimination will participate. It will be a 5 hours contest having 12 problems.

D2. Mirror Final Round (Online): This will be an online round of 5 hours, and having the same 12 problems as of the Final Onsite round. Anyone can participate in this but only the top 15 Global teams who qualified the second elimination will be eligible for prizes.

Schedule:

• Qualifier Round: 3rd September, 2016 10am IST

• First Elimination: 17th September, 2016 10am IST

• Second Elimination: 8th October, 2016 10am IST

• Final Onsite Round / Final Mirror Round: To be announced

Prizes:

• First Prize: i Pad Mini 2 (per member)
Second Prize: Das Keyboard (per member)
Third Prizes: Asus Zenwatch 2 (per member)

• Winning Team of the onsite round shall be reimbursed an amount not greater than INR 45K per member against the total travel expenses, if they will get selected for the ICPC World Finals.

• Winning team of the top 15 Global teams in the Mirror Round will get $250 Amazon Gift Voucher per team member. Reimbursement: • Top Indian 15 teams selected for the onsite round will be reimbursed an amount not greater than INR 10K per member against the total travel expenses. • The said amount shall be reimbursed against submission of valid proof (in original) E.g. Train & Bus Tickets. Happy Coding :) EDIT: The First Elimination Round has been postponed to September 18, 2016, 5:00 PM IST. All qualified teams have been informed through mails. • +62  » 3 years ago, # | +5 Auto comment: topic has been updated by r3gz3n (previous revision, new revision, compare).  » 3 years ago, # | +5 Auto comment: topic has been updated by r3gz3n (previous revision, new revision, compare).  » 3 years ago, # | +5 Two questions: (a) When will the other rounds take place? I can't seem to find a schedule. (b) A couple of my contestants are not ICPC-eligible, but are still students. Are they able to compete in this contest? Thanks. •  » » 3 years ago, # ^ | +11 Thanks for pointing it out. I have added the schedule of the contest. Yes, they can participate in the contest.  » 3 years ago, # | ← Rev. 2 → +11 Will it be allowed to use three computers (one per person) on all stages? Will onsite and online finalists compete in the same contest (fighting for the same prizes)?Do I understand correctly that the very first round will be extremely easy to pass but it will last only two hours? So is its purpose to fail those who can't be online then? •  » » 3 years ago, # ^ | 0 This is a Practice contest for ICPC so ,except for the onsite round, contestants are allowed to use 3 computers. No, onsite and mirror finalist will compete in different contests and the prizes for both the contests will be different. Onsite Round will be Offline and contestants will not be allowed to access Internet. As mirror round contestants have access to Internet and 3 computers, the prizes for the mirror round are less than that of Onsite Round. Yes. First round is very easy to pass but teams have to solve at-least one problem in the period of 2 hours. •  » » » 3 years ago, # ^ | +21 3.Why would you want to check who can be online during some period of two hours? Wouldn't e.g. 24 hours be better? •  » » » 3 years ago, # ^ | +3 Also, why the same institution? You may want to read the discussion under the blog about the Codechef's Snackdown (link). •  » » » » 3 years ago, # ^ | +18 The reason for 2 hours contest was to eliminate cheating cases. But Qualifier the first and extremely easy round so it doesn't matter much. So we are considering your point and planning to increase the contest duration to 24 hours.As I mentioned earlier, this contest is a practice contest for ICPC. So we are following ICPC rules. That's why same institution.  » 3 years ago, # | +5 Auto comment: topic has been updated by r3gz3n (previous revision, new revision, compare).  » 3 years ago, # | ← Rev. 2 → -9 Are school teams allowed?I think school team abides by the rule "All members in a team must be enrolled in a degree program at the same institution.", and there should be no reason to exclude them otherwise, so are they allowed? •  » » 3 years ago, # ^ | 0 As you know ICPC is only for college teams, so, as per the ICPC rules, only college teams are allowed to participate and we would stick to their rules as its a practice contest for the same •  » » » 3 years ago, # ^ | +22 This rule always makes me angry. Why don't allow high schoolers to compete with colleges? They will be collage students one day, too. Consider allowing school teams, please. •  » » » » 3 years ago, # ^ | +21 We will be allowing school teams but they won't be eligible for any prizes. Rules will be updated soon. •  » » » » » 3 years ago, # ^ | 0 Will school teams be considered in 15 different teams that go onsite? •  » » » » » » 3 years ago, # ^ | +6 No. •  » » » » » 3 years ago, # ^ | 0 Why they shouldn't be eligible for prizes? If anything, school teams are at a disadvantage to college teams, because they are younger and have less experience.  » 3 years ago, # | 0 Auto comment: topic has been updated by r3gz3n (previous revision, new revision, compare).  » 3 years ago, # | +3 Hi Everyone,2 days to go. We have announced the prizes. See you on the leader-board.  » 3 years ago, # | +4 Hi Everyone,The Qualifier round is live.  » 3 years ago, # | ← Rev. 4 → +3 Why is total time calculated incorrectly for some teams? Eg: team Wont.Be.In.The.Finals I guess total time should be lot high with so much penalties  » 3 years ago, # | ← Rev. 2 → 0 Hello! Can I delete my team? I created it accidentally and I want connect to existing team of students from my university. I didn't make any submission and I am only one member of this team. •  » » 3 years ago, # ^ | +16 Yes. Please forward me the team name you want to delete and also the team name you want to connect to. •  » » » 3 years ago, # ^ | -7 Great. Now, me and my friends will be both disqualified. Thanks. •  » » » » 3 years ago, # ^ | +3 Your team won't be disqualified if they have solved atleast one problem. •  » » » » » 3 years ago, # ^ | ← Rev. 2 → +3 But you didn't add me to their team. And didn't delete my own. I check it just few minutes before contest ends.  » 3 years ago, # | +3 Can you provide solution for 3d one ? Thanks ! •  » » 3 years ago, # ^ | +15 I used Meet in the middle + Trie.since n <= 40, Split the problem into two (each n <= 20 ), Solve them individually and then merge them. You can apply brute force( all the subsets of size <= k ) for n <= 20 and Merging can be done using TRIE.Trie part is similar problem to this "Given an array of integers, we have to find two elements whose XOR is maximum". Note: To get AC , you will need few optimisations.My AC Code.  » 3 years ago, # | +6 Am I the only one who doesn't see the First Elimination contest? What may cause this? •  » » 3 years ago, # ^ | 0 We will announce the results tomorrow and send invitation to all the teams who are qualified. •  » » » 3 years ago, # ^ | +2 Have you sent the invitation yet? We havent receieved it and our team had 2solved problems  » 3 years ago, # | ← Rev. 2 → 0 your timings clash with google APAC round C 2017.. please shift your schedule.. i guess most of the qualified teams will not miss APAC! thank you.. :) i am sorry.. apac is on 18.. forgive me :)  » 3 years ago, # | ← Rev. 2 → 0 please update about tomorrow's contest? who can participate and who cannot? we cannot see any invitations yet! •  » » 3 years ago, # ^ | 0 We have sent the mails to the teams who are qualified.  » 3 years ago, # | +11 I am the team leader of my team and I am getting options of creating team or joining team. Do I have to create team again and invite my teammates again?  » 3 years ago, # | +6 Cant login...Shows just two options of creating or joining a team...used the link in the mail also....Can someone please help?? •  » » 3 years ago, # ^ | +9 I created the same team few hours back and currently the website is just not loading....  » 3 years ago, # | +3 How to solve C? I tried with hashing + binary search but my implementation gave WA on all :| •  » » 3 years ago, # ^ | +3 I did the same and got ac. Maybe you are forgetting the case when the same element is swapped two times •  » » 3 years ago, # ^ | +9 I solved it using "Suffix Arrays".Let the two strings be S and T. For each query, let the two substrings be S1 of S and T1 of T.We need to calculate quickly for each query the "Longest common Prefix(LCP) of S1 and T1" as well as the "Longest common Suffix(LCS) of S1 and T1".We can do this using Suffix arrays and LCP array. We can find LCP of two Suffixes in O(1) constructing RMQ sparse table on LCP array.For LCP , make a string = concatenate S and T using any special character in between and just locate where is S1 and T1 in the lcp array and find LCP of those two suffixes in O(1).For LCS , just make another string = "reverse(S) + "$" + reverse(T)", and do the same as LCP.Now why do we need this?There are 3 cases to consider. K = 0 | In this case the LCP(S1,T1) = length(S1) since both must be equal , if they are not then we can't make S1 and T1 same. K = 1 | In this case we will calculate LCP(S1,T1) and LCS(S1,T1) using our Suffix array Pre-Computation. Now Think like this, traverse LCP(S1,T1) from left and traverse LCS(S1,T1) from right. We can only make both S1 , T1 equal using only 1 adjacent swaps , if after swapping 2 characters( which are left after traversing both ways) we get equal strings. K = 2 | This case is a little bit tricky. We have two sub-cases. Think like this, Traverse LCP(S1,T1) from left and traverse LCS(S1,T1) from right. now we are left with only 3 characters in between. ( 2 character case is done when K was 1). So just check if you can make S1 = T1 by doing 2 swaps in this 3 length string. If there are more than 3 characters in between then how to do? let the position where first character is different while traversing from left side be id_l. let the position where first character is different while traversing from right side be id_r.Now we can do at most 2 swaps. 1st swap can be done on (id_l,id_l+1) and the second swap can be done on (id_r-1,id_r). Also we have to check that the substring from [id_l+2,id_r-2] are equal in both S1 and T1.We can check this using same concept of LCP array discussed earlier( when k was 0 ). If either of this fails then ans = "NO".If in a query | k = 1, check from k = 0 -> 1. If k = 2, then start checking from k = 0 — > 1 — > 2. My AC Code using same Algorithm.If anything is unclear, feel free to ask!
•  » » 3 years ago, # ^ |   +6 Hi, I was the setter of problem C. Intended solution was the idea you tried, so perhaps you missed something (see alei comment). The easiest way was to use hashing + binary search to find LCP. Suffix Array was also possible of course, but seems harder to implement, at least from scratch in my opinion. My solution is uploaded in Author solution section on HackerEarth. I hope you enjoyed the problem :)
•  » » » 3 years ago, # ^ |   0 Can you please explain your solution. Also how is the subtring_hash calculated. I read this blog , and here they have also taken Modulus with a prime. Also , what is the criteria for choosing prime and modulo ?
 » 3 years ago, # | ← Rev. 2 →   +20 Hi, how to solve D (link)? The editorial appears to be empty =(UPD: The editorial is present now.
•  » » 3 years ago, # ^ |   0 I can't get the formula of f(wi,y)? Where can I find the proof?
 » 3 years ago, # | ← Rev. 2 →   +5 I am not able to see my team on the leaderboard. I am also unable to find the individual submissions by my teammates anywhere.Any help in this regard will be appreciated.EDIT: Submissions made by my teammates are not shown for our team. Instead my teammates got auto-generated, single person, teams assigned to them and their submissions have been considered as part of those.
•  » » 3 years ago, # ^ |   0 Did you had any submission from Team Leader account? I also experienced this same thing in the qualifying round and today too. Both times, i was able to see the team on leader-board only after there was a submission from Team Leader account.
•  » » 3 years ago, # ^ |   +5 Same thing happened to my team too. Team members have got autogenerated,single person teams assigned.
 » 3 years ago, # |   +3 Would there be some info about wildcard? Who can participate (seems that everybody)? Which rules for qualification to the next stage?
•  » » 3 years ago, # ^ |   0 Anyone can participate except for those who are qualified for the second elimination.
•  » » 3 years ago, # ^ |   0 http://codeforces.com/blog/entry/47449 Here is a post regarding the Wild card which has all the rules of the round.
 » 3 years ago, # |   0 Can we get a list of teams who qualified the first elimination round??
•  » » 3 years ago, # ^ |   +3 I will update it today.
•  » » 3 years ago, # ^ |   0 Here are the results of the first elimination round: http://codeforces.com/blog/entry/47455