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.com/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.com/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.

You can run a brute force to generate all solutions for a particular n and notice that a solution of form n, n + 1, n(n + 1) always appears. You can now prove that it works for all n by simple algebra and go for it.

First, I thought that 2/n looks a bit weird and it is worth to remove 1/n from 2/n (put x = n). The remaining equation looks much simpler: 1/n = 1/y + 1/z. If you look at the examples or try to guess yourself, you will notice that 1/2 = 1/3 + 1/6; 1/3 = 1/4 + 1/12 etc. Then you can realize that 1/n = 1/(n+1) + 1/(n(n+1)). So, y = n+1, z = n(n+1).

Otherwise, you can just rewrite simplified equation like follows: 1/n — 1/y = 1/z (y-n)/yn = 1/z All you need to get a solution is to set z = yn and y-n = 1 — which gives you the same as above.

And, of course, notice that y and z should differ — so n = 1 is a special case. Actually, maximum value of 1/x + 1/y + 1/z we can get with pairwise different x, y, z is 1/1 + 1/2 + 1/3 = 11/6 which is less than 2/1 — so for n = 1 answer is -1.

Initially I also formed equations and starting thinking of LCM of x,y,z . But then it was too much of trouble so I gave up that approach and started thinking from scratch. Following is what I next thought: Think of 2/n as 1/n+1/n . Then by observation , 1/n can be written as 1/(n*(n+1)) + 1/(n+1) so write any one of the two (1/n)s as 1/n*(n+1) + 1/(n+1). Thats pretty much what i did. Took me 45 minutes to see this . But then in the end my solution got hacked in the last minute (and i could not correct it in that less time)because there was one edge case here(n=1 ; ans would be -1 for this case). Hope this explanation helps.

I didn't even think that it could be solved with a formula :( I used brute force. The idea is:

1. If 1/x + 1/y + 1/z = 2/n, then some of {1/x, 1/y, 1/z} got to be bigger than 1/3 * 2/n, which means that some of {x, y, z} is less than 3n/2 (which is of order 10^4). Without loss of generality, let it be x, so we guessing it by looping from 1 to 3n/2.
2. Next, same reasoning can be applied to 1/y + 1/z = 2/n — 1/x; at least one of {1/y, 1/z} got to be bigger than 1/2 * (2/n — 1/x), therefore one of {y, z} is less than 2 / (2/n — 1/x). Again, this is something of order 10^4 so we can afford doing second loop over y.
3. Now, you just calculate 2/n — 1/x — 1/y and check a) whether it can be represented as 1/z (so basically nominator divides deniminator) and b) that x != y != z. This check takes constant time, so the whole solution works in O(n^2).

Something like this:

6 1 6
111000

Read this
Some of the test cases I used are
12 6 12
101010111000
9 4 9
101000111

rating is lating ...

you have to pick something, thats the given condition

see the constraints 1 ≤ k ≤ 2n - 1

I'm not sure why it showed up differently on your machine, however your ans variable is an integer instead of a long.

I've figured it out! When you make the bitset out of k, in your computer the initialization treats k as long long. However, in codeforces server, k is parsed into an int, and then the bitset is generated. Sorry, but your wrong answer is a consequence of lack of standardization among compilers :/. (You should try to print string s in custom test of codeforces to see how no bit of k is being registered in the server.)

I think if you try to hack a code and this code is resubmitted it will said "that code has been hacked or resubmitted"

I was the one you tried hacking. You are not correct, thienlongtpct

From log we see, that I submitted after your hack:

01:11:27  A  Unsuccessful hacking attempt by thienlongtpct
01:11:38  A  Accepted [main tests]

My initial code: 22962124 simply passed your hack http://codeforces.com/contest/743/hacks/273143/test with a correct result :)

I think it not depend on how bigger the number N is, it depen on the time we find the answer.

if (a % b == 0 && x != a/b && y != a/b && a/b > 0 && a/b <= 1000 * 1000 * 1000) {
    printf ("%d %d %d", x, y, a/b);
    exit (0);
}

Maybe with n = 10000, it may find the answer quickly and and then end the program (exit (0)) when the stament is true. However, with n = 8865 it cosume more time to find the answer.

When I try it on CUSTOM INVOCATION
- for 10000

- for 8863

Вот мне кажется ты не прав. Хороший раунд получился:

• А. Я перечитал задачу. Там всё достаточно подробно и четко. Кажется, что там присутствует идея с тем, что ответ это 0 или 1. Если не сообразить, то многие могут набажничать (ведь эта задача для тысяч участников разного уровня подготовки). Посмотрел несколько упавших попыток — не похоже на непонимание условия.

• B. Для более чем половины участников задача была в достаточной степени содержательной. Конечно, какой-то особенной новизны в задаче нет. На официальную олимпиаду такое брать нельзя, на Д2 раунд вполне можно. Такое случается для первых задач Д2, ничего особенного в этом нет. В этот раз я следил за раундом из университета и наблюдал как мои студенты пишут раунд. Участнику, который впервые столкнулся с похожей конструкцией задача была интересна и безусловна полезна. Вот чего не хватает — хорошего разбора по ней с введением в строки Грея и описанием некоторых свойств и альтернативными способами построения.

• C. Математическая задача, которую решили далеко не все. Ну вот что значит безыдейная? Технических сложностей её написать, очевидно, не было. Значит не придумывали.

• D. Отличная задача на анализ деревьев, поиск в глубину и тому подобное. В условии явно написано "корневое дерево". Не думаю, что были особые сложности с пониманием её условия. Идея в решении, конечно, присутствует. Почти всем из Д2 она была интересна.

• E. Я не считаю, что если в задаче возможно более эффективное решение, то его обязательно надо требовать от участника. C задачей справились 59 участников из 4381. Большая часть из решивших сделала это в последние полчаса контеста. Такой исход мне нравится значительно больше, чем решения от 0-3 участников и то, которые на самом деле из Д1.

Кстати, вопросов по задачам во время раунда было рекордно мало. Это сильный признак хороших условий.

Мне кажется, ты имеешь какие-то странные ожидания от задач второго дивизиона. Следует понимать, что ты Legendary grandmaster over 3000. Конечно, большое количество задач для тебя безыдейны, но не являются таковыми для многих участников Д2. Эти контесты в первую очередь ориентированы именно на них и не ставят перед собой цель хорошенько озадачить тебя.

I think you have to write your code on ideone in order to be readable

You only check for subtrees of the first tree that have more tan 1 child. It is possible that the answer is lower in the tree. Take the following test case: ~~~~~ 7 -1 -1 -1 1 1 -1 -1 1 2 1 3 2 4 2 5 3 6 3 7 ~~~~~ Your program will state that the answer is 1 (from the subtree rooted at 2)+(-1) (from the subtree rooted at 3), when actually, the answer is 1 (from the subtree rooted at 4)+1(from the one rooted at 5)

First, by dfs you can get sum[u] and dp[u].
- sum[u] means the sum of a[u] and a[ vi ],vi is the son of u
- dp[u] means the max value of sum[u].....dp[ vi ],vi is the son of u
and start another dfs
when dfs(u),
- if u have more than 1 son you choose twos sons v1 and v2,satisfy dp[v1] and dp[v2] is the max and second max value in the son of u.and record the max value of v1 + v2.
here is my code 22968058

its a constructive algorithm so it prooves itself. you can calculate the length of the array in o(n) with formula lng[i] = lng[i-1]*2+1; array is constructed as last array + new element + array; so thr new element is in the middle. with that observation you can say that if the element k you search is in the middle you can say its the unique element of the given length. if its in the left side, you search in array n-1 the same k. if its in the right side, you know that both halves look the same so you find the corespondent of the k-th element in the left side, which is k-lng[n-1]-1 and search that element in the n-1 string

hope it helps, sorry for bad english

Input

15 18432

Participant's output

<

Jury's answer

12

char(12 + '0') will be represented as char(12 + 48) = char(60) = '<', not "12" as you want. Actually, your solution will not fit in the time limit as far as the length of the resulting string will be too large.

562949953421312 = 2^49, 1125899906842624 = 2^50, isn't it?