can anyone suggest approach to solve this problem?

https://codeforces.com/gym/102157/problem/3

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 198 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 164 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Monogon | 159 |

can anyone suggest approach to solve this problem?

https://codeforces.com/gym/102157/problem/3

here, non overlapping means only indexes are non overlap.

for example,

1)

s = “abcab”

ans = 3*2 = 6

two palindromic sequence are “aca” and “bb”

2 )

s = nriatdoiarn

ans = 5*5 = 25

two palindromic sequences are “nitin” and ( “radar” or “raoar”)

3 )

s = “abcdef”

ans = 1*1 = 1

please share your solution.

Easy Version link : https://stackoverflow.com/questions/53663721/find-the-maximum-product-of-two-non-overlapping-palindromic-subsequences

Given an array A[1…N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i…(i+k-1)] and A[j…(j+k-1)] such that i+k-1 < j and swap A[i] with A[j], A[i+1] with A[j+1] … and A[i+k-1] with A[j+k-1].

Example:

For n=6

6 7 8 1 2 3

Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays

we can get 1 2 3 6 7 8 , that is sorted.

How can we figure out minimum number of swaps in most effective way ? and what is minimum time complexity ?

hackereath link :

https://www.hackerearth.com/challenges/competitive/japan-national-programming-challenge/approximate/swap-and-sort/description/

Problem :

This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.

Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.

In another word, you have to divide array into M subset such that maximum sum of subset is minimized.

Input:

First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.

Output:

For each testcase, print the minimum number of maximum chocolate a child get.

Constraints:

1 <= T <= 100

1 <= N, M <= 10^6

1 <= A[i] <= 10^8

Example:

Input:

1

4

12 34 67 200

3

Output:

200

Explanation:

Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.

Another Corner Case : n = 5 and M=3

array is : [ 3 4 5 5 8]

answer is : 9

how to solve? i didn’t figure out.

how to solve this problem?

problem link: https://www.hackerearth.com/problem/algorithm/gcd-on-tree-6c5cdfba/description/

how to apply centroid decomposition in this problem? or any other approach to solve this problem?

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/04/2020 00:01:27 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|