For those who gives me negative vote, please let me know how can I improve my previous comment? Normally we can see the announcement at the homepage and every contest has its writer's name at the contest list. Thanks in advance :)

yep.. it's rated.

-48 votes?? I think we are being quite rude here. This person has participated only once! It might not be obvious for newcomers. This much hostility makes the community unhealthy for beginners.

Why less hacking?

So much for "less hacking"... there are 40 pages of hacks: http://codeforces.me/contest/743/status (EDIT: select "Verdict: Hacked" on the right side panel)

i cant get you

Usually a regular round is rated. So, in my point of view it's unnecessary to mention if the round is rated. But in case the round is not rated then it's necessary to mention it. And newcomers should read the FAQ before participating. Thanks :)

Tell her because it's the new usual.

I just came after having a horrible exam, but yeah it's codeforces round so happy enough.

You'll get the exams! Participate in the contest and don't worry! :)

Some people worries in exam result. Some are just more worried in rating change result

I've been sitting here for the past 15 mins staring at the contests page.

Right after hack it was like
Pretest passed
Running on test 8
Hacked

int n, a, b; string s; cin >> n >> a >> b >> s; if (s[a] == s[b]) cout << 0; else cout << 1;

Взаимная любовь она такая

if you fix the minimum frequency , then you can calculate the answer in N*2^8 using dp with state(position , mask) , so now just do a binary search to find max posible frequency. Total complexity N*logN*2^8

At first we can list all of the length t, which means that each digit can appear t or t + 1 times. Then we need to figure out the longest subsequence, so we can use dynamic programming to do this. Let dp[mask][i] mean the leftmost position for us to consider the next digit when we now have filled the digits set mask, and we have i digits whose length is t + 1. We can choose a digit not in mask and greedy choose the next position, which can be processed in O(n²) time at the begin of the program. Thus the whole algorithm is O(8n² + 8n * 2⁸).

UPD: We can also binary search t to speed up the algorithm into . And if n = 10⁶, we can use binary search in vector to greedy get the next position, in this case the whole algorithm is .

i tried making D[k][i][j] — first position where ends finding j elements of type k from position i after that, for each permutation of the subset ( 0 -> 8 ) i try to find best solution, hard to explain, i finished the solution right when the time ends, the solution is correct but not sure if it fits in time

i think i found a solution in O( N^2*8 + 8!*8*log(n) + 8!*2^8 ) precalculating D[k][i][j] — from position i to D[k][i][j] are j elements equal to k. With that precalculated bs the answer making all permutations and checking every combination if its valid in O( alphabet = 8 ). After we find the respective number, we can check which elements will appear lenght+1 times in the final answer in O( 8! * 2^8 ). I implemented this solution with linear searching instead of bs and it works pretty fine: 68ms http://codeforces.me/contest/743/submission/22980164

Sorry for bad english

Let the binary string be s (1-indexed). Then if s[a]==s[b], then answer is 0, else it is 1.

0 if the companies in A and B are different or 1 otherwise.

Well just print 0 if value at a and b are the same. Otherwise is 1. Because if value at a and value at b are different, you have to get to the next airport if the next one is same as b you travel right away to b so cost 1, on the other hand it will cost 0.

And hacking streak after that.

That feel when you don't understand the answer is 1 when the companies are different and instead find the nearest airport to airport B of the same company as airport A.

Why? The question did not state maximum non-negative pleasantness.

Proof?

Не умничай и радуйся своей победе

This is my logic, but didn't get to submit

First, sum all values in a subtree, and store in a sum array.

Then, do a DP on each vertex and find the max value you can get from this subtree, using values from sum array.

Then traverse the tree again and take 3 global variables with you : v1=-inf, v2=-inf, v3=-inf. V1 holds the max value of two subtrees( we'll use dp table from before ). answer is v1, if all v1,v2,v3 are > -inf.

v2 and v3 are the two values we took to make v1.

For every node you can store the sum of pleasantness of its subtree with DFS. Let's call this value P[node]

Suppose two nodes u and v, these nodes can be paired if u is not an ancestor of v and vice-versa.

You can traverse the tree and, for every node u find another node v which is neither an ancestor nor a children of it, with maximum P[v] and update the final answer.

I think there are several ways to find that node quickly, I used Range Maximum Query with Segment Tree.

The last part of I_love_Captain_America solution can be solved using segment tree too. During traversing we can mark each node by it's start and end time. Now all the node of a sub-tree will fall into a range [start time,end time]. If we take this node for Chloe we need to choose another non-intersecting sub-tree for Vladik. We can take the sub-tree from range [1,start time — 1] and range [end time+1,n] except the nodes fall in the path from root to current node. To exclude the nodes from root to current node we can update it's value with a large negative number at the beginning and rollback to it's actual value at the end. You can look at my submission for better understanding.

Внимательность проверяли

cin>>n>>k; n=n-1; x=n+1; y=power(2,n); while(k!=y) { k=k%y; y=y/2; x--; } cout<<x;

for (ll i = 0; i <= n; ++i) {
if (k&(1LL«i)) {
cout « (i+1) « endl;
return 0;
}
}

And C was googble :(((

what was i thinking...

Hint: DP on tree

it can be solved in a greedy approach too

Example case 2 is your friend , personally i think this problem is too mathematic.

2/n = 1/n + 1/n

So, n is x.

1/n = (n+1)/(n*(n+1)) = 1/n+1 + 1/n*(n+1)

I didn't know about Egyptian fractions! I wanted to find some pattern and suddenly it came to my mind! And the 2nd test case helps a lot to solve this problem.

I did not had any idea about Egyptian fractions so tried the following method. I ran 3 loops for x,y,z, with upper limit 200...after checking for small values of n, I found that the solution will always be n n+1 n*(n+1). I put these values in the expression. And found it to be true.

It is logical that for any number 2/x, it can be divided into 1/x + 1/x

So first number is x.

Now we have to split 1/x into two parts (1/y and 1/z) such that sum = 1/x.

Observation: x/x+1 * 1/x = 1/(x+1) -> we pick such a division to get 1 in numerator

Therefore we can divide the remaining 1/x into 1/x+1 + 1/(x)*(x+1).

For example, 1/3 can be divided into 3/4 and 1/4 parts, 3/4th of 1/3 = 1/4, and 1/4th of 1/3 = 1/12. So answer for 2/3 = 1/3 + 1/4 + 1/12

And you realize all this and fail on n=1...I Hate my life.

I didn't know about egyptian fractions. My approach was heavily influenced by example 2, which was n=7, sol: 7,8,56. Using this example, I proved that n, n+1, and n(n+1) always works.