Is anybody else also having the issue where they are unable to hide tags for unsolved problems? I uncheck the checkbox in the problemset tab but after some time has passed or after I have refreshed the page, the change is reverted and the tags are visible once again. This has been happening to me for more than a week now.

MikeMirzayanov, can you look into this?

Thanks!

UPD — The bug has not been fixed yet.

UPD 1-3-18 — The bug has not been fixed yet.

UPD 3-3-18 — The bug lives on.

Seems like HackerRank is down. Anybody from Hackerrank knows what will happen to the live contests? I mean, should we wait for 5-10 mins for the site to come back or what?

Problem A. Sherlock and Parentheses

Category: Ad-Hoc, Math, Greedy

Let's define n = min(L, R). Then the claim is that the sequence ()()...() consisting of n pairs of "()" will give us the maximum answer

Proof:

Let's look at some sequence T = (S) where S is also a balanced parenthesis sequence of length m. Let's denote by X(S), the number of sub-strings of S that are also balanced and by X'(S) the number of balanced parenthesis sub-strings that include the first and last characters of S (In fact this will be just 1). Then X(T) = X(S) + X'(S).

It should be easy to prove that X'(S) ≤ X(S) (simply because X'(S) is a constrained version of X(S))

If we rearrange our sequence T to make another sequence T' = "S()", then X(T') ≥ X(S) + X'(S). The greater than equal to sign comes because we might have balanced sub-strings consisting of a suffix of S and the final pair of brackets.

Thus, we have that X(T') ≥ X(S) + X'(S) = X(T). Thus by rearranging the sequence in this manner, we will never perform worse. If we keep applying this operation on each string, we will finally end up with a sequence of the form ()()...() possibly followed by non-zero number of ( or )

Problem B. Sherlock and Watson Gym Secrets

Category: Math, DP

Let's look at all valid pairs (i, j) in which i is fixed. Then, if i^a mod k = r then j^b mod k = (k - r) mod k.

There are only k possible values of the remainder after division. Since k is small enough, if we can quickly determine how many numbers i exist such that i^a mod k = r and j^b mod k = (k - r) mod k then we can simply multiply these quantities and get our answer. Thus the reduced problem statement is —

Find the number of numbers i ≤ N such that i^a mod k = r for all .

Let's denote by dp1[r] = number of i ≤ N such that i^a mod k = r. We will try to compute dp1 from r = 0 to k - 1 in time

Let's make another observation —

i^a mod k = (i + k)^a mod k = (i + 2k)^a mod k = (i + x * k)^a mod k

Proof:

Now i + x × k ≤ n. This implies that .

Thus if we know that for some i ≤ K, i^a mod k is r then there are x + 1 such numbers which also have the same remainder.

This gives us a quick way to compute dp1

for i = 1 to k:
    r = pow(i, a) mod k
    x = (n-i) / k
    dp1[r] += x + 1

Similarly, we can compute dp2[r] which denotes the number j ≤ N such that j^b mod k = r

Now our final answer is

ans = 0
for i = 0 to k-1:
    ans += dp1[i] * dp2[(k-i)%k]

But we need to exclude the cases when i = j

To handle this we can simply iterate one last time from i = 1tok and find all the cases when (i^a +  i^b) mod k = 0. and subtract from the answer for all such i

for i = 1 to k
    if pow(i,a) + pow(i,b) mod k == 0:
        ans -= ((n-i)/k + 1)

Problem C. Watson and Intervals

Category: Greedy, Line Sweep

Refer to this comment

Problem D. Sherlock and Permutation Sorting

Category: DP, Math

Since N is too large to enumerate all permutations, we need to come up with a clever way to compute the final answer. There are several hints in the problem that we can pick up on. Firstly there can be at most N distinct values of f(p). But there are N! different permutations. This means that a lot of permutations are going to have the same value of f(p). Thus it seems reasonable to try and find some way to compute the number of permutations which have the same value f(p).

Our second hint comes from the statement "all elements in a chunk are smaller than all elements in any later chunk". Trying some permutations out on pen and paper gives us the following claim —

If there is a valid way to divide a permutation into chunks, then there must exists a right most chunk. Moreover, if the size of the right most chunk is X, then it must consist of the largest X elements of the permutation.

The first part of the above statement is trivial. The second part can be proven by way of contradiction by trying to partition the permutation in a way where at least one element in the rightmost chunk is not one of the largest X elements. Let this smallest element in the right most chunk be i. If i is in the right most chunk, then one of the largest X elements j is to the left. Since j > i, this means that this is not a valid way to partition the permutation into chunks.

But we don't just want to partition the permutation into chunks but we want the maximum number of chunks. To take this into consideration, let's define the notion of a primitive right most chunk. The right most chunk of size X of some partition of the permutation is said to be primitive, if it does not contain a proper suffix of length Y < X which also consists of the Y largest elements i.e. if any suffix of a right most chunk C is not a primitive chunk, then C is said to be a primitive chunk.

Why have we defined such a complex notation? This is motivated by the fact that if a right most chunk contains a suffix of size Y which contains the largest Y elements of the permutation, then we can split the current chunks into two chunks of size X - Y and Y such that this will also be a valid partition and the number of chunks in our partition will increase by 1.

Thus we have another lemma —

If a permutation p is divided into f(p) number of chunks, then the right most chunk in this partition must necessarily be a primitive chunk!

Now, let's use the tools at hand to make our third observation to crack this problem.

Let's assume that the size of the primitive chunk in a maximum partition of a permutation p of size N has size X. We know that this consists of the largest X elements of the permutation of size N. We should notice that all the chunks on the left are just the maximum way to partition a permutation p' where p' is the suffix of length N  -  X of the permutation p.

So what does this mean? We have a recursive way to partition a given permutation into the maximum number of chunks! Start from the right and find the right most index i such that p[i... N] contains the largest N - i + 1 elements of the permutation. This must necessarily be the primitive chunk of the permutation p. Thus we can recursively compute the chunks for p[1... i - 1] and append p[i \dots N] to get the maximum way to partition p! Great, but we can make an even more powerful observation. You don't necessarily have to append p[i... N] to the chunks of p[1... i - 1]. In fact any primitive chunk of size N - i + 1 can be appended to p[1... i - 1] and the value of f(p) for each of these permutations will be the same!

Let's have a look at these statements using some more formal notation.

Define prim(n) to be the number of primitive chunks of size n. Observe that value of prim(n) is independent of the actual values of set but only depends on the size of the set i.e. number of primitive chunks consisting of {1, 2, 3} is the same as number of primitive chunks consisting of {100, 101, 102}.

Define sum_f(n) to be the sum of f(p) of all permutations p of size n. Using our observations from above, we can create a recurrence relation for sum_f(n) in terms of prim()

How did we get this recurrence? Let the size of the primitive chunk in optimal partition be n - i. There are prim(n - i) ways to choose such a primitive chunk consisting of the n - i largest elements. If we choose any permutation p' of size i, it can be a prefix of permutations with primitive chunks of size n - i. For each such permutation p', we have the relation f(p) = f(p') + 1.

Thus,

There are i! number of permutations of size i and each of them can be append with one of prim(n - i) primitive chunks. Thus

If we can compute prim(n) for all possible values of n, we can compute the sum of all values of f(p) for permutations of size n in time.

Prim(n) can be computed by the following recurrence relation

This also takes time. But the question is asking us to compute the sum of the squares of all f(p)! We will take care of this by using some math to build a third and final recurrence :)

Now it is time to make the final observation and make a final notation.

Let sqrsum(n) denote the sum of squares of f(p) over all permutations p of size n

We know that f(p) = f(p') + 1 where p' is the prefix of p after the primitive chunk of size (n - i) is removed. Squaring both sides, we get

If we fix the primitive chunk C of the permutation p and take the sum of over all valid p', we would get

For any primitive chunk of size n - i, the RHS of the above equation remains that sum.

Thus

If we take the sum over all possible primitive chunk sizes we will get sqrsum(n)

Thus

Thus we have our final recurrence relation.

This can also be computed in .

Thus our final answer is sqrsum(N).

P.S. Did you'll have simpler ways to solve any of these questions?

Hi there.

I have written a simple Python script that can do a couple of nifty things:

1. Compare the problems solved by user X but not by user Y
2. Give you a weekly breakdown of your problem solving performance on Codeforces
3. Return a list of all your submissions till a specified point so that you can do your own analyses :)

Screenshot

Link

Github Repo

How to install

Pre-requisites:

1. Python 2.7
2. Python Beautiful Soup 4
3. Python requests
4. Python tabulate

Once you have the prerequisites installed, simply place the CFStat folder to the directory where you want to write your script. Then in your script use import CFStat.

Mini-Documentation

1. getSubmissions(user, page_mx, print_flag = False): Generates a list of all submissions from the first page_mx number of pages made by user and prints this list if print_flag = True. Your submissions will be pushed into a list of 3-tuples: time-stamp of submission, problem code and verdict. You can use this list to perform any kind of additional analyses that you want :)
2. getWeeklyStatistics(user, mx, aggregate) : Using the submissions list generated from the previous function, this generates a table for each week between start_year to end_year with statistics like % of WAs etc. Note: Week no is as per the ISO Calendar.
3. compareUsers(user1, mx1, user2, mx2) : Using the first mx1 submissions of user1 and first mx2 pages of user2, this function prints a list of all problems solved by user1 but not by user2
4. start_year and end_year are global variables used in getWeeklyStatistics() to generate a table for statistics for each week between start_year to end_year. Modify these according to your needs.

I guess a lot of things can be automated to make this tool more user-friendly but I got lazy handling cases with the dates and stuff so feel free to fix this for the community :P Everyone is welcome to fork the repository and contribute :)

The code may take up to a minute to fetch 50 pages of submissions and this number may change depending on your internet speed. If your connection is slow then the script might skip some of your submissions.

P.S. No this tool is not bug free and I claim no responsibility if it causes any kind of harm to your computer. Use at your own risk

Can some user with coach mode provide me test case 95 for this problem? I am using a straight forward brute force approach.

Thanks!

Hi,

Have been trying this problem for 4 days now. My solution is the same as that provided in the editorial but I just keep getting WA :/

I have checked my solution with thousands of small test cases and a python brute force solution (with n upto 100) and it has matched all of them.

Here is my C++ code. (I have added comments to the main sections of my logic)

This is my brute force python solution

And this is the test case generator

Kindly help me. Thank you! :)

Hi, I am unable to understand the solution provided in the editorial of this problem. I read the explanations in the comments but can't seem to understand them either.

In the editorial dp_max(v) is given as but in the sample solution 10973864 it is given as . How is that the same?

I have been at this for hours now! Can someone please help me? Thank you! :)

UPD - I have solved the problem using the method described here. But I would still like to know how the author's implementation is working since in the solution I implemented is different. In my submission, in one dfs we use the notation of dp(v) = k, being the k'th smallest value and in the other iteration as the k'th largest value, but in the author's solution, it seems to me that he has used the notation dp(v) = k as the k'th smallest value in both the cases. If so then can someone please clarify the transitions made by the author?

Hi, I am sure we have all come across those problems that have these simple problem statements but are just diabolical to get right. Problems which give you moments like these

These problems are usually hard to get right for the following reasons:

1. Corner test cases
2. Tricky implementation

Typically problems which involve string manipulation, geometry or problems involving decimal precision are hard to get right in the first go without overlooking some minute details. Sometimes these problems require carefully breaking it up into cases.

Recently I solved the following problem and had 4 failed attempts before finally getting it right. In a competition, you might spend a ton of time trying to identify your bugs and that can make or break your final rank in the contest.

So here is what I want to ask the top programmers in the community -

Q. How do you approach such problems during live contests? I have seen many top programmers getting AC on such problems in the first try. (Usually their code is short, simple and consistent with the cases)

A. mkirsche Spend a lot of time thinking before starting to code, and don't take too many shortcuts (longer code is sometimes better if it's cleaner and easier for you to keep track of). I don't know what to tell you about precision — I have problems with that too.

A. Junior94 They're experienced, they've probably failed many times and know what works best and what doesn't.

Q. How do you test your code to ensure that you have not missed any corner test case?

A. Junior94 You can't know for sure if your code is 100 % correct until the final system testing but you can still write stress tests with brute force solutions.

Q. In case the implementation is long and taxing, what is your approach to keep the code neat and simple?

A. Junior94 Think before coding. Also usually the more time you spent thinking about the problem the better your solution will be (thinking in the right track of course). Experience helps a lot here.

Q. How much time do you invest in such problems before deciding they are too risky to solve in a live contest?

A. Junior94 Is the code going to be too long or complicated to write for the remaining time? Are there any easier looking problems remaining to solve? Is it too frustrating? There are a lot of questions you can ask yourself at this point but whether you keep working on it or move on it will be a risk you'll have to take.

Thanks!

Hi, In this problem, I am using the idea that AM >= GM just like in the editorial but with slightly different steps.

Equality should hold when all elements are equal. So according to me, x = y = z and the solution I arrive at is that x = y = z = S / 3

But this is incorrect as seen from the test case

S = 10

a = 1, b = 6, c = 3

My solution gives x = y = z = 3.33 and hence x^a·y^b·z^c =  169350.87

But the optimal solution is x = 1.0, y = 6.0, z = 3.0 with x^a·y^b·z^c =  1259712

What is the flaw in my math? Is this not a correct way to use GM <= AM? I don't understand why my solution differs from the solution given in the editorial even though the principle behind both is the same.

I am trying the following problem.

This is my code.

I am using multiset in C++. I read from here that erase(iterator) works in amortized constant time and insert(val) works in logarithmic time. According to me, my codes worst case complexity is O(Nlog(N)), but it gives TLE on Test Case 15. Is there something I did not follow or is my complexity analysis flawed?

Would be really nice if someone could help!