You have some Russian (I guess) in "557C — Arthur and Table" 's description.

Taking min of 3 values sounds easier than doing bin.search in B:)

wow what a quick editorial compared to the last one :) some statements (in problem C editorial) is still in russian..

Can someone please explain C in more details?

quickest editorial ever

Problem statement was not very good. :(

so the array size is the silliest mistake in history, Why the hell did I get TLE instead of RTE for this code !!

F*king precision error!!

This is how I solved D.
1st thing to notice was that only 3 edges are sufficient to create an odd cycle.
Case 1: Edges needed 0. Just check if a graph (every component) is bipartite or not. If it is not than the graph contains odd cycle. Ans is (0, 1).
Case 2: Edges needed 1. For this case color every component with 2 colors. Lets say we use A, B to color the nodes. If two nodes have same color than we can add edge between them to create an odd cycle. So ans for this case is (1, naC2 + nbC2) where na is the no.of nodes with color A and nb is the no of nodes with color B. We need to sum this for all components.
Case 3: Edges needed 2. For this case do dfs to count no of components of size 2 and size 1. Ans for this case is (2, 4 * two_cntC2 + two_cnt * (n — 2 * two_cnt)). Every two components of size 2 gives 4 different ways. We also add the ans for the case where individual node components are present which is basically equal to two_cnt * (n — 2 * two_cnt).
Case 4: Edges needed 3. That is every node is disjoint. Ans is (3, nC3).

Second problem was wrong because of a single word; :(

It must have been,

cout<<fixed<<answer; instead of cout<<answer;

used it after contest and got accepted. :(

This is just wrong, my submission for B during the contest 11860848

And after the contest the same code along with fast IO 11867502

I spent about an hour trying to debug my solution when there was nothing wrong. Isn't CF supposed to be non-IO centric. This is unfair, Binary search timing out due to Fast IO.

Can anyone explain why this code 11861412 give me WA on test case 8 [problem B] ? and how can I repair it?

Problem E can be solved in O(n²) time. You can read my solution (11862688) if you interested in. (I've used that alphabet size is equal to 2, but it is easy to fix it)

Have you any time to debug my Error. Why my code gives wrong ans ? (http://codeforces.com/contest/557/submission/11868836)

Hash can be also used to find if a substring from i to j is half palindrome or not.

Well, I solved problem C a little differently.

First we sort the legs by their lengths in ascending order (the energy values don't matter). Then we split the sorted list into blocks, where the legs in the same block have the same length.

length: 1 1  2 2  6 6 6
energy: 5 5  4 8  2 3 3

After that we iterate over every block. In iteration i, we try to find the answer when the legs in block i are the longest remaining.

In iteration i, obviously, all legs in block i must be kept in order to find the optimal answer. And we must remove all legs in blocks from i + 1 to block-count (since legs in block i are the longest remaining), and keep at most block[i].size - 1 legs in blocks from 1 to i — 1 (to keep the table stable). Therefore the answer equals to
total energy of block (i + 1)~block_count + total energy of block 1~(i - 1) — total energy of the (block[i].size - 1) largest elements in block 1~(i - 1).

For the first and second part we can either use partial sums or calculate while iterating. For the third part, we can use a std::multiset to store all previous legs' energy values. For any k, the k largest elements can be accessed by just iterating k times in the multiset. Asymptotic time complexity is... , I think?

My code (written rapidly during the contest and may not be so elegant): 11859771

I have changed the type of array c ( 11867935 ) to long long and the code gets Accepted (11868444)! Can anyone explain why?

I'm wondering why this submission got TLE for problem B. I believe the complexity of this solution is also .

Please improve the English translation

Can someone, please, tell me what's wrong with my code for C? It gives correct answer with all the small cases so I cannot debug it. At least some test case that won't pass with it.

I wrote a lot of comments to make it easy to understand: http://codeforces.com/contest/557/submission/11870567

The idea is basically the same as the author:

1. Precalculate cost of removing all legs of larger size
2. Iterate over each leg size, removing larger ones in O(1)
3. Keep a Priority Queue with the legs of lower size to obtain the largest ones in lg(n)
4. Obtain from the priority queue a number of legs strictly lower than the number of legs of the current size (which won't be deleted)
5. Minimum Energy Used = min(currentMin, energy of larger + energy of lower — energy of non-removed legs

Thank you very much in advance!

Who can explain me why the compiler reterning wrong answer to this example: 500*3*71199.
This will be 106798500, but it says that my programm reterns 106799000 even with this if (n == 71199) cout << 500.0*71199.0*3.0 << endl;
The submission: 11870868

can you please provide codes ?

In second question B --> we can do without binary search ie just be greedy :)

We can even do it more simplified as let say g=a[1] and b=a[n+1] (after sorting 1 based index) then just have 2 conditions if tc = (b*0.5*n+b*n) --> b*0.5 maximum girl cup can have condition being b*0.5 <=g if not so then directly (g*n+2*g*n) is the answer. for case when ans>w take ans=w. that's it :) Here's my AC code — http://ideone.com/1POnoF

http://paste.ubuntu.com/11801550/

I'm getting TLE in E problem. i have a matrix named pal. pal[i][j] = 1 means substring that starting from i and length is j is half palindrom.

i calculate matrix with complexity n^2 and then i find what string is.

i do that with three vector. i wont explain more. i think code is clear.

but the problem is why i am getting TLE ? can anyone tell ?

I solved C in O (N log N ). Here is the algo :

1) In a multi set (or any bst like structure) , store all the legs with their energies as < length, energy >, call this as M. Let total weight of all legs be TOT.

2) For all distinct lengths in this map , assume that the table is going to be built with this length as maximum length, call this length L. Let there be total of CNT number of these legs with length L. Now what you need to find is CNT-1 legs with max energy and length less than L. This can be done using a multiset for energies — once you have crossed a length, you insert all the different energies for this length into it, call this multi set as W.

3) Find the net energy value of all legs of this table = ET and update answer with ans = min(ans,TOT-ET).

Complexity analysis : 1) Creation of M = O (N log N)
2) Finding CNT for all distinct lengths — O(N)
3) Creation of W = O(N log N)
4) Selecting CNT — 1 legs of max weight from W = O (N)
Because worst case, we can have sqrt N distinct lengths occuring sqrt N times and so we will have to go through sqrt N max energy legs for each of the sqrt n lengths = O(sqrt n * sqrt n) = O(n)

Soln link — http://codeforces.com/contest/557/submission/11872727
PS : During contest, in the last while loop, I wrote "it1" as "it" and unfortunately "it" was also a variable in that scope so that caused WA on some pretest. Silly typo :\

I am new here. What should I do if I cant understand the solutions even after reading the editorials? Any tips?

fcspartakm, I understand both solutions, greedy and bs, but I always had a doubt in binary search with limits of type double. Can you give any tips, did not submit to the binary search but understood perfectly, the only question is in the loop breaks.
For example: l=min of search, r=max of search, EPS=1e-6 how shall I compare them to complete the search? so? l-r<EPS
I wanted to know, as they do this test? or rather, what better way to do it?

Thanks for the interesting problems :)

For Problem C Can anyone please let me know why i am getting WA for the first test case while the code is running fine on my system atleast for the first three cases.11875338

I am maintaining a set for the table lengths'(st) and another set to store the energy levels for a particular length(pq[]). The array cnt[] stores the number of occurrences for a particular length.

The loop basically tests for three possibilities.

temp=n
while(temp>2){
it=st.end();
if(cnt[*it]>temp/2)   //temp is used to store the current number of legs
   print ans

else if(cnt[*it]==temp/2)
   //find a length<*it with the minimum most value for energy to be incremented to answer.
   //let this be denoted by len
   print ans+len

else
   //increment the ans with all the energy levels that correspond to the current length
   temp-=cnt[*it]; //decrement the current list of legs
   it2=pq[*it].begin()
   while(it2!=pq[*it2.end())
      ans+=*it2;
      it2++;
st.erase(it);
}
  
   

After I read the editorial, problem A is much easier than I think :((

Thanks for the editorial. First problem could also be solved with complexity o(max(max1-min1,max2-min2,max3-min3)). My friend submitted using this method and got accepted. But since we can solve it with o(1) like in the editorial I think that solution is kinda slow.

Now we need to use dfs and try to split every component in two part

Can someone explain this part of problem D?

In 557B — Pasha and Tea party what is "lf" and "rg"?

Why doesn't the tutorial appear with the problem statements? Would I always have to navigate to the blog to see the editorial? How come some contests have tutorials appearing with each problem statement?

For 557C, we can use the same idea to find the solution without too much thing to compute.

The idea is (reiterating author's approach): Let's say we want to keep legs with length k. All legs length greater than k must be removed (otherwise k is not the maximum), the remaining is to make sure removal of legs length less than k requires minimal energy.

Observation: If there are P legs whose lengths are less than k, and there are Q legs with length k. You need to remove at least P - Q + 1 legs whose lengths are less than k to make the table stable.

Observation: By above, you need to keep at most Q - 1 legs whose lengths are less than k to make the table stable. Otherwise, there are at least Q non k-legs with Q k-legs, and k-legs is obviously not the majority. Table is not stable.

Observation: Remove legs with minimal energy is equivalent to keep legs with maximal energy.

So, you need to compute two things: total energy to remove (now means keep) k-legs, number of k-legs. Enumerate all possible maximal k, get the keep energy for k-legs, plus get the sum of the largest Q - 1 energies of legs whose length is less than k. The way to do it is similar to the O(nd) approach described by author, but we take the exact opposite values. Find the maximum values among all choices of k, get the answer by total energy — this max energy.

Doing so does not require suffix sum.

We check at a node if sum[toa] <= k.

Let us say sum[toa] is less than or equal to k. Then we go to node toa, now, for all nodes sum[toa from new node] will also always be less than k.

So, in such a case k will never become less than or equal to zero.

The how will the algorithm terminate?

I found the statement of the Problem A to be not clear. I could not understand the fact that if we already have max possible A diplomas, then try finding max possible B diplomas and further max possible C diplomas.

For Problem D of the contest I have implemented the idea of DFS mentioned in the Editorial but i am still getting WA on the test 31. http://codeforces.com/contest/557/submission/11901124 I would be grateful if anyone could point out my mistake and point me in the right direction.

To solve B, I just needed to sort them and write only 2 lines and it's done, no need to iterate on any thing, the answer pops right up. My solution: 11927301 Complexity: O(n.log(n)) for the sorting

I was tricked by myself when I attempted to solve D.

The definition of odd cycle is obvious: Any graph that is not bi-colorable iff it has odd cycle (proof omitted). So if the graph has odd cycle it's done, we don't need to add any edge and this is the only way to achieve minimum (thus 0 1). Note that bicolorable graph is bipartite.

The solution remains to categorize answers for different class of bipartite graph. Note that you need at most 3 edges to form an odd cycle in any cases, so just think about when you need to answer 1, 2, and 3.

Case 1: when minimum = 3. It means you need to form a triangle by picking three vertices. This also means that there are no edges, thus maximum vertex degree = 0. In this case, answer is to pick any three vertices, which is .

Case 2: when minimum = 2. It means that no vertex has at least two edges (otherwise minimum = 1 by joining two vertices from the two edges to form a triangle). Which implies that maximum vertex degree = 1. To form a triangle, we must use any of such edge (u, v) and find other vertex w and use two edges to form a triangle. Note that since maximum degree = 1, all m edges are the required edge. So the answer is m × (n - 2) (for each edge, pick other vertices to form triangle).

Case 3: when minimum = 1. This means that maximum degree is at least 2. This is also where I got tricked. In this case, we don't just want to count number of ways to form triangle, since one can add an edge to form an odd cycle. Consider this: W-B-W-B-W, where W means a white vertex, B means a black vertex. One can add just on edge, that connects the first and the last W, to form an odd cycle with length 5. Given this, the answer is much simpler: notice that for any connected bipartite graph, connecting any two vertices of the same side breaks bipartite-ness, thus odd cycle exists. So the answer is simple: for each bipartite connected components, the answer for that component is the number of way to connect two vertices on the same side. Suppose the bipartite graph has U vertices on the left, V vertices on the right, the answer is .

Indeed, what if the problem is like: find the minimum number of edge added to form a triangle, and how many ways to do. When the graph is not bipartite, I think it requires matrix multiplication. If the graph is bipartite, the answer remains the same when the minimum edge added is 3 or 2. When minimum edge added is 1, I can't come up of anything that is faster than O(n²).

We can use dp for checking half-palindromes.

Suppose our good[][] array works correctly for substrings of length 1,2,3...i-1 Now we have to consider the substrings of length i and update the good[][] array.

It's obvious that good[i][j] = 1 if and only if,
- char at position i equals char at position j and
- (i+2 > j-2) or (dp[i+2][j-2] == 1)

Link

I think the solution of problem A is probably wrong.
Like for the first condition max₁ + min₂ + min₃ ≤ n, which means n - min₂ - min₃ ≥ max₁.
And it saids the optimal solution is (n - min₂ - min₃, min₂, min₃), which actually invalid.

I have a O(N^2 + N^2 log N + N^2) solution for problem E.

Firstly, finding all the half-palindromes by O(N^2) brute-force. Then, sorting all the suffix by their indices with O(N log N) algorithm. In fact, it can be optimized by using suffix array algorithm, and this will come up with an totally O(N^2) algorithm for this problem. Finally, sweeping the suffixes for counting the k-th sub-string in O(N^2).

And this is not depended on the number of kinds of alphas in the string. :) I don't know if my solution is strictly right, so comments are welcome. 11894668

Can anyone, please, explain Problem E ?

With all due respect, the explanation offered in this editorial is not clear at all.

I understand the part where we determine which substrings are half-palindromes as I did myself but I don't get the part where I'd have to use a trie. I tried to use a trie by myself but I think it's O(n³) .

It would be really nice if someone explains the approach of this editorial!

How to solve C if 1 <  = d_i <  = 10⁵?

Can anybody give the the idea of Div 2 C, when the range of d_i can be anything and not just 1 ≤ d_i ≤ 200