SecondThread's blog

By SecondThread, history, 11 months ago, In English

Meta Hacker Cup Round 1

Meta Hacker Cup is back, with Round 1 starting in under 24 hours! Register here.

To qualify for Round 2, you must place in the top 5000 of this round. As a reminder:

  • In the human track, we do not allow AI usage, or working with any other contestants during the contest.
  • Please make sure you are familiar with our submission system, and have a strong internet connection available during the contest. We don't expect to have as large output files as we did for the practice round, but we won't be able to extend your timer due to network issues for future rounds.
  • If you are using Windows, we recommend you do not use notepad if you do not Windows to render your data files as garbled characters.

T-shirts will be awarded based on Round 2 and Round 3 performances. Round 1 will include some of your favorite Hacker Cup characters and locations, along with some brand new ones. We had a lot of fun putting the problems together, and we hope you enjoy solving them. See you on the scoreboard!

Update: Scoreboard has been revealed!

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

»
11 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Excited to participate!

»
11 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Contest starting in 2 minutes! GLHF!

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

We pray for servers to work this time (also gl hf!)

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

I get the following error when trying to submit: https://freeimage.host/i/K8fZkUx.

I get the same error when I try to request clarification.

@SecondThread

»
11 months ago, hide # |
Rev. 2  
Vote: I like it +5 Vote: I do not like it

Ok, I'm going crazy here. I've gotten presentation error 20 times by now when using the validator on A1... When I use diff on my local machine, it gives me exactly the same result... am I just stupid or is this actually a problem other people are facing?

Edit: Just turned on a VPN, and all of a sudden it's accepting my code... wth??

»
11 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Tell me this round server is vibe-coded without telling me this round server is vibe-coded :). Still can't submit anything :(.

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

Contest site is very very unstable and can't download input file

»
11 months ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Oops, an error occurred on our end while processing your submission. Please try again.

What should I do ... in 2 minutes left...

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

Is the server down? getting

Sorry, this content isn't available right now The link you followed may have expired, or the page may only be visible to an audience you're not in.

»
11 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Stop the count 🙏🙏🙏

»
11 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

frustrating and painful my rank is soo bad even after trying for soo long :depressed_cat:

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

Enjoy a (tougher?) bonus variant of the problem C since I completely misread the question and only realized after 30 mins of coding and debugging — score of a subarray is min(number of operations + number of non-zero elements after performing the operations)

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

Hi, can someone explain how to solve B2?

  • »
    »
    11 months ago, hide # ^ |
    Rev. 4  
    Vote: I like it +14 Vote: I do not like it

    Factorize $$$B$$$. Iterate over all subsets $$$S$$$ of prime factors of $$$B$$$. Check for each subset $$$S$$$, whether the product of its elements is not bigger than $$$A$$$. If yes, also take $$$T$$$ the subset of elements you didn't put into $$$S$$$. Calculate $$$ans=SnB(S) \cdot SnB(T)$$$, with $$$SnB$$$ being the amount of possible Distributions of those factors into $$$N$$$ baskets, see also https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). Sum all those values together. That is the answer.

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

      What are e.g. the factors of 12 — {2, 3}, {2, 2, 3}, {3, 4}, {2, 3, 4, 6, 12}, or something else? How do you avoid double-counting an array of N elements like [2, 2, 3]?

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

        Ah, I will edit to "prime factors", thanks for this heads up. The prime factors of $$$12$$$ are $$${2,2,3}$$$

        I counted like this, see "recurse"-Method:

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

    I tried something on the lines of factorization. So basically considered all factors till sqrt b. If counterparts are less than equal to a consider that too. This gives you a list of eligible factors for the first N, prime factorize that to get frequency of each prime factor.

    For each prime factor, the number of unique combinations due to that or the number of ways to distribute that specific prime factor in n spots is equivalent to x1 + x2 + x3 + ... xn = freq. Do this for all prime factor freqs both before and after, take product of all.

    Sum for all factor, did not consider sqrt twice. Also the result for x1 + x2 + x3 + ... xn = freq = n + freq — 1 Choose freq. But I got incorrect answer, can anyone please help?

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

      I think I got my mistake, but unable to download the full input to test my updated code

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

    My solution idea:

    First compute all the factors of B.

    Then let dp[a][b] = the number of sequences of length a+1 that start at 1 and end with b, with every element being a multiple of the previous one. The final answer is the sum of dp[n][b] * dp[n][B/b] where b ranges over all factors <=A.

    To compute dp, use this transition: dp[a][b] is the sum of dp[a/2][c] * dp[(a+1)/2][d] over all c,d such that c*d = b. And of course, dp[1][b] = 1 for all b.

    This works because there's only O(log n) "a" values you care about, and the number of triples (c, d, b) is small (I don't have a good bound but the intuition is that the number of pairs a, b such that ab <= n is O(nlogn) so I imagine it's low in this case too).

    This is the gist, in the implementation I compressed the values of a and b to intervals and used a 2d array.

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

If my submissions to the last two problems are accepted, I can see why they are round 1 problems.

»
11 months ago, hide # |
Rev. 5  
Vote: I like it +49 Vote: I do not like it

You can actually solve C in $$$O(n^2)$$$.

Here is a pseudocode for straightforward $$$O(n^2)$$$ solution:

Code

It of course won't work in the reasonable time (5 minutes) for $$$n = 10^6$$$. Therefore it won't work for solutions that solve each testcase in parallel. But what you can do is just parallel not the testcases themselves but rather the function do_job() between all testcases simultaneously.

I was able to get the answers to all testcases ($$$39.84$$$ megabytes filesize of input) in $$$18.097$$$ seconds while running my solution on $$$96$$$ CPUs. That would even be enough for the maximum possible input of $$$90$$$ cases with $$$n=10^6$$$ each. Such an input would be $$$684 Mb$$$ long and running time would be about $$$18.097 \times \frac{684}{39.84} \approx 311$$$ seconds.

It's worth mentioning that running time heavily depends on the behaviour of if in the cycle: if the input is random than it almost always gonna be evaluated as false and compiler will optimize that with branch prediction. If the input is such that the if can randomly be evaluated as true and false, the execution time gonna heavily degrade.

I benchmarked that if you compile solution (without do_job() parallelizing) with -O3, on random n=2e5 array it works in $$$\approx 20$$$ seconds and on n=2e5 array where each result of if is 50/50 it works in $$$\approx 65$$$ seconds.

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    whoa !!! how do you have 96 cpus for fun stuff ?

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

    wait, what!! Are we allowed to do that??

    • »
      »
      »
      11 months ago, hide # ^ |
       
      Vote: I like it +22 Vote: I do not like it

      I'd be shocked if it wasn't allowed. Its an obvious trick for this format that I've seen many people use (though often with a lower number of cores).

      Another interesting technique that people sometimes use (often in combination with the above trick) is calculating all possible answers for problems with small input spaces (which might still take 30+ mins) before requesting the input and just trivially querying their pre-calculated answers.

      • »
        »
        »
        »
        11 months ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        Imagine you runned solution on your machine with $$$10000$$$ cores and it worked for 3 minutes. Than you fail to submit your solution in time because of problems with the Meta servers (which are happening quite often).

        In that case you submit clarification with your solution and output. Which admins might not be able to process in your favour if they decide to run your solution locally.

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

      Haha I didn't even know that they generally don't plan to run our source code (so there's no implicit runtime constraint of one to a few seconds) until after the contest D:

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

    This is actually goated. Pure goated behaviour.

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

    Pay to win ahh contest. (jk)

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

    on n=2e5 array where each result of if is 50/50 it works in ≈65 seconds.

    It's an interesting fact, that clang++ prefers using CMOV, completely eliminating all branches. This leads to degradation in the average case, but significantly improves performance in the worst 50/50 case.

    rand() & 0xFF: clang++ (1.18x) vs g++ (1.0x)

    rand() & 0x1: clang++ (1.18x) vs g++ (5.45x)

    builtin_expect_with_probability do not solve the problem.

    Let's hope for builtin_unpredictable in the future.

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

I couldn't submit anything. I managed to download the validation tests for the first one but the real pwd protected input wouldn't download. For the other problems not even the validation input would download :'(

I ended up sending my source code via a clarification, but I lost all that time trying to download, checking my internet, switching to my hotspot, etc

»
11 months ago, hide # |
Rev. 2  
Vote: I like it +21 Vote: I do not like it

Is this legal for D or not?
write brute force dp solution (this takes 10 sec for 90 tc having n<1000)
once i download the test file, it has only 4 inputs having n >1e3, so just submit 16 files.

Btw i was unable to submit D as i got this idea near last few minutes :(

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it +17 Vote: I do not like it

    Presumably, only your last submission counts, and they don't tell you if it's right or wrong on submit. So I guess you still have a 1/16 chance of AC with your approach =)

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

    300 iq tactics.

    Interestingly enough that input for C also has exactly 4 testcases with $$$n=10^6$$$, all other cases are $$$n \leq 100$$$.

»
11 months ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

SecondThread Please let us download the submissions of other users. I can confirm my result by comparing the output of my code with that of tourist's code :)

»
11 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I want to try to submit for B2 in practice, but I can't download input, it just returns error:

Sorry, something went wrong. We're working on getting this fixed as soon as we can.

»
11 months ago, hide # |
 
Vote: I like it +69 Vote: I do not like it
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

After how much time, can we expect the result of Round 1 to be declared?

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

    Weird shit to have server issues with less than 15K concurrent users sending less than 10 submissions

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

      I would suspect unoptimized leaderboard queries more so than submissions, but yeah, weird regardless.

      • »
        »
        »
        »
        11 months ago, hide # ^ |
        Rev. 3  
        Vote: I like it +16 Vote: I do not like it

        Unfortunate to be rejected by the company due to low performance on system design interview

»
11 months ago, hide # |
 
Vote: I like it +148 Vote: I do not like it

Did you forget to press the "unfreeze scoreboard" button?

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

    Maybe they are doing LLM/plagiarism checks before revealing results?

    • »
      »
      »
      11 months ago, hide # ^ |
       
      Vote: I like it -78 Vote: I do not like it

      Enlighten me with your brilliant idea for such a thing, how do you guarantee someone has not just messed up with an AI generated code to look a bit more realistic?

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

    From what I've figured, they're just trying to fix the scoreboard/validate submissions of people that couldn't submit due to server errors. Also some people have penalties of 13h for problem B2 :D

»
10 months ago, hide # |
Rev. 2  
Vote: I like it +7 Vote: I do not like it

Though the score doesn't come out, based on the difficulty, if the contest hold normally, any score strictly lower than 32 (A1 + A2 + B1) cannot pass, and any score strictly higher than 32 can pass, for score equal to 32, speed is needed, so you need some speed if you only got 32.

But due to the network issue, maybe author will let every 32 score pass, and there will be more than 5000 and probably less than 6000 contestants passed.

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

I saw a guy who solved all 6 Problems with a penalty of 18:54:22 , how is that possible, even if he submits all 6 questions at the same time in the end , it would be 6*3 = 18 hours only , or is there any penalty for multiple/wrong submissions ?

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +47 Vote: I do not like it

    Haha that’s actually me (feeling famous now hahaha). What happened is that during the first 5 minutes of the contest I tried to submit B2 normally, but because of the website errors I couldn’t. So before the timer ended, I sent a clarification with my solution asking if they could submit it manually (I must’ve been one of the first to do that, since I did it before they even sent the announcement explaining that option). They must have mistyped the time when submitting it manually, because they gave me a penalty of 13:15:47, but I actually sent it around 1:31:54 into the contest.

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

      oh cool , btw can you give any tips how of how give became so good , u literally solved all 6 , meanwhile me struggling to even solve 4.

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

When will we get the verdicts as there is still only submitted tag on our submissions?

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

How to C, like what's the exact intuition behind that?

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

    Flattening is only possible when a subarray’s total XOR is 0, so we use prefix XORs to count such ranges. We compute the total cost assuming all subarrays are unflattenable, then subtract those belonging to equal-prefix-XOR groups using combinatorics.

»
10 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Submit For Practice is redirecting to the Error page! When can we submit?

»
10 months ago, hide # |
Rev. 4  
Vote: I like it -144 Vote: I do not like it

SecondThread its request to hacker cup organizers that your 5 min rule is not fair beacuse lot of folks A2 submissions missed due to VS code large data set compilation for sample validation and after 5 min you guys locked the submission, im saying what the cause for doing that even its not answer script its simple test cases you can allow just simple due to this and your system issue yesterday me missed my A2 and even lot of folks experienced that so please consider this for next hacker cup.

thanks.

wanted to know about OGs opanion about this matter Um_nik

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    The server was having trouble with submissions, but what does it have to do with VS Code? I'm confused...

    The more times I read this text the less I understand it.

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

      I think what he means is, he downloaded the input, and then copied it to clipboard to paste it into some VSCode extension instead of just doing file redirection. Since the input was large, (who tf copies a 40+ MB file) his VSCode crashed costing him time. But instead of learning how to do it perfectly, isn't it easier to blame the authority. This is exactly what he did. Typical, mess up and blame.

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

    You should learn how to use computer (and English) first.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +171 Vote: I do not like it

    My opinion is that you can't speak English.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +31 Vote: I do not like it

    My Observation: The whole first paragraph here is actually a single line containing 91 words and a single comma.

    A true masterpiece

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

What factorization method did you guys use in B2 ? Cuz the naive implementation would take 140 * sqrt(B) operations ~1.4 * 1e9 ?

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

Haven't looked into Hacker Cup much, but can someone tell me what's the acceptable number of operations for a solution. Like in A2, T*N = 4*10^7. So I didn't attempt Binary search as it would have made operations 20*T*N -> 8*10^8. But the actual testcases passed using Binary search when I gave up writing a O(N) solution after 1.5 hours.

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

    Same for me I was thinking of using some prefix and suffix array thing but was missing some edge cases; so thought of taking a bet on BS and it took approx. 15 sec to generate the output file.

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

    I would recommend doing practice problems on past contests and using the time function when you run your code to test these things out empirically.

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

    The time limit is 6 minutes. They don't care about how efficient your solution is, as long as you are able to get the output file and submit within 6 minutes. I might have a wrong solution for A2, as my binary search solution takes 1.6ms to run for the test input.

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

    Whatever can run on your PC (or VM or wherever you'll be trying to run your code) in the 6 minutes you're given; but on a pretty modest PC you should be more than fine with ~$$$10^{10}$$$ operations in the timeframe.

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

    Binary search is absolutely fine with those limits in that time unless you write it really poorly.

    I used binary search up to about 10^10 (just being over-cautious at the top end), so that's about 34 iterations. Within each binary search I did BFS. It passed the whole set in 2 seconds.

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

      Yep mine too passed in 2 sec, but I spent 1.5 hours thinking of an O(N) solution. For example if same constraints were given on codeforces, Binary Search would have given TLE, so I got confused as I had not looked up Hacker Cup.

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

        It wouldn’t, because the time limit is per test case on codeforces

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

          So you are implying that when in codeforces t=100 and time limit is 3 seconds, I could potentially write a solution that goes on processing for 3*100 = 300 seconds. I am pretty sure that is not true. Am I missing something?

          Also as you said earlier that the total operations went 10^10. So you think this would have passed in codeforces even with a 3 sec time-limit?

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

            In codeforces questions where T > 1, they constrain the sums over all test cases. That’s what you’re missing. Also I didn’t say total operations 10^10, I said that 10^10 was my upper limit for binary search :)

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

              Got your point. As you said codeforces sums up N when T>1. But this is mentioned in the constraints itself. Sometimes this is not mentioned and it means every testcase could have that many N. Just like in Meta Cup, this wasn't mentioned, so as far as I am concerned each T could have had N = 5*10^5, so T*N = 4*10^7, Now when you multiply 34 -> 10^9. So I have always considered 10^8 to be 1 sec (unless that is also wrong) it would have meant 10 sec. And I was thinking that they will also run our file again to check TLE, but ig I was wrong.

              I was under the impression that the intended solution would have operations under 10^8. Thanks for the help!

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

                Can you find an example on codeforces where T is large, the sum of N is not constrained, and the time limit is small? Meta has an extremely generous 6 minute limit which means there’s no concern.

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

Do we know by when the solution's correctness will be revealed? And tutorials available, especially for D? I'd want to understand how to approach/prove solution for D theoretically.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +35 Vote: I do not like it

    Consider each A as a '(' and each B as a ')'.

    Now imagine it’s Bob’s turn, and they’re playing on a regular parentheses sequence. Since it’s a regular parentheses sequence, every '(' is matched with a ')', so what Alice can do is play the '(' that’s paired with the ')' Bob played on his last turn.

    So, if Alice can make her first move in such a way that the sequence left for Bob is still a regular parentheses sequence (maybe with some unmatched '('), then Alice wins. If Alice can’t find such a move on her first turn, then she leaves Bob with an irregular parentheses sequence (with an excess of ')' somewhere), and by an analogous argument, Bob wins.

    What’s interesting is that I didn’t think about the parentheses idea during the contest, and after it ended, we discussed our solutions with kovaxis, and they seemed quite different: I was thinking in terms of Alice playing in a position such that the prefix sums of the resulting array are always non-negative, while he did an iterative process where he kept matching things of the form “BA” since that would make Alice win (I didn’t fully understand that part, hahaha).

    The funny thing is that I spent some time wondering whether those solutions were equivalent or if one of them would fail during testing, hahaha. After a while, I arrived at the parentheses interpretation, and the cool part is that I check the condition in the classical way (by verifying the prefix sums), while he builds it by matching '(' and ')' from the inside out.

    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it -19 Vote: I do not like it

      I honestly considered parenthesis sequences but the initial selection by Alice (consider case BBBBA) is where this was not convincing (I tried prefix sums), so I'm trying to figure out why there can't exist any second case where Bob can do something like this in his turn, how Alice's first turn prevent that.

      I simply tried all sequences of length 20 with a brute and compared with suffix sum (finding last position where Count(A) > Count(B)) and it matched for all inputs.

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

    If we treat an A as +1 and B as -1, the strategy is for A to make the biggest move possible such that the remaining suffix has a non-negative sum. If that's possible, then A wins, otherwise B wins.

    Note that if the full string has positive sum, then you can always make a move like that, but it's not a necessary condition — for example BBBBBBBBBBBBBBAAB is winning for A despite having a negative sum.

    To prove the condition, you can think inductively — suppose A makes this maximal move — then you can show that no matter what B's response is, the sum will be positive and then A can make a good move again. Similarly, if A cannot make a move that leaves a nonnegative suffix, that means that no matter what, B will have a negative-balance string, and can follow the strategy from his side.

    The parenthesis interpretation above is cool — I didn't think of that earlier, but you can show that if you follow my strategy, you are guaranteed to leave a balanced string. I don't know if noticing this fact helps come up with a solution though.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +12 Vote: I do not like it

    Here is a way to solve it without the bracket sequence observation (and feels more natural to me).

    Start with the naive $$$O(n^3)$$$ dp. $$$f(l,r,t)$$$ denotes whether the current player can win the game if the game is played on the segment $$$[l..r]$$$ ($$$t = 0$$$: Alice's turn, $$$t = 1$$$: Bob's turn). Transitions are $$$O(n)$$$ so the whole dp table can be computed in $$$O(n^3)$$$ time.

    Now observe the structure of the dp. For a fixed $$$r$$$, $$$f(l,r,0) = 1$$$ for some prefix of $$$l$$$, because if $$$[l..r]$$$ is winning, then $$$[l'..r]$$$ $$$(l' \lt l)$$$ can also win by copying the same first move played on $$$[l..r]$$$.

    Based on this observation, let's define $$$dp[r]$$$ to be the maximum $$$l$$$ for which the segment $$$[l..r]$$$ wins for Alice (or $$$0$$$ if no such $$$l$$$ exists). Alice wins the game if $$$dp[n] \gt 0$$$.

    We will compute this dp in increasing order of $$$r$$$. There are now 2 cases to consider. The case where $$$s_r = A$$$ is trivial, $$$dp[r] = r$$$.

    Consider the case where $$$s_r = B$$$. Let's say after Alice makes her move, we are left with the segment $$$[l..r]$$$ $$$(l \leq r)$$$. This $$$[l..r]$$$ segment needs to be losing for Bob, so $$$s_l = A$$$ must be true (otherwise Bob wins right away). In Bob's move, he reduces $$$[l..r]$$$ to $$$[l..r']$$$ $$$(l \leq r' \lt r)$$$, and then the turn comes back to Alice. Bob loses if all states that he can put Alice in are winning for Alice i.e $$$dp[r'] \geq l$$$ must be true for all possible $$$r'$$$. Thus, the conditions for Alice to reduce the game to $$$[l..r]$$$ and win are:

    • $$$s_l = A$$$
    • for all $$$l \leq r' \lt r$$$, $$$dp[r'] \geq l$$$

    To compute $$$dp[r]$$$, find the largest such $$$l$$$ (if it exists) and set $$$dp[r] = l-1$$$ (Alice can reduce to $$$[l..r]$$$ only by starting at some $$$l' \lt l$$$). If no such $$$l$$$ exists, $$$dp[r] = 0$$$.

    This is the core idea of the solution. However, my final implementation turned out to be something very similar to the bracket sequence formulation, which is very interesting to note.

    DP Code Snippet
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    If Alice makes a moves and eats A and there is B right after that, she will lose. So, she would never make a move by eating AB, the same logic applies to Bob. Therefore, they would never make a move by eating AB, so erasing this pair from the sequence would not affect the game. We can repeat this until we left with the sequence of the form BBBBAAAAA, (Bs and then As), this case is trivial: if there is A Alice wins, otherwise Bob wins.

»
10 months ago, hide # |
Rev. 3  
Vote: I like it -13 Vote: I do not like it

.

»
10 months ago, hide # |
Rev. 2  
Vote: I like it +156 Vote: I do not like it

It's a little unfortunate that results have taken nearly 24 hours to release--aside from general curiosity about how things turned out, contestants who got FST will likely want to debug their solutions, and it's easier to do that when results come out soon after the contest.

Separately, it seems unfair to use penalty time to determine Round 2 qualification, since contestants experienced varying degrees of tech issues. If I had as many tech issues as some other people seem to have had, it's easy to imagine how my penalty time could have been several hours worse.

My suggestion (if technically feasible):

  • Release the current results now, rather than waiting until every clarification has been processed
  • Pick some reasonable cutoff (probably at or slightly below the current 5000th-ranking score) and let everyone with that score or higher advance to Round 2.

Notably, the second proposal addresses concerns where if results were released right away, someone ranked around 5000th could think they qualified for Round 2 based on the current results but fall outside of qualification bounds as more clarifications are processed.

  • »
    »
    10 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it -29 Vote: I do not like it

    Gloves Off,

    why the fuck is Meta modifying results after it's over and just taking peoples word on when they submitted and allowing them to provide source code after the contest finished?

    Why should the people who couldn't submit at all leapfrog the people who got delayed and took longer to finish the round?

    Remove the cheats and finalize the results!

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -72 Vote: I do not like it

    And what about all the people who solved their problems correctly but missed the tiny 6-minute submission window due to the system being broken?

    There already is a precedent for this — invalidate the round like in 2023. It makes no sense to go for a different solution when the exact same situation repeated itself.

    • »
      »
      »
      10 months ago, hide # ^ |
      Rev. 3  
      Vote: I like it 0 Vote: I do not like it

      they have mentioned everything about what procedure you had to do while submitting solution in FAQs section plus they conduct practice round so that most participants/new participants get used to submission system so they won't face any difficulty while submitting in Original contest,so I feel there is no fault from their side

»
10 months ago, hide # |
 
Vote: I like it +151 Vote: I do not like it

petition to make it a punishable offence to delay contest results by more than 36hrs

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

    this is my first time giving hackercup, generally how much time does it take to publish results?

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

    btw you can process the clarifications even after making the solution verdict public, i don't understand the point of keeping everyone waiting

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -13 Vote: I do not like it

    I'm not sure there's going to be a next year for you to use your brilliant idea. AI will get smarter than Tourist and no one can validate who has wrote the code before submitting.

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

When will the result be rolled out?

»
10 months ago, hide # |
Rev. 2  
Vote: I like it +75 Vote: I do not like it

It's understandable that the tasks of processing so many solutions AND trying to weed out cheats are taking a significant amount of time, but it would be nice if Meta could communicate in the interim with occasional status updates and even rough, indicative timeframes.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -44 Vote: I do not like it

    A blue dude made a script to compare scoreboard with CF rating, in a few minutes after the competition. The delay is probably not related to task processing, they have not even allocated enough resources to host the competition without downtime.

    Any engineer earning 6 figures can probably just poop in the keyboard and come up with a better architecture than the current shit that is running on their server.

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

      Clearly the architecture is not up to scratch, you’re right about that. But I’m pretty confident you’re wrong and the delay absolutely is to do with task processing.

      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it -21 Vote: I do not like it

        What if I use AI to go to the finals this year, are you going to remain with your affirmation? Leetcode has already proven the latest models can solve all of their contest questions.

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

          I didn’t make a single affirmation relating to the use of AI.

          • »
            »
            »
            »
            »
            »
            10 months ago, hide # ^ |
             
            Vote: I like it -18 Vote: I do not like it

            So, what are they processing then? Better to make an IPO of this application that took so long to develop.

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

              Um. All of the hundreds, probably thousands of submissions that people failed to upload because the servers were down. I thought that was obvious.

      • »
        »
        »
        »
        10 months ago, hide # ^ |
        Rev. 3  
        Vote: I like it -8 Vote: I do not like it

        How many tasks do you think there were? Let's assume 3 per user, which is less than 50K in total. Most of them consists about extracting a file from a message and comparing it with the expected one.

        They have almost 15 years of experience hosting this kind of competition, supposedly with the same system as of the last 5 years. You're telling me that, this is the first time they came across this problem?

        I can clearly see AI improvements since the last competitions, which can bring ranking problems. How do you differentiate between someone using chatGPT or not? A random person can simply go from nowhere to finals.

        • »
          »
          »
          »
          »
          10 months ago, hide # ^ |
           
          Vote: I like it +15 Vote: I do not like it

          Cheat detection usually happens post publication of the scoreboard. I'm not sure why you keep going on about AI — you're having a conversation entirely with yourself on that one.

          As for having to process thousands of bespoke requests, checking for legitimacy of submission, timings, matching against the right questions, etc, then I think you're grossly underestimating the simplicity of the task.

          But if you know better than they do, you should get in touch with your script — I'm sure they'd love to hear from you.

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

            Aren't all submissions valid? AFAIK they have created a Facebook account, and they probably already store timestamps.

            You can basically compare the sent output with all questions outputs, then mark the matching question as solved. Why would that be a problem?

            Check if it was sent during the 6-minute time window of clicking on the UI button and reject otherwise.

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

              Because they're applying a degree of rigour to it, to ensure they get it right, rather than just waving their hands and saying "it's easy" like you.

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

                How tricky is it to compare two files? I had to pass through this part to submit it. You only get a score if there's no presentation error and no value diff.

                The only exception is for accepting a submission out of the 6-minute time window due to any personal reason.

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

                  You don't know anything at all about the nature of the clarification requests. You're just making sweeping assumptions that they're all identical. It doesn't require much imagination to think of quite a few ways they could deviate from 'standard', such as tagging the request as a 'general query', or to the wrong question by mistake (which would be picked up by the standard submission process, alerting the user), or marginally outside the time versus significantly outside the time.

                  There's several other examples just off the top of my head, after you declared there was only one possible exception.

                  And then, of course, if they do write a script that covers all of these, they have to be super-confident it works in every case — which requires quite a bit of testing. When did you last design, build, test and release a product feature in a day?

                  Seriously though — get in touch with Meta — you clearly know it all.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months ago, hide # ^ |
                  Rev. 2  
                  Vote: I like it -11 Vote: I do not like it

                  Thank you for remembering me, this is definitely the first competition that Facebook/Meta hosts.

                  They have never had a similar issue previously, nor worked with a more complex website, with just a tiny larger user base.

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

                  The fact that they've never had a similar issue previously means they don't have a ready-made fix.

                  At this stage you're just flaunting your ignorance. By all means carry on into the void though. Or put your money where your mouth is and get in touch with them to let them know about your fix.

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

      Is the script published somewhere? I'd like to see some statistics as well :D

»
10 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

I wasn't able to submit for the first 30 minutes because of "Something went wrong". I managed to solve A1, A2 and B1 and with my current penalty I'm ranked 5.5k+ but considering the issues I had from the website, when I subtract 90 minutes from my penalty (30 minutes of issue and 3 ac's so 90) I get top 4k. this really is unfair because I had nothing to do. Even then I had to submit in Incognito mode after reading this comment (LINK).

I hope some action will be taken for this. SecondThread

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    But the issue was with everyone, right? Why are you crying then? Considering the same penalty for everyone, you will still be at the same place, isn't it?

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

      No, the issue wasn't with everyone. Only some people. You can check the comments under this blog and the main hckercup blog to check

      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it +6 Vote: I do not like it

        I also had this issue, but refreshing the page and tapping on Submit/Validate option worked, although I had to submit multiple times for that.

        I don't think anything can be done for this, but you can still be qualified for the next round as they will surely filter cheaters, as problems were AI-solvable.

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

          I had the issue initially, but i closed all tabs, then tried clearing cookies and then opened again, it worked (I mean i could submit).

»
10 months ago, hide # |
 
Vote: I like it +49 Vote: I do not like it

Please fix "Submit For Practice" (Ф﹏Ф)

Frozen scoreboard is a minor inconvenience, but not being able to upsolve is a real torture :)

»
10 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

wow, already 48 hours...

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

Finalize the results!

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

it was diffcult as hell

»
10 months ago, hide # |
Rev. 6  
Vote: I like it +32 Vote: I do not like it

Could you just reveal all the submission and let us practice? Actually I don't care what is my final ranking. And I also don't mind my rank keep dropping after the reveal. Just tell me which question I did right or wrong.

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

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

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

I noticed some mismatches between the AC verdict and points.

Someone who solved all except B2 has 56 points, which should be 82. Another person who solved all except D has 56 points, which should be 79. I believe there are more examples like this.

The standings need to be refreshed.

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

These rankings are so funny. I can clearly see cheaters who got their scores updated after sending clarification requests. What a fucking joke.

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

    let's hope , plag check happens...

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -7 Vote: I do not like it

    Yeah, it’s honestly a complete joke. What’s even funnier is that I got flamed by the cheaters themselves when I called them out.

    They didn’t even catch 50 people — that’s laughable. For context, a typical LeetCode contest catches 3,000–5,000 cheaters on the night of the event, and another ~1,000 over the following week.

    At this point, they may as well just allow AI outright and stop pretending this is still a “human” competition.

»
10 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

I didn't — make it to round 2 :(

I didn't play in 2024, I saw the announcement a little to late, and in 2023 was generally around 1100-1200th. I couldn't even make top 5000 this year.

I wonder how much of this drop is

  • My ability on the day (I made a couple of mistakes on the day)
  • New people entering the competition that are better than me
  • Cheaters using AI, I used google to search something and actually skipped over the AI response because that would be cheating, but I'm sure others did not do that

Maybe I'll do better next year, or worse.

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

sir, for my solution for A1 is correct but in contest it is showing wrong answer on test case becoz ur new test cases is not in correct form- https://ibb.co/jPhf2GXy . as well my code logic is same as geothermal . my code — ~~~~~~~~~~~~~~~~~~~~~ #include <bits/stdc++.h> using namespace std;

void solve_case(int case_num) { int n; cin >> n; vector arr(n); for (int i = 0; i < n; i++) cin >> arr[i];

int maxi = 0;
for (int i = 1; i < n; i++)
    maxi = max(maxi, abs(arr[i] - arr[i - 1]));

cout << "Case #" << case_num << ": " << maxi << '\n';

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

// Enable this block if testing locally with files

ifdef LOCAL

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

endif

int T;
cin >> T;
for (int tc = 1; tc <= T; ++tc)
    solve_case(tc);

return 0;

} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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

how to solve $$$D$$$?

»
9 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Any updates on the tshirt??

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

Any update about the T-shirts?

  • »
    »
    6 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +49 Vote: I do not like it

    Why is it always the cheaters that are loudly requesting this stuff. You all ruined the competition this year, badly. You don't deserve the prize you got. And if Meta hacker cup doesn't return again, it is because of you.

    And do not try to deny that you are a cheater. A lot of objective evidence has publicly surfaced against you recently.

    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it -46 Vote: I do not like it

      A lot of objective evidence has publicly surfaced against you recently.

      - Maybe my words are of no value to  you as of now , as I am helpless, Those are claims , not proofs , I repeat those are claims not proof . If I'd been so desperate , then why would I let it take so long . I wouldn't  be this active and hindering my academics , you know that most people are taking advantage of this situation . Do not cross question now , I am not in the state of tolerating this much hate .