What a nice person!

So don't give contest

Contest > Cricket

No! It's a tradition! It will forever be there!

mathematics 100

Let me rethink :

so why not rated for someone whose rating is more than 2100

the next prepare many DIVs for you,the div3 is for the rating lower than 1600

The trick is to get lucky, this is the second time I fall from expert to specialist and the next round is DIV3.

haha

I had the same idea and it got AC https://ideone.com/rRrMmW

My solution had the same idea also and it fails on testcase 2. Did you take into consideration that you can reorder the cards of each round however you want?

I've got accepted with this idea.

int dp[2][10]; /// cur/prev, cards count modulo => max damage

55365600

This is the solution for F, maybe you made mistake in considering the different cases.

1. Choose only one three cost card (if exists)

2. Choose one two cost card and one, one cost card (if exists)

3. Choose one two cost card (if exists)

4. Choose 1-3, one cost card (if exist)

5. Choose no card.

There can be up to $$$2*10^5$$$ test cases in the problem with graph containing only one edge (1, 2). Your solution creates so many arrays of size $$$2*10^5$$$ each, and it leads to quadratic complexity of the solution. Replace all arrays with vectors of size $$$n$$$ instead of $$$2*10^5$$$.

I dont know. As for me, it was not too hard. A,B — quite standard problems. C — binary search, D — Sieve of Eratosthenes, E — vertex paint. But maybe i'm wrong

Whats number of the taks?

The best and straightforward answer is just solve more problems. I've started CF 2-3 months ago, and I'm better now than I was then purely because I've simply solved more problems.

I managed to only solve A in this contest when I usually do ABC in Div3, but that attributes to me mostly not solving enough problems that are similar to this.

All other advice pale in reference to the first I provided you, but its also nice to know that Div3 ABC and Div2 ABC can almost always be solved greedily (they just require implementation/data structures and not complex algorithms like graphs or dynamical programming).

In fact, A was not as easy as it should be. I solved it by trying in which order the three operations should be applied. But I still dont know why the one I finally submitted works, and others do not. B was less problem for me than A. As a suggestion, try to keep calm if it does not work out as expected.

You can't delete your comment after two minutes.

Example from awoo:

If you'll start coloring from the vertex $$$5$$$, you cannot take less than $$$3$$$ vertices to cover all vertices (vertices can be reordered so the vertex $$$5$$$ will be vertex $$$1$$$ or something like this).

Consider a chain of length 3. If you start from one end, you will need to color 2 vertices which is more than 1.

maybe smth like 1 -- 2 -- 3 -- 4 -- 5, you get 1,3 and 5?

I am getting a runtime error in Problem E. Can someone help fixing it. Link to Code

https://mirror.codeforces.com/contest/1176/submission/55374222 i have done the same !! why it giving me tle ?

Sir, I love your videos regarding competitive programming and always get motivated

We can find the distance of all nodes from root(1). (using simple DFS)

Then we can select even or odd distance nodes which fulfill ( N/2 — condition) .

May be smth like this: 12 4 8 15 16 23 42 4 8 15 16 23 42

Did you interpret meaning of subsequence right? I thought it might be an error.

maybe due to the use of remove function. I was doing the same at first attempt .

rem[1] -= min(rem[1],rem[2]); rem[2] -= min(rem[1],rem[2]);

when you subtract from rem [1], the result increases as the already subtracted rem [1] is subtracted from rem [2]

You are changing the value of res[1] before calculating min(res[1],res[2]). Store the value in some other variable and then u can use it later. I have corrected your code : https://mirror.codeforces.com/contest/1176/submission/55376346

Is it legal for codeforces? If so, it seems to me unfair

In my case: My solution got Hacked because of using memset(visited,0,sizeof(visited)); for each test case. The size of visited array in my soln was 2e5. So if the number of test case is 2e5, it will give TLE. :/

you use memset T times

Using memset T times: giving TLE. Even my solution got hacked due to same reason :/

not in div 3

The number 1530169 = 1237 * 1237 is not a prime, so in the first program you will iterate from 2 to 1237, but in the second program you will iterate from 1530168 to 1237.

• In the worse case the first program will iterate from 2 to sqrt(x).
• In the worse case the second program will iterate from x-1 to sqrt(x).

No

Asking for minimum number of vertices is NP-hard. Wikipedia page

For a tree u can calculate that value using dynamic programming and problem is called minimum set cover

Indeed, this number sequence is the one used in "Lost".

I think it's because you use memset in the beginning of each test case. Which is around 1e5 test cases, and you use memset for an array with a size of around 1e5, so its basically a TLE.

yes, someone hacked my solution using TLE verdict. :(

You can DFS or BFS start from node 1 to build a tree of the graph. Now if the number of nodes which have odd degree is <= n / 2 then the answer is all of them, otherwise the anwser is all the nodes which have even degree.

Notice that this problem can be solved on a tree this way:

1. paint a tree in two colors (black / white), this way each edge will connect vertices of different color and it will guarantee us that each white vertex is connected with at least one black and vice versa
2. splitting vertices into two groups guarantees us that one of these groups will not be greater than $$$\lfloor \frac{n}{2} \rfloor$$$ (application of Pigeonhole principle)
3. We can select any group of vertices to solve the original problem, so we need to select smaller group of vertices

Now, we can notice that removing edges from our graph without breaking it into multiple connectivity components does not affect the solution correctness (if we satisty all conditions with less amount of edges, we still satisfy it for any additional edges). This allows us to delete some edges from our graph without breaking connectivity. So, we can delete all edges and only leave a spanning tree of our graph (we can do it with DFS) and solve problem on a tree.

Try resubmitting it.

check answers above before commenting.

i don't know if that is the main problem or not .. but test like this

 14
 4 8 15 16 23 23 42 4 8 42 15 16 23 42

fails in your code .. you pop from the queue whenever you enter the function even if the sequence isn't right so you affect the following sequences.

you define vector t times with size MAXN.

Not it

your bug is in finding maxD. actually you're finding greatest prime factor! and cause of this you may erase something which is not in multiset(st.end()) from it and you get memory limit in this case

I think you're incorrect fill maxD. maxD at your logic is max prime divisor while you need there to just max divisor.

You can fix it, if replace maxD with minD and try to find p / minD[p] instead of maxD[p].

I think this is intended solution. I have something similar but I didn't debug yet. And I really doubt there is something shorter

For this test case your output is correct. But in test#2 there are 40057 testcases. You just wrong output in some other testcase.

P.S. Your solution is incorrect for graph-chain. Lets imagine graph 1-2-3-4-5-6. There are 6 vertexes. And you output n / 2 vertexes with smallest degrees. There you can output vertexes 1, 6, 2. And vertex 4 remain unconnected.

your solution isn't correct let's try this:

1

7 6

1 2

1 3

1 4

2 5

3 6

4 7

Your solution doesn't respect order of numbers.
As said in task:

"Examples of bad arrays:

[4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,42);..."

First solution does three recursive calls, second always does only one.

I don't think the order matters in this question, as the number of steps depends on the prime factors of the number itself. Let's take 60 for example, here 60 = 3 * 5 * 2 * 2 ; so it will always require 2 operation 1, 1 operation 2 and 1 operation 3 and as second and third operation multiplies 2 and 4(2 * 2) respectively, we would need to apply first operation 3 more times. Hence, the answer would be 1 + 1 + 2 + 3 = 7 irrespective of the order of operations applied.