It's also:

sum of squares of first 5 prime numbers,

25-th semiprime number,

7-th centered octahedral number,

47-th Sophie Germain semiprime,

and thousands more on oeis :)

is it rated!?

I think they weren't in div1 when they registered for the contest (before yesterday's rating changes) :D

Daniar LOL

Oh, wait, I AM SUPERSTAR NOW

Commenting here will not help you to leave gray.Try to give focus on problem solving. That will help you to leave gray. wish you to be green :)

mission accomplished

Fixed, thanks!

It's not necessary problems to be from A to F, it could be dobule D (as it was before (D1), (D2)) or any other problem can be doubled

http://mirror.codeforces.com/blog/entry/47816?#comment-321100
Yes!

Here the "but" refers negative.

Such as: I will go anywhere but there.

Not an old issue, but there should be more efforts on translating into English statements.

Same with me , got hacked , lost around 400 points -_-

Anyway problem set were good this time

How do you solve C?

I initialized ans=-1 :'(

should be zero as it was mentioned arr[0] and arr[n + 1] = K

Almost all Hacks for B is n=1 ! :) The answer should be 0...

the extra breakfast is from the last day. you have 2 days of full 3 meals, and 1 day with only breakfast

I hacked one with 0 3 1 ans: 3

0 1000000000000000000 0

n=1 , ans =0 while some people printed k-a[0].

eg:- 1 10 2

You can go into the sanitorium just before the supper and leave just after breakfast.. This case is similar for cases like N M N where N > M.

I am pretty sure greedily finding matches for the next smallest adapter works. Keep computers in a set/dictionary that you can do O(1) lookup on, and remove them when an adapter matches with them.

My solution goes as follows:

Sort all the computers and sockets. Then, find all the pairs where socket power is the same as computer power. Because of the sorting, this can be done in O(n+m) time with two indices. (By moving an index forward when its power is smaller than the other's, and skipping if the socket/computer is already in use). Then I add adapters to all of the sockets and repeat, finding all the matches. You only need to do this around 31 times until all socket powers will become 1.

My code was the 5th fastest overall.

Edit: An identical solution is proposed in the editorial.

let n=max(a,b,c)

now depending on his arrival and leave time, there can be seven possiblities for number of breakfast, dinner and supper available. they are:

b=n,d=n,s=n b=n,d=n,s=n-1 b=n,d=n-1,s=n b=n-1,d=n,s=n b=n,d=n-1,s=n-1 b=n-1,d=n,s=n-1 b=n-1,d=n-1,s=n

for each of these cases , find the minimum number of foods he can miss

Number of days in sanatorium = max(a, b, c).

Then you have 3 case: 1. max = a, it means that you came in morning, also it means that you leave morning (you miss dinner and supper in last day because it's optimal)

Then easy to calculate answer = max(0, (a — b) + (a — c) — 2)

The same logick for other case.

Sorry for poor english.

Suppose the given values are a[0], a[1], a[2]. Sort a and subtract a[0] from all the elements. Now the answer is

This is because any triple b, d, s where difference of any pair is at most 1, is valid.

Hi,
I am guessing that the issue might be because of the implementation of bridge tree mentioned in my blog. It is not very memory efficient because of the global queue used. I realized that once when i got an MLE in a bridge tree problem. You can try changing it with a more memory efficient implementation. For eg, I wrote this better implementation. You can have a look at this:
http://pastebin.com/c7hMLzVw

Edit : Updated the blog as well.
https://tanujkhattar.wordpress.com/2016/01/10/the-bridge-tree-of-a-graph/

if u remove all the bridge edges, u'll get different connected forests. Choose the forest with maximum number of nodes as the center and direct all other forests towards this since there is only one way to orient the bridge edges. So choosing the largest forest will maximiize the minimum sum required.
Then Do a euler tour to give the orientation by adding edges between nodes that have odd degree. Nodes having odd degree are always even.
similar concept was use here : http://mirror.codeforces.com/contest/723/problem/E
The overall complexity is of the order O(n+m).

My idea on F.

We can see that it is optimal to let every biconnected component to form a directed cycle as this won't affect it's potential on other biconnected component. So we should always try to form a cycle for every biconnected component first.

Then we contract all biconnected component and this would form a tree. Now we can do binary search for answer.

Every cities's r_i will have at least x. As every node in tree represent a biconnected component in the graph, r_i will initially be no. of cities in biconnected component i. Lets consider node u, if it's r_u is more or equal to x, it should let the edge between u and its parent and direct it to u. So its parent's r value will be increased by r_u. Else, the edge should direct its parent.

Now dfs again and for every edge that are directed to its child, we can increase its r value.

So if every r_i is >= x, x can be obtained.

edit :

lol I failed system test because I read the problem wrongly and thought r_i is the number that cities can go to city i. But the idea is still the same for the problem.

ac code : http://mirror.codeforces.com/contest/732/submission/21563511

Well I passed the system testing with a pretty simple solution. First of all we should notice that the answer of the problen is the maximum size of a bicconected component. Then to get how the edges will be directed, first you convert each bicconected component into a strongly connected one and you are left with the edges between the strongl/bi-connected components. It's simple to see that the compressed by strongly connected component s graph is a tree. So you make the component with the maximum size as a root of the tree. Then you make all edges between the components to go to their parents so that you can reach the root from each one of them. In this way you get alogN (N+M) solution.

PS: I wrote an O(N+M)logN one because I used a map to easily access edges but this can be done in O(N+M) too.

I am surprised that no one mentioned tarjan algorithm, I think that's the most straight forward way to solve it as you may have already a template coded.

All you have to do is to find the minimum among the most compressed node in each connected component, and memorize them as roots. Initialize them as the root and reverse all the edges, there's your answer.

When you sort pc[], you lose the ordering of the computers. There is no way to output the computers in the right order in line 3 of your output.

Binary search

Binary search. It's easy to verify if the first x days works by choosing the last test day for each exam in those x days and seeing if there are enough days to study before them.

Do a binary search over the number of days starting from day one to day X

To ace M exams you need at least M days + the required days to prepare, i.e. lower bound L = M + sum of required times

Now, to check if it's possible to do so in X days, start from the last day and do the following:

tests = 0

days_needed = 0

if it's a day off OR we took the test already:

decrement days_needed by one if they were > 0

else:

increment tests

increment days_needed by the days you need to prepare for current subject

After last (which is the actually the first) day, check if tests is equal to number of subjects AND days_needed == 0

You can binary search the answer. To check if a particular number N of days works, we can assume we take every test at the latest possible opportunity (within the first N days). If not all the tests can be taken in that time, or we don't have time to study for all of them (and this is pretty easy to determine), then N is too small.

Here's my bit complicated approach : Iterate on the exams, and maintain count of total free days available till now, which are not assigned.

When an exam comes that has not been taken, if its required days are <= count, then mark this exam as done(for now), otherwise, we have two choices, either forcibly take this exam on this day by marking some of the previously done exams as false and adding (their preparation days + 1 exam taking day) to count , or just not assign this exam for now.

We will try to do the first choice if its possible by cancelling some previous assigned exams first. And also take care that any exam that we are cancelling, its next occurrence exists and is before next occurrence of our current exam, otherwise we can just wait to assign current exam on its next occurrence.

To get next smallest occurences of previously done exams, i have used a set. As we are cancelling exams, we remove them from the set. Also, when assigning an exam, insert its next occurence in the set.

Code

That's my solution:

1) Let's create deque[m + 1] byExam, where byExam[i] contains days (in asc order) where we can pass exam number i
2) Check whether byExam[1..m] has at least one exam (otherwise it's unable to pass everything)
3) Create array exam[] where exam[i] = 0 if we don't wanna pass exam at day i, otherwise it contains exam number. At first, iterate over all exams in byExam array, poll last day for each exam and set exam[last_day] = exam_number
4) Create partial sums on exam array. ps[i] = ps[i-1] + (is_exam_at_day_i ? -exam_cost[exam[i]] : 1); We add one to ps if we are free, otherwise we spent exam_cost[exam[i]] at this day
5) Iterate over days in reversed order.
5.1) if (exam[day] == 0) just continue
5.2) if we have an exam at this day (exam[cur_day] is not 0), do the following:
5.2.1) check, whether we can try to take this exam earlier. Just check whether byExam[exam[day]] has elements. If it has, set exam[day] = 0, exam[prev_possible_day] = exam_number, otherwise print day number and exit
5.2.2) Iterate from prev_possible_day to cur_day, do ps[day] -= (1 + exam_cost[selected_exam]). If we have on any iteration ps[day] < 0, it's unable to take current exam earlier, so the answer is cur_day, print it and exit

In other words, at first we choose the safest variant. Then we greedy try to pass last exam earlier.

You can see my solution here: 21584671

Also, the same idea is used in 722D - Generating Sets

Failed in the system test though :p

But the feeling was awesome for sure.

binary search on the number of days . If you want to check if its possible to pass all exams in X days , find last occurence of each subject in [1,X] and take exam of each subject on its last occurence .

Binary search!

Build the directed acyclic graph of the strongly connected components and take the minimum size of a sink connected component.

Just finding all strongly-connected components having no outcoming edges to another SCCs, and determining minimum between their sizes.

Empirically Polycarp learned that the dog needs at least k walks for any two consecutive days in order to feel good.
There is no 2 consecutive days here.

Nice idea!

Can you please explain what the checking function is doing ?

Wouldn't it fail on sth. like this?

5 2
0 2 1 0 2
2 1

you are assuming that we need to do an exam whenever it is possible to do it. But this is wrong, be cause you could save those days for some other exam which has to be completed first. I hope you understand what i said.

counter testcase: 10 3 0 0 1 2 3 0 2 0 1 2 1 1 4

6 2 1 0 0 0 0 2 1 1 I think the answer should be -1 in this test (your code output 6)

check this http://ideone.com/EgztAG

1 3
1

ans wasn't given an initial value to 0 It outputs a random number if the program didn't enter your second loop

I ran your code on codeforces's custom test and it is answering currect to the hack!!!

Can you explain it?

Your program actually gives -1 on the Codeforces Custom Invocation.

1 10
1

Because in your template:

#define rep(i,x,y) for (__typeof(x) i=x;(x<=y?i<=y:i>=y);i=(x<=y?i+1:i-1))

It also loops from reverse to start incase x > y i.e. at pos 1 and 0

your rep(i,x,y) is defined in such a way that in this case it runs from 1 to n-1 i.e from 1 to 0.