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:)

Недосообразил в задаче D, как найти кол-во способов, если ответ надо добавить 2 ребра. Все моральные свои силы я истратил на задачу C. Обидно:)

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 :)

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.

C can be solved by treap and the asymptotic will be O(nlogn). This solution doesn't demand constrains on lengths and energy.

Can anyone Explain why this code give me WA on test case 8 ?! 11861412

how can I edit it?

thanks in advance.

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

Также нам понадобится массив cnt[]. Спасибо за быстрый разбор, но читается это с трудом. Сразу в голове возникает куча вопросов "Какой кнт, зачем кнт, что это за кнт массив?"

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 used to find if a substring from index i to j is half palindrome or not.

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);
}
  
   

Задачу С думал так же решать,как и в разборе,но испугался ограничений на время (1с). Подскажите, каким образом решение O(n*d+n*logn) может пройти на Free Pascal за 1с? Насколько мне известно (опыт+инфа) 10^6 итераций ~1 сек.

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"?

You have mistake in Problem A: Not <=, it will be right if write >= !

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?

Why TLE O (700) ? 11885455

UPD: because of double with cin :( 11885605

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.