__BaD_mAn__'s blog

By __BaD_mAn__, history, 20 months ago, In English

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

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

| Write comment?
»
20 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

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 ?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This test case exists? I wasted like 1+ hours to debug and wonder where did my segment tree gone wrong

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

    • »
      »
      »
      20 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

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

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I'm trying to reach them out as well and they responded with this

        Yes, we will check the test cases first and then after making the required changes, we will run all the test cases. There were a few test cases that caused the issue. Thanks, Team Unstop (Formerly Dare2Compete)

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

»
20 months ago, # |
Rev. 6   Vote: I like it +3 Vote: I do not like it

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 !

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea as to how to do the 4th or the 5th one?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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'

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve hotel problem ?

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
20 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how you solved the cashback(Happy Tourism) problem?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

»
20 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

In problem 6 (Best-rated hotel), I've tried with segment tree and sqrt 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++.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
20 months ago, # |
  Vote: I like it +15 Vote: I do not like it

One of their problems is the exact copy of this problem.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
20 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They don't provide the clarification form as well :)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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'

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I did the same but the implementation was so boring -_-

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know the codeforces handle of 何凱鈞 from the winners list ?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1 I also wanna to know :)

    • »
      »
      »
      19 months ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      For example, is this the account https://codeforces.com/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.

      • »
        »
        »
        »
        19 months ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Guy on the 1st seems suspicious to me. Is there any way to enquire about his identity?

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          I guess we can try emailing the unstop support, but I'm not sure if they will bother anymore :(

          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            Rev. 2   Vote: I like it +3 Vote: I do not like it

            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]

      • »
        »
        »
        »
        19 months ago, # ^ |
        Rev. 4   Vote: I like it -41 Vote: I do not like it

        .umm what are u saying?

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

          Yep some random leetcoder beating multiple grandmasters.

          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            Rev. 4   Vote: I like it -54 Vote: I do not like it

            Demn

            • »
              »
              »
              »
              »
              »
              »
              19 months ago, # ^ |
                Vote: I like it +27 Vote: I do not like it

              Your logic:

              1. Assert that the person(P) was (A) legit and (B) did problems on leetcode
              2. Assert that (C) GMs cannot do leetcode and (D) did not do leetcode (???)
              3. Under assertion A, P beat 5 other GMs legit.
              4. because P did leetcode, GMs did not do leetcode, and P is better than GMs in one single aspect, all doers of leetcode must be better than all non-doers of leetcode on all levels!!1!
              5. And thus you have "proved" that leetcoders are better than GMs, which justifies Step 3 and assertion A!!1!

              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.

            • »
              »
              »
              »
              »
              »
              »
              19 months ago, # ^ |
                Vote: I like it +13 Vote: I do not like 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                19 months ago, # ^ |
                  Vote: I like it +13 Vote: I do not like it

                I don't want to accuse anyone here without actual proof but it's not that hard if you really want to cheat.

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  19 months ago, # ^ |
                  Rev. 4   Vote: I like it +8 Vote: I do not like it

                  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.

»
19 months ago, # |
  Vote: I like it +31 Vote: I do not like it

The reply is ridiculous.

»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Surely waste of time