I am new here. This will be my first contest here. So will I get my first rating by competing in this contest

There will be 5 problems.

Div-1 participants can participate in Div-2 but those contests will be unrated for them. So they are out of competition.

D2C was one of the dirtiest problems in CF, wasn't it?! and D2D was too simpler than usual. but it was a satisfying contest at all. :)

and newbies are out of competition XD

don't think about ratings, u are here for solving problems and learning something new and challenge yourself :)

Most of the contest it comes after the contest.

A & B not that hard but their codes are really tricky. C & D are really hard.

I don't think you are allowed to discuss the problems here. pretest 1 may not be the same test case as sample test 1.

Same situation with me!

Once happened with me. In my case, i have used "long long int" to access an vector of integer. In my pc not presented error, but CF presented WA on sample 1 :(. I solved this problem by changing the compiler version on CF.

may be you forgot to initialize something .

Probably you didn't see my round :D

Indeed, the idea behind problem C could have been wrapped into another more friendly problem.

I usually code in C++ but recently I have been trying out python on codeforces. I think python was suitable for problem C.

• I got set of usernames using usernames = set(input().split())
• I got username and text using user, text = input().split(':').
• I got the set of words in each text using set(re.split(r'[^A-Za-z0-9]+', text))
• I got the possible senders for each message by subtracting the set of words from the set of usernames. - operator is overloaded for sets.

Implementing this in C++ is so much more effort.

DP on states (index, last user choosen). Possibilities for current user that is unidentified are n. So total complexity O(n*m*m*) per test case

Let's make for all users with unknown name (?) the possible names we could put there. So count[i] = number of possible names to put in row i. If count[i] = 0 and right now it has "?" as username, there is no solution, if there are some i with count[i] = 1, you should put its unique possible name.

Now putting that unique name at some position i with count[i] = 1 could change other count[j], so you do this like bubble-sort algorithm, where you stop when there are just count[i] >= 2 left

If you got to a point where there are just usernames with "?" and count[i] >= 2, there is always a solution, and you can do greedy on that.

backtracking?

do you mean backtrack to recover the solution after doing dp?

My solution will probably fail but anyway, this is what I did. First keep a map to maintain the amount of names which we cannot replace with a given '?'. If it for any of the '?', the value is n, answer is impossible. Now check how many of them have the value n-1, then we satisfy this and update the sizes of neighbouring question marks (if there are any). Keep repeating this until you run out of questions marks with value n-1. Now remaining have values <=n-2. Assign anything to them (obviously not the names in their messages) and keep updating the neighbouring ones. Print the answer according to this.

I tried to do it, but I got mle on test 9, then I coded ordered_set.

In fact, it can be solved just by sorting events({position, coupon-id, is_start_or_end}) but it requires careful processing :/

I tried and got WA on 5

Yes. It was close in memory and time but I optimised ^_^

How would you handle question marks with KMP in E? My solution uses bitsets and has an O(N^4 / 64) time complexity, so the time limit seems reasonable (under assumption that the model solution is similar to mine).

KMP does not work, see my first submission :( (maybe there's a bug in my kmp tho, lol, or hey your kmp is different from mine). I notice a 30ms solution tho, don't understand how it works but it does not seem to be kmp either. My solution works with same time with kraskevich, O(N^4/64)

EDIT the 30ms solution actually TLE in one of my testcase

In fact no O(n+m) algorithm for counting occurrence of wildcard matching is known as I saw here. http://web.cs.iastate.edu/~fernande/STRING-ALGMS/MoreKMP.pdf

Me too QAQQQ.

Actually, problem D is also a hardcore implementation problem.

What is your logic for D? Since you say you think it was beautiful I'm guessing you had a beautiful solution.

*let's sort the intervals

• use 2 sets : set< pair<int,int> >L,R 

 L : to store every  left  side and it's index  

 R : to store every right side and it's index  

• add first k intervals to the sets 

• the ans exists if the max left side <= the min right side

-you can find their values easily from the sets L,R  -first element in L is L.begin()->first -last element in R is (--R.end())->first

• now you should remove one of the k intervals you have    and then add new one from k+1 to n

the optimal way is to remove the interval with the min right side 

you can find it's value and index easily from R then remove it from both sets

during the process , you should save the best ans to get it back 

take a look at my solution and ask me again if you need :  http://codeforces.me/contest/754/submission/23603100

I had the same issue during the last 10 minutes, maybe it was also because of the internet connection, but you should know that it is a common on CF :(

This is because of Christmas "magic". You can change your colour till the 10th of January too, under the magic tab on your profile.

I'm ready to disagree.

I think you forgot to get actual indices after sorting. When I fixed it I passed test 5.

Maybe something like:
2 2
1 2
2 3

What algorithm?

Yeah C, D were whole new Level, :p thats why i became an expert by solving A, B quickly enough, got lucky, Oh and hacks!!, too many people ignored this in the first question
3
0 0 1

You , I like you. :)

worst round of 2017 too.

Heap and two pointer is all you need for D. (I suppose, I didn't submit for system test =P)

I solved it using priority queue. Here is the code. 23593559

Another way to do it without priority_queue is to use an AIB and binary search.You split the interval in two types of events.A starting point and an ending point.Every point will know from which interval came.You sort the points first by value and then by type of events if they are equal the starting points should be the first.

For every starting point you add at position X in AIB 1, where X is the position in the initial sorted vector of intervals.When you have an ending point, you try to find in the AIB the smallest position where are exactly K intervals using binary search ,you save in max the result and you Add -1 in the AIB again at the sorted position for this point.The complexity should be O(N*logn + N*log^2(n))

The simplest way: If total sum is not zero, segment is 1 to n.
If it is zero, Find the first non zero point(say index i) then segments are 1 to i, i+1 to n.

So first of all let's see when it isn't possible to answer, and you can see that it is only that case when wall the input are 0s. When the input has an integer different than 0 you have two possibilities:

1. they sum 0
2. they sum != 0

in 2) you can simply output the whole array
in 1) if you get from the first element to the first different than 0, and from that one till the end. It is guaranteed that both are different than 0

If you check the test, you output
60 60
66 67
Skipping 5 integers, that's why you have the WA

You can't hack it by your test.

Update : In my opinion your test it (variable in code) will grow up to MAXN. Because for p = (n+1, MAXN) : a[p] == 0

The code at hand has undefined behavior — once it == maxn+1, it reads past the array t. The C++ standard does not guarantee memory order of global variables, and it cannot be guaranteed what is located there. If, say, the adjacent memory contains integer n, the condition evaluates to false and the loop terminates. However, if there is only zeroed memory, it will become too big and t[i] will point to invalid memory, causing SEGV.

Yes.

When we choose k coupons, (x1, y1), (x2, y2) ... (xk, yk), number of products we can use is minimum y — maximum x + 1. So we need maximize this value.

Sort initial points by y coordinate increasing. Let's say we are at position i. We can fix this point as the one with the minimum y, and we need to take k — 1 points from range [i + 1 ... n].

The k — 1 points must have maximum x coordinate as small as possible, in order to maximize the value (minimum y — maximum x + 1).

Let's iterate over all points in this order : n, n — 1.... 1, and maintain a heap / set with smallest K x coordinates we have met until now.

The answer for a position i would be : y coordinate of i-th point — largest value in the heap + 1.

Let's say we divide every pair of coupons in two kinds of events, a starting point one and a ending point one.We know that the largest interval we can find for example (x,y), the x will be the x of a coupon interval and the y will be the the y of another coupon interval.

If you do a line sweep in every point and for example you push the interval which has the x point in a set, when you get to a y point you will erase the interval which has this y point but if you do this , it will mean that if you are at a y point you will have in the set all the intervals (x1,y1) in which x1 <= y and y1>=y. At this point the problems resumes at a classical problem.Which is the x from this set, that if you sort all the intervals in the set by x, it will be the k'th element.

Consider 1d version:

There are 2 strings a and b (maybe with question marks), we want to find all occurrences b in a.

Create vectors A and B such that

.

Then calculate where . Now b can start from position i in a iff (remember that C is complex vector though).

For our initial problem we can use similar approach . To find 2d convolution we just need to apply fft to rows, then to columns.You can check my code. Overall complexity is

btw, most of the contestants just used bitsets to find substring occurrences, but there is nothing interesting in those solutions.

There can be multiple answers. Jury's answer is just one of them.

Try this: 4 2 3 7 1 4 2 6 5 8

You can, but I don't think it's an efficient approach.

Here is my approach to solving D. 1.Let's first store a vector {l,r} in another vector for all queries. Let's denote this vector of vectors as v. 2.Now sort this vector.Now we have a vector containing l,r pairs sorted by l. 3.Now here is the analysis — The answer to our question is a range such that its 2 endpoints belong to the set of points obtained from queries. Whenever we get a query of form l,r, we include l and r in this set of points. Lets call this set pts. So our 2 end points belong to pts. 4. Now we plan to iterate over the pts set(stored in a vector). We also make a set<vector> called st. Now as we iterate over pts, we keep in our set only those ranges from v such that their l <= pts[i]. We put the sanges into st in the form {r,l}, so that the ranges in set are sorted by r. 5. We plan to use 2 pointer technique here. For each i over pts we increase j (which is also iterator over pts) and remove all ranges from st whose r<pts[j] till the size of st > k. 6.The answer is max of all pts[j] -pts[i]. 7. There are definately a lot of details left to be explained but are not very difficult to figure out. This is just the basic idea. 8. If you feel something wrong with this approach, feel free to tell me.

I understood the problem after reading the following comments:
1. explanation1
2. explanation2
3. explanation3
4. explanation4

After that I came up with my own interpretation — maybe it will be useful for someone.

Let's think backwards. Imagine that we know the largest interval that we get after intersecting some k out of n original intervals. This interval has to start at some position l_best and finish at some other position r_best.

Now let's concentrate on the starting position of the largest interval — l_best. What is the smallest possible value for l_best? In other words, what is the leftmost position where the largest interval could possibly start?

Intuitively, we need to take k smallest values from a set of all possible left coordinates:
L_n = {l₁ ≤ ... ≤ l_k ≤ l_k + 1 ≤ ... ≤ l_n} ⟶ L_k = {l₁, ..., l_k}
The value l_k is the largest value among all left coordinates in L_k. The left side of the final largest interval cannot be smaller than l_k.

So, here is a skyscraper view of the algorithm:
1. First we set l_cur = l_k as a starting point of our investigation.
2. We find the largest interval that starts with l_cur, by gradually extending r_cur.
3. The interval [l_cur, r_cur] is now a local maximum and we compare it's length to the global maximum achieved so far: [l_best, r_best]. If dist(l_cur, r_cur) > dist(l_best, r_best), that means we have discovered a better interval that starts with l_cur. We update global maximum: l_best = l_cur; r_best = r_cur.
4. This new interval [l_best, r_best] is largest among all possible intervals that start from l_best or start sooner than l_best. Possibly, there is a better intersection of the intervals that starts to the right of l_best, so we update the set L_k and go the step 1.