minute

You could reach 2000 after this round. Set your dream high.

is it possible to achieve 1300 for me

Your rating curve is so smooth lol

m=0; c=1400; y=m*x+c;

1. Process the exponent (i) from 0 to 62 (actually 60, but it doesn't matter)

2. If the i-th bit of n is set, then find the smallest existing box that is at least 2**i, then divide it by 2 until it is 2**i, creating two other boxes in each division. Then use a box of size 2**i.

3. Then use all k boxes of size 2**i to create k/2 boxes of size 2**(i+1)

SUM = sum of all Ai. So if SUM < n answer is 0. else SUM = n + reminder. now go from big powers to small. a = 2^k. if reminder>=a so reminder-=a else if n>=a so n-=a else cnt[k-1]+=2 and start iterate on k-1.

Greedy. First for each power of 2 count how many boxes with this number we have. Then start looking at the bits of n, starting from the lowest one. If this bit is 0, we just go to the next bit, and in the meanwhile try to merge the boxes with corresponding size (2^i) to "create" boxes with a higher power of 2. If current bit is 1, we use the box of size 2^i, if possible. If it is not possible, we take the "nearest" box with bigger size and divide it until we get a box of the right size.

You just need to construct all of the bits of number 'n' . Start from constructing lowest bit .for constructing ith bit first check if it can be constructed by numbers smaller than or equal to 2^i . Else you need to divide some number 2^j , j>i and j should be closest to i , see if this is possible .if no for some bit then -1 else answer is sum of number of divisions .

of course above is just rough idea but you can go through the submission and ask if you have some doubt .

submission 70903270

1 a

I think you should check your code in the test case if the string length = 1.

Unfortunately, we had to put tight memory limits to disallow solutions with dynamic connectivity offline approach.

By the way, which approach uses $$$O(nmc)$$$ memory and cannot be modified to use $$$O(nm)$$$ memory?

You should do (1LL<<smth) instead of (1<<smth) because it overflows.

Now i got my mistake...I consider if any number x is divide by 2 then number become x/2. Then i consider only 1 frequency of x/2 But actually Now we have 2 frequemcy of x/2. I misunderstood the problem..

Which problem from this round was copied?

Got it, i'm now tring to solve ApIO18 (LOL

not slow

It's centroid decomposition with convex hull trick. As TL is 6 seconds, it should pass.

I tried too, but I had an error in my code during contest that I couldn't fix in time. However, after fixing it it gave me WA, i think I'm bad implementing the dynamic convex hull trick.

For each possible split t1 + t2 of the string t, dp[i][j] = "minimum prefix of s such that it contains non-intersecting i-th prefix of t1 and j-th prefix of t2"

First try every split of the string t and then dp[Position of current symbol in the string s][length of the first subsequence] — maximum number of symbols in the second subsequence.

(Mine is kind of weird, maybe there is a better one)

Assume the first subsequence is of fixed length N. Then dp[i][j] = after taking the first j characters of string s, it is the largest length of second subsequence, given first subsequence has length i. If dp[|s|][N]=|s|-N, then we output YES. Now repeat for all possible N. If no such answer is found, output NO.

Submission: https://mirror.codeforces.com/contest/1303/submission/70902911

...

...

Well, variable 'n' has no certain value in your code.

for (i=0; i<n && s[i]=='0'; i++);

here variable n is not defined. Use s.size() instead.

        if(g>=b)
            cout<<n<<"\n";

i cant understands this, you can see my code

else if((temp%g)!=0)
{  
                cout<<(tp*b)+temp<<"\n";
}

You need to check if the answer is no less than n, as in the following "else" statements. (Input: 10 3 4, Output 9, Answer 10)

Imagine waking up and half of them had been hacked, just kidding :P
Good night.

If there is a cycle then there is no solution. Checking if there is someone with degree 1 is not enough.

Your code does not correctly check the degrees > 2. abacad gives YES.

nvm, made silly mistake of using float instead of double

if(a.size()!=2){cout<<"NO\n";continue;} But it can be string like this "abcbdbeba", in set a will be 'a','c','d','e'

ignore previous post, sorry if(a.size()!=2){cout<<"NO\n";continue;} if your input just one char like "e" so size of set a will be zero, but you output NO.

size of of vector a can be 4 if there are two connected component in graph with more than 1 vertices. it can be any even number.

Represent the keyboard as a graph: letters are vertices and edge between vertices 'a' and 'b' means that 'a' and 'b' should stand next to each other in the keyboard. You can create this graph simply by iterating through the input string and adding an edge between each pair of adjacent letters.

The trick here is that the keyboard can satisfy the conditions iff it is a linear graph (maybe with some vertices with degree 0). The only thing you have to do is to check if the graph you have built is linear. The simplest way to do so is to make sure that, if all isolated vertices are removed, it is either empty or contains exactly two vertices with degree 1 (these will be the first and the last letters of the keyboard), and the rest of the vertices have degree two. If the graph is indeed such, you can output the keyboard by doing a dfs from one of the ends of this graph and then append all isolated vertices in the end.

Actually, you can perform this approach without bitset. Observe we only need to hold the best possible length for the second part for any given length of the first part. Thus we only need dp[i][j]=best length of second part for each split, so O(n^3).

Submission: https://mirror.codeforces.com/contest/1303/submission/70902911

You can have more bad pavements than good pavements during the days, it's only at the end that you can't.

it takes 500000 good days and 499999 period of bad days 1*500000 + 499999*1000000=499999500000

how do people solve problems that fast QoQ

Check this 70858282

[user:Um_nik]Yes, you should look into this.

totally agree with you bro !! Also , they make 100 announcements during the contests , they better pay more attention while making the questions!

In this contest problem C can solved with graph theory, E is easy DP so what's the problem?

Check if "babacncd" works.

Let $$$C[2^k]$$$ be the number of boxes with a size $$$2^k$$$. Let $$$Small[2^k]$$$ be the sum of box sizes smaller than or same to $$$2^k$$$ (i.e., $$$\sum_{i=1}^k 2^i \cdot C[2^i]$$$.) Iterate $$$i = 1$$$ to $$$maxbit$$$ of long long signed integer. If the $$$i$$$th bit of $$$N$$$(the bag size) is $$$1$$$, then we have to fill bags with boxes using their sizes are smaller than or same to $$$2^i$$$. It is possible when $$$Small[i] \geq 2^i$$$. But if not(i.e., $$$Small[i] < 2^i$$$), we have to divide a bigger box into the size $$$2^i$$$. Dividing procedure is quite implementive. I hope my submission would be helpful. 70933987

It gets wrong answer on my computer, too. :(

The problem said that you shouldn't minus one on d.size(), the data type of d.size() is unsigned integer, which means you can't get a negative number by doing any calculation. You'd better put it as pt+1 == d.size(), which is equal to your original expression.

If it's the first time you used two account to check your answer, I think it won't get your account banned . As it says in statement, 'In case of repeated violations, your account may be blocked.'.

However, you should trust the cheat detection system and don't do that again.