Today I participated in the coding competition Codegoda hosted by Agoda. I'm not going to talk about their weird rules and coding environment. I just want to share some of my experiences regarding the problemset. In a word, worst experience ever. I just want to mention some things here that seem annoying to me and make me feel it was a waste of time participating in the contest.
Most of the problems require no more than 30 seconds of thinking to get the idea. The problemset was not standard. Expected more quality problems in such a big competition. In the problem of probability, it was mentioned to print up to 5 digits after the decimal point. What does it mean actually? Is it exactly 5 digits? Or at most 5 digits? If it is, then printing more than 5 digits should give wrong answer, right? I printed 10 digits and it passed 3 tests and gave wrong in the 4-th test case. I was thinking my idea/solution is wrong. Then wrote the bruteforce solution and wasted almost 1 hour finding out the actual problem. Printing 5 digits after the decimal point got passed all the public tests. Why it didn't give wrong answer verdict in the first 3 cases? Isn't it weird? They could clearly mention that we have to print exactly 5 digits.
The problem of checking whether two companies are from the same group or not is a very common problem of DSU/DFS. Why such a common well-known problem in such a contest? Are they taking speed test?
The problem of digit mapping was so annoying as we cannot copy/paste into the contest editor. It requires writing some similar types of lines multiple times. All you have to type so fast.
The problem of finding the best hotel within a budget range had a confusing statement. It was mentioned nowhere what should be printed if there is no hotel in the budget range given in each query. If it is guaranteed that at least one hotel exists in the budget range, then why it was not mentioned in the statement? Is there any issue in the dataset of this problem or any corner case? My fresh solution didn't pass after 3rd test -_-
I tried these 4 problems and found none of them interesting. Didn't try the other two problems. The problems are so poor compared to their magnificent advertisement. Overall it feels like a waste of time.
UPD: I contacted them about their duplicate problemset. Here is their funny reply. They don't think it unfair xD 
Okay, for problem 6, I think test cases had something wrong with it. For once I assert checked that "lower bound of the budget >= 1", and it failed. I believe model solution might have had something wrong as well. How can I contact the organizers ?
This test case exists? I wasted like 1+ hours to debug and wonder where did my segment tree gone wrong
Okay I complained about this, and got an email saying :
"Hi,
Hope you are doing well.
Most of the participants have solved this problem statement and we haven't received any such complaints from them but we will still look into the matter and in case of any discrepancy, the necessary action would be taken.
Thanks, Team Unstop (Formerly Dare2Compete)"
Idk, i see alot of people here had the same problem. It would be great, if people who had issue with this problem email "[email protected]" and complain about it to let them know. That way they would see that a lot of people had issues with this problem.
I'm curious if anyone actually got all 5 tests correct for that problem. I can confirm that I added the assert and found that the lowerbound was invalid, too.
Congrats on third place!
Thanks a lot!
Done! I sent in an email as well. It's strange that they could write "most of the participants have solved this problem statement" when everyone here, including orange and red coders, is facing the same issue...
I'm trying to reach them out as well and they responded with this
Thanks for sharing. In my email I described my rough approach in using segment tree, and they initially brushed aside my email saying that I needed to implement the tie-breaking rule to pick the lowest priced hotel. Of course I did implement, I just didn't thought that is an obvious part of the solution that doesn't need sharing. Were they expecting me to share the entire code with them??
It seems that enough of us gave feedback that they finally look into it... I hope they rejudge with all submissions because my first submission was correct and subsequently I tried funny ways of altering my code to debug until time up. So my last run was a debugging run...
But they have lost all credibility with me. Especially after they first lied that many coders got the problem. shrugs
Worst contest possible! Why the hell did they host a contest on a platform like that? Just do it on ANY regular online judges with original problemset, then you don't need to put all the useless security shits !
Any idea as to how to do the 4th or the 5th one?
For the digit mapping problem, identify unique letters like 'z' for 0 and use that to deduce the count of each digit. After adjusting for the first round of unique letters, you get new unique letters for the remaining digits.
For the merge and break question, the question can be tackled in two parts. You need to break all arrays into contiguous subarrays of strictly increasing sequences. To do this with minimum cost, each array you should avoid incurring cost for the longest continguous subarray. You cna achieve this by chipping off one subarray at a time, either form left end or right end, until you are left with the longest subarray. Then for the merging part, form a heap with all the subarray lengths. Pop the lowest 2 lengths, merge them and add back to the heap, and repeat.
Can you please elaborate how to solve digit mapping problem. Because only zero, six and two contains unique letters which are z, x and w respectively. In all other strings characters are repeated.
u is also unique to 4. After you adjust down the count for o to take into account 0, 2 and 4 (which you know), o becomes unique for 1. Extrapolate this example (o was initially not unique but became unique after adjustment). With successive adjustments and elimination, new digits become uniquely identifiable. It's quite tedious but you can eventually work out the right sequence to consider.
Here is what I thought would work but didn't pass more than one test-case, Can you explain why was it wrong ??
My approach was very simple : Find the first occurrence of smallest decimal digit present in the string, then remove chars from the string, required to make one instance of this decimal digit. This decimal number will be my most significant digit, thus I will append this digit once in my ans string.
Now from the leftover string, I will try to form as many zeroes as possible. then append this decimal '0' in my ans string as many times as possible.
Now finally, I will iterate from one to nine and try to form as many digits as possible for each one of them in the ascending order and keep appending these digits as the end of my ans string
For Example : str = rzerotwooneonezerofo
Approach : I will first find the smallest possible digit that can be formed (except '0') which is '1' Then I will try to form as many '0's as possible, and finally in increasing order from '1' to '9' form as many instances as possible.
Expected Output : '10012'
"ninefourone"
Since you go from 1, you pick 2 'o's, 2 'n's and 2 'e's and form 11. Whereas, you ought to have 1 '1'. If you form 2 1s, you are left stranded with "nifur" which cannot go further.
how to solve hotel problem ?
I use segment tree. Since prices for each hotel are different, I store a hotel inside the array which the index is the price
So for each query, I just do range maximum query within the bound of the given budget (since now the budget is the index of the range)
*note : my solution only pass 3 test cases
I felt the same. I spent some time trying to pad the answer to exactly 5 decimal places, was annoyed by having to type the same block of code multiple times for the digit mapping question.
The hotel one was the worst. I was pretty sure the $$$O(n \log n)$$$ solution should pass, but it also didnt pass after the 3rd test. I thought it was a Python TLE problem but I noticed you use C++ as your main language, so I think it's just bad dataset? FYI I used a segment tree, and yes I had to code a segment tree query function from scratch because I can't copy and paste my template code. -_- The worst part is no time limits given, so I can't figure out if I got WA or TLE due to python.
Oh wells...!
Can you explain how you solved the cashback(Happy Tourism) problem?
Let $$$x_n$$$ be the probability of not happy when you are currently at $$$n$$$. (You want $$$x_0$$$). The recurrence relation is $$$x_n = \frac{x_{n+1}+x_{n+1}+...+x_{n+maxcash}}{maxcash}$$$. Set up the boundary cases $$$x_j = 1$$$ if $$$j \in [M,H)$$$ and $$$x_j = 0$$$ if $$$j \ge H$$$.) Then compute $$$x_n$$$ as $$$n$$$ decreases and you can do it in linear time by maintaining the running sum $$$x_{n+1}+x_{n+1}+...+x_{n+maxcash}$$$ and updating it in $$$O(1)$$$ each time you shift down.
In problem 6 (Best-rated hotel), I've tried with
segment treeandsqrt block decomposition. But guess what? Both of my solutions passed only the first 3 test cases though I'm pretty sure about my solutions.So, I firmly believe there are some issues with the dataset. Wasted almost 1.5 hrs on this problem.
P.S: I used C++.
Can someone tell me how to solve the lock-down sequences problem?
Problem Statement: We are given a sequence S of n integers and Mr. Agoji chooses an index i and decreases S[i] and S[i + 1] by 1. A sequence is good if all its numbers can be converted to zero after some moves. We need to output the number of good sub-segments of the sequence.
Constraints: 1 <= n <= 1e5 and 0 <= S[i] <= 1e9
Make good problems for contests? No amigo, imma copy paste
The problem was ripped from Technocup 2022.
Thanks for the link
One of their problems is the exact copy of this problem.
You meant two https://codeforces.net/blog/entry/105684?#comment-940482
I wrote the blog about last year, and luckily I don't (and can't) participate in this year's contest. Seems like they don't improve at all.
The environment was really irritating. I felt like I was in remand.
Testcase of First Problem ( Digit mapping may be) doesn't satisfy its constraints.
They don't provide the clarification form as well :)
Can someone kindly explain how to do digit mapping problem ?
My approach was very simple : find the first occurrence of smallest decimal digit present in the string, then remove chars from the string, required to make one instance of this decimal digit. This decimal number will be my most significant digit, thus I will append this digit once in my ans string.
Now from the leftover string, I will try to form as many zeroes as possible. then append this decimal '0' in my ans string as many times as possible.
Now finally, I will iterate from one to nine and try to form as many digits as possible for each one of them in the ascending order and keep appending these digits as the end of my ans string
For Example : str = rzerotwooneonezerofo
Approach : I will first find the smallest possible digit that can be formed (except '0') which is '1' Then I will try to form as many '0's as possible, and finally in increasing order from '1' to '9' form as many instances as possible.
Expected Output : '10012'
Let's maintain a counter array called cntletter[130].
Definition of cntletter[ch] = number of character 'ch' in the given string.
Now closely look at these string: "zero","one","two","three","four","five","six","seven","eight","nine".
'z' is the unique letter that appear only in '0'. So it can be said that numberofzero = cntletter['z']. Now remove all the occurrences of 'e','r','o' from cntletter that are needed to form "zero".
From now we always find an unique letter that appear only in one number.
They are:
'w' for 2.
'u' for 4.
'x' for 6.
'g' for 8.
'o' for 1. ('o' is also appear in "zero" but we remove those contribution earlier)
's' for 7. ('s' is also appear in "six" but we remove those contribution earlier)
'v' for 5. ('v' is also appear in "seven" but we remove those contribution earlier)
'i' for 9. ('i' is also appear in "five" & "eight" but we remove those contribution earlier)
't' for 3. ('t' is also appear in "two" & "eight" but we remove those contribution earlier)
Now you know the occurrences of each digit. Let's greedily construct the minimum number.
I did the same but the implementation was so boring -_-
Does anyone know the codeforces handle of 何凱鈞 from the winners list ?
+1 I also wanna to know :)
For example, is this the account https://codeforces.net/profile/apupneja2002 of the guy that got 1st place ? If it is, i mean everyone else except him (and i dont know 4th place) in top 6 is GM+ on codeforces.
Guy on the 1st seems suspicious to me. Is there any way to enquire about his identity?
I guess we can try emailing the unstop support, but I'm not sure if they will bother anymore :(
You guys should email directly folks from Agoda. Unstop are just a intermediary who will try to hide issues and pretend that everything ran smoothly.
[UPD] That's a relevant email address I think: [email protected]
.umm what are u saying?
Yep some random leetcoder beating multiple grandmasters.
Demn
Your logic:
Total counter: 4x unjustified assumptions 1x jumping from the corner case to the general case 1x correlation=causation moment 1x circular reasoning
You make more logical loopholes than me in a contest, which is truly surprising.
.Thats irrelevant to what i said
dashing_arpit and apupneja2002 are from the same college, and dashing_arpit is illogically trying to defend his friend. I'm starting to doubt that this is a case of cheating. Should we report this issue to unstop team?
flashmt, Nikitosh, kal013 please look into it.
Okay i didnt care too much about your first comment, but now i start to suspect that you may be a part of the cheating schema that might be going on here.
I don't want to accuse anyone here without actual proof but it's not that hard if you really want to cheat.
While the platform forces you to compete in full screen mode, you can still use an extra monitor to refer to any online resources or passively receive communication from others. You can also do it with other devices like phone or tablet as long as it doesn't show up on the webcam.
The 6 hour window introduces plenty of room for cheaters to exploit. One person can use the first 3 hours to read all the problems and have them implemented then the other person can just type them in for the last 3 hours.
I dont really want to make accusations either. Just his last comment about gms and leetcoders seemed too absurd to me, I felt like expressing what was on my mind then.
The reply is ridiculous.
Surely waste of time