orz

deleted

Last round you got +220 rating,so I think this round you can have higher rating. May be you can become Master.

I am 1800 now, and I hope I can get +100 rating in near future.

Best wishes to all of you!

And if my rating is 1900, whether my name is purple or blue?

А спустя еще 40 — появится div0 специально для едуков.

Не нужен

to green lol

why somebody always dis me are everyone want‘t be better？ or what wrong with me

you should ask question in the contest but not here

Your score changes so bumpy!What a bumpy grade change.

Your logic behind calculating the modulo of the number of ones is wrong. It is not necessary that the number of ones is divisible by four for a valid sequence of transformations to exist.
Here's an example:
1 1 1 1
1 1 1 1
1 1 1 0
1 1 0 0
you can apply the operation at:
1 1
1 3
3 1
2 2

I think you forgot the case height 2 to height 1 (or height 1 to height 2) when the second position is '0' or '1', these two cases are not the same.

You memset all array in every test , clear only size n

The height of the rightmost pillar must be 1.

"Note that you must start and finish the pipeline on height 1 and, also, it's guaranteed that the first and last characters of the input string are equal to 0."

You could just brute force for B. Check out every possible square, in O(N^2) time. N < 50.

For C, DP isn't actually necessary, although it took me a lot of time implementing.

can't we solve it using greedy? I tried it using greedy but got WA on test 13 and still don't know why.

idea — first find all the continuous segments of zeroes with length > 1 and for each of them check the min of both possibilities and then just calculate the answer.

entertained the first and last element case by combining them (they become a segment of 2 or greater elements).

Edit: it should start and end at 1 (i didn't entertain it)

Maybe your solution performance will improve if you flip the dimensions?

Also probably make K smaller, the cost of query 1 is much more expensive than query 2.

Also remove the optimize pragma, I found most of the time Ofast actually slows things down a lot.

Because CF is too fast. As you can see, even $$$n$$$ is $$$500,000$$$, there are several participants run in just 1 sec.

My solution on G n sqrt n log n fit in 3 seconds with n = 4e5

+1

Use including exclusion, I calculate the number of ways to sort each part and minus the number of ways to sort both parts. The answer initially is n!.

Let's say desired number is $$$X$$$. If you could query only one number, you would send 0 and get $$$X$$$ XOR 0 = $$$X$$$ as an answer. If you sent some degree of 2, you would get $$$X$$$ XOR $$$2^k$$$ = "$$$X$$$ with its k-th bit reversed". Generally, if you send an arbitrary number, you would get $$$X$$$ with some of its bits (the ones that are set to 1 in your number) reversed. The only problem is that you do not know which bits are reversed when you send 100 numbers.

My idea was the following: use only odd bits in the first query and only even bits in the second query. So, the first query will contain 100 numbers with some of their odd bits set to 1, and the second query will contain 100 numbers with some of their even bits set to 1. Then you will get the following as answer:

   X = 100010110
ANS1 = 101000111 // 1st, 5th and 7th bits were reversed; XOR happened with 1010001
ANS2 = 100011100 // 2nd and 4th bits were reversed; XOR happened with 1010

When you compare ANS1 and ANS2, you will see that they differ only in those places where bit reversal happened:

ANS1 = 101000111 // 1st, 5th and 7th bits were reversed
ANS2 = 100011100 // 2nd and 4th bits were reversed
         ^ ^^ ^^

That means that ANS1 XOR ANS2 (1011011) will give you the set of bits that were XOR-ed in both queries. Then you just need to check which two numbers among those 200 you sent form the same set of bits. In other words, find $$$x_i$$$ from 1st query and $$$y_i$$$ from 2nd query such as $$$x_i$$$ XOR $$$y_i$$$ = ANS1 XOR ANS2. Then you can find X as ANS1 XOR $$$x_i$$$ or ANS2 XOR $$$y_i$$$.

Let the input results be N and M and the answer be A. Then, we have two equations: A ^ X = N and A ^ Y = M, where X is in the first output set and Y is in the second output set. Taking the XOR-sum of these two equations gives A ^ X ^ A ^ Y = X ^ Y = N ^ M.

Then, if we can find two sets of 100 numbers such that there are no two distinct pairs of integers, one in the first set and the other in the second set, with the same XOR, we're essentially done: find N ^ M, and then use that to find the unique X ^ Y such that X ^ Y = N ^ M.

This is fairly easy--just take 100 integers that make use only of the first seven binary digits as the first set and 100 integers that only use the next seven binary digits as the second set. One simple construction is to use 1 through 100 as the first set and 1 * 128, 2 * 128, ..., 100 * 128 as the second set. From here, we can iterate over all pairs of these integers to find the appropriate X and Y. Afterwards, reconstructing the answer is easy--if A ^ X = N, then A = X ^ N, so once we know X we can simply print X ^ N.

Where exactly in the problem statement is it written that you must print one integer per line? :)

Here's another. http://codeforces.net/gym/100739/problem/B

Change every int to long long int (you can leave int i), and you will get AC.

did u get anything !!!

sorry)

Greedy seems correct to me. Basically, you only need to take care of separate segments that look like ...100001..., and you either select to cover it all at height 2, or choose to dive at least once to the height 1. But if you go to height 1, you already spend 2*a, and there is no reason to put any additional pillars on this segment. It is just that DP is a safe bet :)

My solution greedy: https://codeforces.net/contest/1207/submission/59310430 DP code faster than greedy. I think so..

check this submission https://codeforces.net/contest/1207/submission/59283633

Try this snippet:

5 50
0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0

The answer is not -1.

Brute Force!!!

Try all possible sizes of hamburger and chicken burger and check if you have enough buns, beef patties, and chicken cutlets to make them both if you do save the result and at the end output the maximum.

JUST CURIOUS

Does anyone have an O(1) solution excluding the number of queries?

HOW? MAXSUM = MAX(yi)*q <= 1000*500000 < 1000000000 (it must be int) Your solution get WA only because you should get sum of all numbers from 1 to 500000 which have remainder y, but you sum all numbers from 1 to q which have remainder y

2000 revisions wut

For those who are curious. Comment You can't hide it by 2000 revisions.

You can use modified suffix array algorithm to build something like suffix array on the given strings.

The modification you need in the suffix array is that on the $$$i$$$-th iteration you should compute the equivalence class for every vertex $$$v$$$ of the ``string tree'' (the class of the suffix of the $$$v$$$-th string from the input which has length $$$2^i$$$).

UPD: Forgot to mention that you should consider reversed strings in this approach to build suffix array correctly.

Hey I solved it only with Aho corasick, Can you explain your approach with segment tree? Mine is solved ofline and having an array of frequencies for each string (like all the matches from the root to current node). So basically I do a dfs traversing the tree and process the current character of the current node, and then answer all queries. In order to update the array, I iterate over the fail links in the aho corasick. The code is very simple if you know Aho corasick. It works in N*sqrt(n). code

I solved it with centroid decomposition.

We only need two string algorithms. Denote $$$n = |STR|, m = |PAT|$$$:

1. O(n log n) preprocessing, O(m log n) counting of appearances of pattern in string
2. O(n) counting of appearances of pattern in string

I did the first by binary searching suffix array, and the second is just KMP.

Given these two, we can solve the problem with centroid decomposition. First read all queries and place them into the nodes in the tree where they occur. Find the centroid of the entire tree. Preprocess the string from the root to the centroid. Then DFS all queries in the subtree of the centroid, and add to their answer the number of the pattern's occurences in the preprocessed string (with algorithm 1), and its occurences overlapping with the end of the string but not contained in it (with algorithm 2). Note that we only have to process a string with length 2m in algorithm 2.

After processing the centroid, clip its subtree away from the original tree and recursively solve its subtrees. Repeat until the original tree is empty.

This correctly answers the queries by dividing the query string into multiple strings $$$S = S_{1} S_{2} \dots S_{k}$$$, and calculating its appearances inside each individual $$$S_{1}, \dots, S_{k}$$$ (with algorithm 1) plus its appearances not inside any individual $$$S_{i}$$$ with algorithm 2.

Total time complexity is $$$O((n + m) \log^{2} n)$$$ where $$$m$$$ is the total length of the query strings, since due to the centroid decomposition we do the preprocessing of algorithm 1 on every character at most $$$\log n$$$ times, and we do the matchings with algorithms 1 and 2 for every pattern at most $$$\log n$$$ times. Note that if a suffix automaton was used instead of binary searching a suffix array, we could do algorithm 1 in $$$O(n)$$$ and $$$O(m)$$$ time, bringing the whole algorithm to $$$O((n + m) \log n)$$$.

Code: 59351316. My submission during the contest TLE'd due to doing $$$O(n \log^{2} n)$$$ suffix array construction.

Can't agree with that.

Model solution with ints replaced by long longs works in something like 2.2s.

My solution with long long works in 2s (59309544)

However, just because of the adrenaline of the contest, I couldn't notice that long long wasn't needed.

For large x, you can easily accumulate all values in a (There are about 500.000 / x indices with remainder y).

For small x, this is not suitable. But for a small x, you can maintain a 2D-Table (i,j) := Sum of all values in array slots with index % j == i. Updating this table for a single query takes j steps.

Now use the sweet spot K = sqrt(n) to decide if x is small (about 700 for n = 500.000, but depending on the constant factors of both sides this value can be shifted 'slightly' between at least 400 and 1000.)

Update: - the array in O(1) - the 2D-Table in O(sqrt(n)) is about 700 Query: - Large x (x > K = 700) in O(n / x) is about 500.000 / 700 =~ 700 - Small x : query the table in O(1)

For n queries you get a total of O(n sqrt(n)).

deleted (I am not right)

allPermutations = n!

permutationsSortedByA = multiplication of count of first value in pair

permutationsSortedByB = multiplication of count of second value in pair

permutationsSortedByAandB = multiplication of count of each unique pair