Блог пользователя Melnik

Автор Melnik, 2 года назад, По-русски,
Tutorial is loading...

First accepted Div1: 00:00:58 kriii

First accepted Div2: 00:00:59 Baneling3

Author's solution
Tutorial is loading...

First accepted Div1: 00:03:30 egor.lifar

First accepted Div2: 00:04:43 Baneling3

Author's solution
Tutorial is loading...

First accepted Div1: 00:08:30 nuip

First accepted Div2: 00:10:19 ColdSu

Author's solution
Tutorial is loading...

First accepted Div1: 00:15:47 arsijo

First accepted Div2: 00:18:01 ColdSu

Author's solution
Tutorial is loading...

First accepted Div1: 00:43:18 Deadwing

First accepted Div2: 01:05:21 CountOlaf

Author's solution
Tutorial is loading...

First accepted Div1: 00:16:33 mcfx

First accepted Div2: 01:12:52 Nisiyama_Suzune

Author's solution
 
 
 
 
  • Проголосовать: нравится
  • +98
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

how do u prove that the solution to D is ?

When u are processing dp, it seems like depending on how many prime factors i has.

So i think it should be ?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    No, because you only need to choose the smallest prime factor each time.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    If you go one by one and factor every number from l to r, the running time is indeed . However, to speed this up, we instead use a Eratosthenes sieve-like approach: from l to r, look at all the multiples of 2, then all the multiples of 3, then all the multiples of 5, etc.. The running time is thus which was proven by Euler (?) to be approximated by .

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why is this solution giving tle whereas this passes.

      In first soln I am storing all the distinct primes of a no than calculating the ans whereas in second soln I am dividing by smallest prime factor each time.

      I also calculated the total no of times the loop is executed in both the solutions and the first soln has less execution.

      Can anyone help on this ?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Would you mind sharing why most people got E WA'd by using dp[sprefix][xcnt][flag]? I tried to come up with a counterexample but nevertheless failed.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can anyone please tell me what I did wrong on problem C so I got WA on test 58 :(

28220911

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    The question asks you to find the sum of cost of vouchers whose intervals don't intersect. You don't entertain that possibility. You just find the minimum cost of the required interval length whose starting point is before it, but that doesn't guarantee that they don't intersect.

    For eg, Your code fails on:

    3 3
    1 2 1
    1 1 1
    2 2 3
    

    Answer is -1 whereas your code prints 2. Your code takes two intersecting intervals which should not be the case.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody help me please ? :)

C solution

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    it gives 3 instead of 2 on foll test case:- 3 6 1 3 1 4 6 2 7 9 1 Mistake in ur code is that when u binary search,according to your code you should check all possible coupons for whom st>last and time==left. but say if a[mid] follows the condition it may be possible that a[mid+1] also follows these 2 conditions and furthermore may have lower cost causing the error.But u change r to mid-1 hence never searching for lower cost in indices greater than mid.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me what I did wrong on problem C so I got WA on test 58 :(

28220911

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

It's embarrassing although my solution for D passed I couldn't prove it before reading the editorial. Thanks!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

I dont know why i got E wa on test 172,which is the last case. Can any one help me??? My submission

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

For people who are still struggling or trying to understand problem c solution and not able to understand editorial (like me :p ), i want to explain it since i solved it now.

Brute force solution is O(n^2) which i think everyone can get. We want O(n) or O(nlogn).

Approach:
1)store interval {l,{r,cost}} in vector<pair<int,pair<int,ll>>>a
2) First sort the intervals vector<pair<int,pair<int,ll>>>a wrt left point.
3) Iterate over vector a and store duration in another vector vector<pair<int,int>>min_value[N] (It contains left point and cost). This vector will contain information about all intervals with a specific duration.Good thing is min_value[d] will contain interval information in sorted wrt left point (isn't it ?)
4) Now we will find our answer similar to our bruteforce approach. Bruteforce is to iterate over all intervals , and for each interval we will take O(n) to find min_cost. We are trying to reduce this O(n) to O(logn) to make our solution O(n logn).
5) So start iterating , choose first interval , we know it's duration d , our need = x - d; we have intervals in our vector min_value[need] which is sorted wrt to left point , we want to find that index in min_value[need] which has it's left point greater than current interval's right point.
we can find that using binary search and obtain minimum cost. There will be many possible interval satisfying our interval condition , we can choose any with min_cost , so we also need to precompute min_cost in all intervals ahead of that index (similar to prefix sum)
Here is my solution , see this everything will make sense.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    codenote Thanks for the explanation :) But I have a small doubt in your code.

    	// this is the crux to find desired cost in O(1) :)
    	for(int i=0;i<N;i++)
    	{
    		for(int j=min_value[i].size()-2;j>=0;j--)
    		{
    			min_value[i][j].second=min(min_value[i][j].second,min_value[i][j+1].second);
    		}
    	}
    

    Consider a case where there are N elements in the array only 4 distinct values as their cost so your min_value[j].size() will be ~ N/4. Now you are doing it for all N so it will be O(N^2) right ? Correct me if I am wrong!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    helpful explanation.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    your explanation helped :) But one thing is not clear to me. Can you explain this to me?

    There will be many possible interval satisfying our interval condition , we can choose any with min_cost , so we also need to precompute min_cost in all intervals ahead of that index (similar to prefix sum)

    how and why does this work? thanks :)

    EDIT: I got it now. :D

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It looks like author's solution is a bit different. He adds to a processing queue two kinds of tuples: {{l, Type.ForPossibleAnswerCalculation}, {r, cost}} and {{r, Type.ForMinCostHashTableUpdate}, {l, cost}}. Queue sort arranges tuples of the first kind by left border and the ones of the second kind by right border. Because at the moment when you process a travel that starts at li all tuples with r < li already processed, bestCost[needLen - curLen] contains best possible value.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't understand this part in your code —

    `// this is the crux to find desired cost in O(1) 
    	for(int i=0;i<N;i++)
    	{
    		for(int j=min_value[i].size()-2;j>=0;j--)
    		{
                    min_value[i][j].second=min(min_value[i][j].second,min_value[i][j+1].second);
    		}
    	}`
    

    Why are you changing the costs attached to the intervals ? Please explain

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Problem D, this code, gives TLE on test 18, I think it has the same time complexity as intended. Could anyone help me with this. Thanks.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your code's complexity is R.log(R) whereas the intended complexity is R.log(log(R))

    No need to divide x by all its factor to find dp[x]. Just divide it by its smallest prime factor.

    dp[x] = dp[x/sp[x]] + (sp[x]*(sp[x]-1))/2 will work, sp[x]: smallest prime factor of x.

    Preprocessing the sp array is O(R.log(log(R)) and the calculation of dp will be O(R).

»
2 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Melnik, What if for C we consider the following solution:-

1) We sort the vouchers in increasing order of the cost. O(nlogn)

2) Then for each voucher Vi we find a Vj (j>i) such that the intervals don't intersect, and such that duration of the Vi+Vj is x. We return the first Vj we find satisfies this conditions.Time complexity — O(n^2)

Is the above solution conceptually correct?(Other than having poor efficiency)

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In D, "So, we proved that all di should be prime", how is it proved bcz spliting a composite number into 2 gives less comparisons?? can someone explain this

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    "how is it proved bcz spliting a composite number into 2 gives less comparisons"

    You said it yourself: splitting is cheaper. So we should split, as much as we can -> we have split it into primes.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thanks, got it!!

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi johnLate, Dont you think then even must be split in only pair of twos and odd with a triplet and all other into pair. This should result in minimum cost . However I am not getting same answer. Thanks

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Each group of a stage must have the same size. For example, you can split 15 into 3,3,3,3,3 or 5,5,5. But you can not split it into 2,2,2,2,2,2,3 or something like that.

        Example for n=15: In the first stage split into 5 groups of x=3 girls, do x(x-1)/2 comparisons for each group, then solve the problem for the resulting 5 girls. f(15) = 5 * 3(3-1)/2 + f(5) [Note: It is f(n) = n/x * x(x-1)/2 + f(n/x), it is NOT f(n) = n/x * f(x) + f(n/x)]

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O (n) solution for C 28236057

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody please help me find out what's wrong with my solution for problem C?

28233171

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For each value of i, we may have many possible values of ind but we need to find one for which cost is minimum. You are just checking the first possible value of ind only!

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the reply! However, I first sort all the vouchers according to the cost in ascending order and then I pick the first voucher. So, the first one has minimum cost.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        Say if m does not satisfies the condition, you take l = m+1 ( rembeber that if duration of coupon is greater than or equal to x than we can simply ignore them right from the start hence second condition really never makes sense as we can assume all coupon have duration less than x!) . But it may be possible that m-1 may satisfy the condition or similarly any value less than m even though m may not satisfy the condition! In your soln, You need to find out smallest index between l and r that satisfies the 2 condition!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain author's solution of C

what is the use of keeping 4th variable {-1,1} and how is bestcost being updated

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain author's solution in C. Why 2 types of queries {-1,1} and why updating bestcost online like this works.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Firstly notice that we are adding both 'l' and 'r' to queries vector as this will help us refrain from intersecting intervals. Then on the other hand we have to also keep track of whether the value is the start of interval or end of the interval, so {-1,1} are used.

    The main thing to see is that bestCost is updated when 'r' is found and ans is updated when 'l' is found.This thing makes sure that an interval doesn't uses bestCost from any other intersecting interval before "ans" is updated on 'l'.

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

HELP!!! How to FORGIVE!!

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help regarding my solution for D. It's giving runtime error on test 1. I think there is a problem with my sieve because after commenting that program runs correctly on test 1. But my sieve function looks good to me. 28250621

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Runtime error cause you are using too much memory! And even if you decrease the memory complexity, you'll still get tle anyway.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      As far I know allowed memory is approximately 1500 MB and mine uses approximately 80 MB. So I think memory is not a problem.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    See I submitted 2 solutions. With sieve 28250621 and without sieve 28250581. They both almost use same amount of memory but sieve one is giving RTE.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div 2 C wrong ans test case 25. Any help?

http://codeforces.com/contest/822/submission/28250623

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DIV2 wrong answer on test 13, but I really think it is right(binary search for len of every voucher). Anyone help? http://codeforces.com/contest/822/problem/C

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For C what I did was made a array of vectors of duration. Then while traversing the queries I know that the required duration is x-(r[i]-l[i]+1) and in duration vector I find the starting position with binary search and apply RMQ. I got runtime error on test 3. Is there anything wrong with this approach?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте!

Вчера пыталась написать программу А на питоне, мне написали: "!Time limit exceeded on pretest 5". Я не могу понять в чем проблема. Мой 1-й код на Питоне:

import math a = input().split() c = min(a[0],a[1]) print(math.factorial(int(c)))

Он абсолютно рабочий, но почему-то не укладывается по времени. Я решила, что, возможно, использовать внутреннюю функцию долго и просто написала расчет факториала. Но она тоже выходит за рамки времени на 5-м тесте. Программа 2:

a = input().split() c = min(a[0],a[1]) q = 1 for i in range(int(c)): q = q*(i+1) print(q)

Смотрю код в ответе и не понимаю в чем отличие от моей 2-й программы? По-моему считается идентично. Подскажите, что не так?

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    split() возвращает массив строк, а строки сравниваются не так же как числа, например "111" < "2"

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with hashing to find lcp in problem E? Do we precalculate hash values and then in every DP state find it in O(logN) — only binary search? Please help.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

"But if we divide this stage into two new stages, then number of comparisons is " .
how do we get this equation ?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    In first stage: There are "n/a" groups of a elements each. So comparisons are (n/a)*(a)*(a-1)/2 = n*(a-1)/2

    For Second stage: There are "(n/a)/b" groups because from first stage "n/a" elements go ahead. So comparisons are (n/(a*b))*(b)*(b-1)/2 = n*(b-1)/(2*a)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help in finding why my Div2 C is giving wrong answer.. I know my solution will give TLE but why is it giving WA.. I need to know,what's wrong with the approach,I already know it's not efficient,but I cant figure out why WA in testcase 12..

SOLUTION

My approach : I created a vector that contains duration of vacation,start time,end time and cost in that order.. Next,I sorted it... Next,starting with i = 0 , from the beginning of this vector,I find the required duration (x — duration[i]) I use lower_bound to search for this value compare all such elements having the same duration (x — duration[i]) I understand it will yeild TLE,but WA,I can't understand..Please help!!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone help me with my solution on problem C? Why is it failing on test 3?

I sort segments (l, r) by left bound, then while being in segment i, I update mincost with all segments with r_k < l_i which have not been used for updating yet.

Submission: http://codeforces.com/contest/822/submission/28257988

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with my code? I got Runtime error on problem C but I don't know why. Thank you very much! http://codeforces.com/contest/822/submission/28261279

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Problem C, I'm really amazed no one mentioned the O(Max(li, ri)) for i = 1 → n greedy solution!

The solution is only possible due to the low range of li, ri which is less than 2·105

We simply use this fact to store the vector of pairs of {ri, costi} at index li in an array called left , and do the complement of this in another array (i.e. store the vector of pairs of {li, costi} at index ri in an array called right)

Then we loop for every i = 1 → Max(li, ri) and fix our index i to be the left bound and check for every pair j at left[i] to see if we have encountered a non intersecting segment before it that has the length X - (left[i][j].r - i + 1) in an array called best for example and minimize our cost by the current which is the cost of the current pair left[i][j].cost and whatever was saved in the complementary segment length in our array best[X - (left[i][j].r - i + 1)]

After we have processed the fixed left index, let's see if there's a segment has its right index at this same index i, if so we need to minupdate the value of its length in our array best to use it in the future at further indices, and this way we're sure we can never have intersecting segments, because we query first and then update.

I hope I haven't made it much worse than the obvious O(n·log(n)) which could be due to binary searching or using a map/set to store higher ranges.

All in all, here's the link to my submission for further detail -> 28237414

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Update: Never mind! My brain did not work until I wrote the comment!

I was going through the submission 28257135 for problem E. I was wondering what is the time complexity of below two statements.

1.

	sort(u1, u1 + L, [](int a, int b) {
		return str[a] < str[b];
	});

2.

	for (i = 0, j = 0; i < L; i++) {
		if (i == 0 || str[u1[i]] != str[u1[i - 1]]) j++;
		sa[0][u1[i]] = j;
	}
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

regarding problem D in the point of all di should be prime:

it can also be thought of as: suppose number d with n1*n2 = d (where n1 and n2 >= 2 and are prime), without splitting, comparisons made are: n1n2(n1n2 — 1) / 2. with splitting, comparisons made are: n2n1(n1 — 1)/2 + n2(n2 — 1)/2 (supposing that d is splitted to n2 groups with n1 participants in each group), now subtract the second equation from the first one : 0.5((n1n2)^2 — n2(n1^2) — n2^2 + n2), rewriting the expression: 0.5n2((n1^2) * (n2 — 1) — (n2 — 1)), rewriting again: 0.5n2(n2 — 1)(n1^2 — 1), which is clearly greater than 0, so the number of comparisons made in the first equation is larger than those made in the second equation.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem C, can it be solved by sorting the vouchers by r-l+1. Then iterate through every single voucher and take it as the first voucher selected, the second one is chosen through a binary search(look for the value x-(the first selected voucher r-l+1). If it's found check if there are more x-r-l+1 values to the left and right. Check if any of them is valid and it minimizes the money needed.

My submission It's a messy solution.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me how to solve a variation of Problem C, i.e., if more than two disjoint trips are allowed? (Select T trips covering duration K) All I can think of is a recursive approach. For N trips and duration K, choose

min(cost[i] + Trip(disjoint_trips(i), K - dur[i]), Trip(remove_i_from_list(i), K))

Any other approaches would be nice. Thanks

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I understood the problem D. However, how can we come up with the idea "all di should be prime" ? Thanks you.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Observing.Try to calculate f(16), f(20)...If u had experience in olympiad maths it would be easier, because in maths many times you need to observe something, to see a pattern. So, just calculate few f-values and you will see that optimal is to choose di as smallest possible, but since they need to divide total number of people in current stage, they must be primes.

    Its important to mention that i solved a problem without this observation, only bottom up DP. Thats why solution passed in 1450 ms while 1500 ms was limit, so i was lucky.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone teach me how to prove "you can prove the fact that we should split the girls into groups by prime numbers in the order of their increasing" in problem D.Thanks a lot :)

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    just suppose a and b are two distinct prime factors of n. The number of comparisions that you want to minimize is given by the recursion formula:

    By this you can imagine the expansion for all the factors of n. For two different prime factors a and b you get to choose if a is bigger or smaller than b. will be the same no matter the choice. So just analise the first part of the expression, the . Imagine all pairwise choices for a and b among all prime factors of n, by proving that choosing a<b is better (that is, between the two options choose, for a, the smaller one), you can notice that among all pairwise choices only the smallest avaible factor won't lose to any other factor, so, since there must be a choice that minimizes (or at least equals the minimum), it must be the current smallest factor avaible.

    So what is left is to prove that for a set of two numbers, choosing for a the smaller one minimizes the expression:

    That is the same as, given two prime numbers a and b such that a<b prove that . You can rearrenge the last inequality to get ab(b - a) + (a - b)(a + b) + b - a > 0 which is true because b>a and both a and b are bigger than 1 because they are primes so, for sure |ab(b - a)| > |(a - b)(a + b)| because ab > (a + b) which concludes the proof.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you. Maybe I fail to get the point... I thought you only prove that if the pair a,b is given (a<b), then it's wiser to divide people into n/a groups. But what if there are four prime factors of n, a,b,c,d(a<b<c<d), and it's better to choose b,c as the pair first instead of a,b or a,c or a,d? Can you prove that this situation is impossible? Sorry for my poor English...

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You are right. I did not prove why the solution must be greedy and, in fact, I do not know how to do that. An ideia to why this works is, since the next values will be divided by ab (the part) what is most important to minimize is the current value not divided.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone please post a noob's solution for problem E. couldn't understand a thing...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone please post a noob's solution for problem E? really couldn't understand a thing...

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can refer to my submission here. Tried to make it as clear as possible. (:

    http://codeforces.com/contest/822/submission/28289280

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      by noob's solution I meant, noob's explanation :P... can you help with that? really having a hard time to figure out how to proceed...

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Okay so you need to find if string S of length l1 can be broken by maximum x cuts into pieces that can be joined together to form string T of length l2. Assume that the strings are 1-indexed. dp[i][j] stores the maximum prefix of T that can be obtained from length j of string S after i cuts. So obviously, we need to see if there exists a value of i that is less than or equal to x such that dp[i][l1]=l2. Now assume that you have dp[i][j]=t1. That means after i cuts and length of j from string S, we can obtain the first t1 characters of string T. Now, two transitions are possible. Either the j+1'th character of string S matches with t1+1'th character of string T, resulting some length of their prefixes matching, or those characters are not equal.

        If the characters are equal, we can binary search + hashing to find the LCP (Longest Common Prefix) of string S from j+1...l1, and string T from t+1...l2. Suppose the LCP is t2. Then, the transition dp[i+1][j+t2]=max(dp[i+1][j+t2],dp[i][j]+t2). (i+1, j+t2 must lie within bounds)

        If the characters aren't equal, then dp[i][j]=max(dp[i][j],dp[i][j+1]) because the first j+1 characters of string S can give the same answer as the first j characters.

        Hope this explains it. (:

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

I notice that some of the current AC solutions for Problem E use greedy strategy and I think it is wrong. For example, 28272853. I was wondering if there is a chance to open hack and rejudge. Hope the solutions won't mislead future coders. I got a test case to turn these solutions into WA.

19
xmmmabcdmmmabcdbmmm
7
xabcdbc
3

The answer should be YES but these solutions output NO. Thanks.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

guys can someone gives me a simplified test case according to test case 7 in problem Div2 C that's my code and I don't know why WA :/ here

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

guys can someone gives me a simplified test case according to test case 7 in Div2 C problem :( my code fails and has got WA on test case 7 :/ this is my code here

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    On codeforces we do not have access to the full test case, but what you can do is when you detect the problematic test case (that is, in your case when n == 200000 and x == 114451) you print whatever parameter you need to debug. Your code is outputing a value smaller then the answer from the jury, so your two choices for the 2 vouchers shoud be invalid, that is, they intersect or something like this, just print it to check.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the author's solution for 822C - Хакер, собирай чемоданы!, why do we have to add two types of queries? Isn't the first type enough to handle all cases?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain for me why n * (a + b — 2) / 2 <= n * (a * b — 1) / 2 in problems D ?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For those who use hash for E and got wrong answer in test case 172

unsigned long long is hacked, u have to modulo something else.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I use an O(r*log(r)) algorithm and get Accepted as well. Instead of enumerating all primes, I use all factors to update the answer.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am getting runtime error for case 2 but when i am running my code on my pc for case 2, i am getting correct answer. Here is the link to my submission: http://codeforces.com/contest/822/submission/28796938

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Very strange TL in div2 D, I wrote solution with the same idea as in editorial, but it got TLE with 1.8 sec in worst case (l = 2, r = 5·106). I replace some long long variables with int (it always helps a bit), but got 1.575 sec in worst case.

So it would be smarter just to make TL = 2 sec and not to make people find small extra optimizations for their code (main solution idea is enough, isn't it?).

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://codeforces.com/contest/822/submission/34284404 can anyone tell me why i am getting WA on test case 19? it seems okay to me

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the dp states along with transitions of problem E div2, unable to get it from editorial.

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div2 C problem, Why we can't sort the vouchers by their right borders?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2 C , isn't the standard algorithm used in editorial actually known as 'line sweep algorithm' ?