Can someone explain why https://mirror.codeforces.com/contest/1671/submission/155171162 is failing on test case 5? Cannot find the bug...

what if khaled97ha reach grand master in few contests please

Well... my comment aged well lol

What if you both reach master with the same rating on the same contest?

For Div2D, I was wondering if the following approach would work. I tried coding it but it gives WA on TC 22. A small test case for when this fails (could be implementation or idea) would be helpful. Here is the code: 84850363. I create a DSU and each number is a node. I then sort the input array. Then there are two cases: K is even, K is odd.

If K is even, then I need to pick the k/2 smallest numbers such that there is a gap of at least one between each number. I start picking from the smallest number. If there is no conflict (we haven't taken the number before and haven't taken the number after), we can simply take this number. If there is a conflict, then the number is added to that component, and the amount of numbers that can be taken from that component is (size + 1) / 2. We keep taking numbers until the sum of the components with the rule above is >= k/2.

If K is odd, then we need to concern ourselves with the first and last numbers. If we pick the first number or last number, then it can only be a part of the odd indices. If we do not pick either of those numbers, then the sequence can be a part of the even indices, so we must pick k/2 - 1 more.

Please let me know if this idea would work, and if so, what is wrong with the code. Thanks!

Sorry, I’m not fully understanding how you’re including-excluding over primes directly. How do you compute the number of pairs with a common factor of 2,3,5? This would be common factors of 30, so we’d see the number of combinations of (x, y) where 30|x and 30|y? Which is the number of multiple of 30s in the x range * the number of multiples of 30s in the y range? And then you’d do inclusion (+) of all 1-prime factors, exclude (-) all 2-prime factors, incision (+) all 3-prime factors, and so on for all primes <= 10^7?

I’m thinking the following solution, but it seems too slow. Compute the prime factorization of all numbers <= 10^7. Using sieve this takes O(n loglogn). Then each query for a prime factorization of a number takes O(log n) time. Then for each prime in the prime factorization, we need to do inclusion-exclusion, which takes O(2^p), and the number of distinct primes of any number less than 10^7 is at most 10. So O(2^10)=1000. So each query will take O(1000+logn), and there are at most 10^7 queries, so O(n(1000+logn)), which is too slow, about 10^10. How did you solve this previously using this method, or am I missing something?

Can you explain step 3 in more detail. Namely, how does the inequality simplify?

I understand and have coded the LCP solution now, thanks! I am not sure if I fully understand the alternative solution. I understand how you can binary search (if a length of k is valid, then all lengths 1...k is valid; if a length of k is not valid, then all lengths k...n is not valid). If I want to check if some length of k is valid, how would this be done efficiently? There are n-k+1 substrings of length k so O(n) substrings of length k, and we just add all of these substrings to a set and if we ever add a duplicate, we know that length k is valid? I am not sure how efficient a set is for strings (is it O(n^2) for n insertions as each insertion takes O(n) time since we must compare the strings one at a time?). I think this is where hashing comes in, but I am not sure how to use this correctly.

I am trying to learn C++ as I usually use Java. I had a question regarding DP problems in C++. Often, a vector cannot be used in recursion, so is an array preferred? I was thinking one way to still use a vector is to give an initialize max size so we can treat the vector as an array and access indices but is initializing a vector with a specific size really slow (I used a vector with 10E6 size and TLEd)?

Furthermore, if I do use an array, how can I initialize all elements to a value as fill_n(begin(dp), size, INF) gave a run-time error.

Thanks!