Hope the next football match doesn't have much kicking the ball, also I have a question for everyone, how is kicking the ball in football relevant for any real life problem?

Maybe spend more time observing :/

I mean, you were asking for problems to not have observations (which is the only part of the problem you have to think). Its pretty reasonable to downvote

The round will be rated for 1600- only or for all who "do not have a point of 1900 or higher in the rating" too?

I guess that will be unfair, because problems are mostly same and somebody could participate at the latter contest knowing most problems

Yeah, we need just to solve 4 tasks quickly.

how long for new ratings to get updated?

This is human nature my friend.

we all hope that but it isn't possible.

div3 are bliss.

And why ?

The problems are fairly interesting especially from D to G although F is easier than what it's position suggests

why? it's quite interesting. you didn't even solve any problem.

exactly

I have an intuition for Dijkstra, not sure though. LOL

Basically just finding SCCs in a fast way. Even DFS works.

you can solve it without binary search https://codeforces.com/contest/1619/submission/140094897

My solution for G: Create a graph by connecting edges between two adjacent nodes such that either they have the same X and abs(diff(Y)) <= K or same Y and abs(diff(Y)) <= K. Each node will have maximum 4 edges. Find connected components and let the total components be T. For ith component, assign value i to all nodes in that component. Then, sort the vertices in order of increasing timer and go through them from 1 to N. At ith vertex, add its component value to a set S and update ans = min(ans, max(timer[i], T — size(S) — 1). That's it! Simple dfs.

Accepted solution: 140115861

Yeah couldn't implement since I kept trying to fix my segment tree solution to E that was getting TLE. Turns out if you use stack you can get $$$\mathcal O(n)$$$ implementation. The last few minutes of Div 3 are always a blur. :(

binary search the alpha. if each people have at least one shop to go and at least one shop can satisfy two people or more, then that alpha is OK.

Binary search on answer

Ok so there are many ways to solve D but I think this is the easiest one: First, compute the shop with the maximum value of each friend.

Let's call the set of the best shops $$$B$$$

If $$$|B| \leq n - 1$$$ then the answer is the minimum of $$$B$$$ ($$$|B|$$$ denotes the size of the set $$$B$$$, i.e the number of distinct values in $$$B$$$).

else, it is obvious that $$$|B| = n$$$ because we can have at most $$$n$$$ different best shops as there are $$$n$$$ friends.

So we only need to remove one shop from $$$B$$$ to be able to buy all the gifts. This means that we need to:

— pick two friends

— assign them to the same shop (so at least one of the two friends will change it's shop)

This way we will reduce $$$|B|$$$ by one (or more) and this is the minimal move we can do so if we pick an optimal move here then it'll give some optimal answer.

So what we need to do is: — Iterate over the shop where we will place the two friends

— Pick the two friends whose joy in this shop is maximum

— Compute the changes on the answer and chmax

Here is my code: https://codeforces.com/contest/1619/submission/140072358

Always

Hard luck.

How can u be at rank 200 with such a very high penalty? :| My friend solved 5 and got rank 300 (official) with much lower penalty.

a=1 s=20

If it works, there is a unique B that satisfies A + B = S (where plus represents the modified addition operator).

Why? Consider working in order through the indices of A and S in reverse. If the next_dig(S) >= next_dig(A), then the next required digit of B is just next_dig(B) = next_dig(S) — next_dig(A). Otherwise, we must consider the next two digits of S as the target number. If 0 <= next_two_digs(S) — next_dig(A) <= 9 then we have our next B digit. Otherwise, we fail and return -1.

If we reach the end of A and S continues, we can extend A with leading 0s to determine the remaining B digits. However, if A continues further than S, we fail and return -1.

Maybe its cuz you used unordered_map?

The issue is that lower_bound defined in algorithm library takes $$$O(n)$$$ time for non-linear containers.

You should use set.lower_bound(key) instead.

O(N) dp solution:

https://codeforces.com/contest/1619/submission/140071470

In F there is some severe text understanding skills necessary.

I think people just died on D, cuz they just read it reversed, thinking n is amount shops but rather not friends.

I didn't read F because it looked long and I didn't have enough time (I lost a bunch of time on D because I swapped n and m...and I just had a hard time solving E) but I read G 5mn before the end and insta solved it so for me G < D < E :')

Could you explain your approach for F please?

if ((y % 100 - x % 10) > 18 || (y % 100 - x % 10) < 0) { cout << "-1\n"; return; } I think first one should be > 9 instead of 18 because of single digit say if y = 22 and x = 9 it will add 13 to the value which is incorrect

If you had that talent, you wouldn't be in division 3.

What is the person even trying to do? Copied some others code and pasted those whiles?

vector.size() returns unsigned int, so when you do v2.size()-1, it will not be -1, it will be out of bound for the unsigned int. And that is why you are getting runtime error. Instead you can store v2.size() in an int variable before the for loop and use that variable in the for loop.

And avoid tagging Mike and other coordinators. Your doubt is not a big issue that you are tagging them :)

3 3

1 2 5

5 1 2

1 4 3

Correct Answer: 3

Use stoll().

Well, I think you can use stoll to get long long int.

We are checking two numbers greater than mid for any shop so let's say there exist two numbers greater than mid and all the rest conditions are also fulfilled then we are taking the answer as mid(which doesn't exist in the array) , so how are you assuring that the final answer will exist in the given 2-D array. Will the binary search cover all the cases ?

you can make it easier

1. for each store find a gift A with the largest joy and gift B with the second largest joy (max and second max in each row)

2. сhoose the store X with the maximum B value

3. for two friends, take these two gifts in the store X

4. for another friends take a gift with larges joy without limiting the store (max in column)

all calculation is performed in one pass O(n*m)

if(tens - digit > 19 || tens - digit < 0) {
                cout << -1 << "\n";
                return;
            }

instead of this you try

if(tens - digit > 9 || tens - digit < 0) {
                cout << -1 << "\n";
                return;
            }

if(tens - digit > 19 || tens - digit < 0) {}

Instead of 19 u should be using 9 since single digits is what we want

I explained my solution in this comment :p https://codeforces.com/blog/entry/98076?#comment-869474

No idea but try on your own for this test:

3
8
8 8 2 0 2 4 7 3
8
5 4 5 1 8 7 2 7
8
0 6 1 6 1 0 6 5

Most probably it is due to the line usable.back() incase your usable vector is empty In that case mex[i+1] directly becomes -1

I believe in that case the problem becomes NP-complete. We can reduce the vertex cover problem (which is known to be NP-complete) to the problem you proposed. But first, let's assume that $$$p_{ij}$$$s can only be $$$0$$$ or $$$1$$$. Therefore, your problem becomes: are there at most $$$K$$$ shops such that we can buy $$$n$$$ gifts of joy value $$$1$$$ for each of our friends?

Now let's get back to the vertex cover problem: Given a graph $$$G(V, E)$$$ and $$$K$$$. Does $$$G$$$ have a vertex cover of size at most $$$K$$$?

To reduce vertex cover to your problem, we map each input of vertex cover to some input of your problem.

For any vertex cover input ($$$G(V, E)$$$ and $$$K$$$), you can assume that the set of vertices $$$V$$$ is the set of shops, and the set of edges $$$E$$$ is the set of your friends. We set $$$p_{ij}$$$ to be $$$1$$$ if the $$$i$$$-th vertex is connected to the $$$j$$$-th edge. Otherwise, we set it to $$$0$$$. So now, the number of shops is $$$|V|$$$, and the number of friends is $$$|E|$$$. If you can find $$$K$$$ shops from which you can buy $$$|E|$$$ gifts for each of your friends, then you have found a vertex cover of size $$$K$$$. Hence, the problem you proposed is NP-complete which almost implies that there is no polynomial algorithm to solve it.

for a = 5 and s = 4 , s-a will be less than zero and no possible value of b can be found