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

Автор Vovuh, история, 3 месяца назад, перевод, По-русски,

988A - Разнообразная команда

Разбор
Решение (Vovuh)

988B - Подстрочная сортировка

Разбор
Решение (Vovuh)

988C - Одинаковые суммы

Разбор
Решение (Vovuh)

988D - Точки и степени двойки

Разбор
Решение (Vovuh)

988E - Делимость на 25

Разбор
Решение (Vovuh)

988F - Дожди и зонтики

Разбор
Решение (Vovuh)
Решение (step_by_step)
 
 
 
 
  • Проголосовать: нравится  
  • +37
  • Проголосовать: не нравится  

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

Can you explain a bit about what the Convex Hull Trick and Li Chao tree are ? Most Div 3 contestants like myself have little-to-no idea about what they are :)

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

    Also check the solution by step_by_step which uses Convex Hull Trick and Li Chao tree (I added it to the tutorial)

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

      Are you sure that it works in n*log^2(n)? In my opinion it's n*log(n). Why is it log^2?

      Does it also use Convex Hull in some way?

      In my opinion the tree can: 1. Given a and b, insert a new linear function. 2. Given x0, print the maximum value f(x0).

      and it is done in a*log(a)

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

        It depends on solution. Solution by step_by_step works in O(n*log^2(n)), but there are another one solution that works in O(n*log(n)) (of course there are many solutions which works in O(n*log^2(n)), O(n*log(n)) and with many other complexities). I was describe one of them and i do not deny that in this problem exists solution in O(n*log(n)).

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

          Thanks for reply. Could you tell me why it’s log(n)^2? Does update on the tree take log^2? I can’t see why.

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

            This segment tree does the following:
            1) splits the query segment into log(n) segments (like all segment trees do)
            2) From each of these log(n) segments it goes down until it reaches the leaf, so for each segment it spends log(n) operations (the height of tree)

            If n = 2^k and the query segment is [0, 2^k — 2] then the number of operations will be (log(n) — 1) + (log(n) — 2) + (log(n) — 3) + ... = O(log(n)^2)

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

              Thanks, I understand now. So all Li Chao trees work in log(n)^2?

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

                No, if the size of segment tree is power of two and you update all elements then it works in O(log(n))

                So you can use it when you need Convex Hull Trick and the query coordinates are not big. Time complexity will be log(a) per update/query, where a is the minimal power of two greater than maximal coordinate.

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

                  So if I make updates on whole tree, then updating works in log(n), because I divide it into one segment and it goes down one way to leaf. So log(n). And query costs log(n) (from root to leaf).

                  If I change updating to whole tree, then it will work in a*log(a).

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

                  Yes, it will be O(a*log(a))
                  While writing my solution I didn't notice it)

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

                  Can we use this when the query coordinates are negative but their absolute value<=10^5?

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

                  Yes, you can add 10^5 to all your coordinates and change linear functions:
                  k*x+b -> k*(x+10^5)+b-k*10^5

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

                  Thank you,just one more question suppose there are n linear functions and for a given query we consider only functions from l to r. So can we use lichao tree in this problem?

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

Hard contest for Div3, I think that it is Div2. Statistics of successful solutions in comparison with previous Div3 and Div2 confirms this

  | #486 (Div. 3) | #485 (Div. 2) | #484 (Div. 2) | #483 (Div. 2) | #482 (Div. 2) | #481 (Div. 3)
-------------------------------------------------------------------------------------------------
A |          3308 |          4140 |          2291 |          3879 |           3503|          2493 
B |          2460 |          2763 |          2175 |          2952 |            636|          2508
C |          1313 |          1963 |          1416 |           743 |           1362|          2139
D |           292 |           600 |           370 |           392 |            130|           777
E |            64 |           501 |            14 |             9 |              7|          1066
F |            18 |             8 |             3 |             - |              -|           824
G |             - |             - |             - |             - |              -|           261
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you share the statistics ?

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

    Maybe it's not that this round was too hard but the previous ones were too easy?

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

      Almost all my school mates are complaining about the round.

      I think maybe it's a bit too hard for division 3?

      Easier than div.2 rounds, but definitely harder than what I thought div.3 round should be.

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

        There are no really hard problems, even the problems E and F are close to typical Div2C problems, but not harder than Div2C. If i will make Div3 rounds much easier, it will lead to easy way to get 1600+ by participating in Div3 rounds.

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

          All problems were doable and I liked them, but I think there is too little difference in difficulty form C to F

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

          I would agree with you that the difficulty of E and F were quite normal.

          However C and D might be of inappropriate difficulty.

          What's more, STLs like map, vector or set shouldn't appear so frequently since the beginners may not make their way to STL so fast.

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

            My solutions for C and D are almost don't use STL expect sort and standard binary search method. This is not too hard to implement your own sort or your own binary search to find the element in O(log n) instead of O(n).

            But I agree with you that C and D should be much easier that they were in this round. And in these problems must not be too difficult ideas or algorithms as fast sorting or binary search.

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

          Reading your comment Vovuh : I wonder , why Div-3 was even created!

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

            Reading your comments Player.01: I wonder that you first ask to make the problems harder, and when I did it, you wonder that they are too hard.

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

              My intention was to remind the setters that the logic behind creating Div-3 , which is not surely pulling them to Div-2 comfortably , but to set problems that would help them to train logically & rigorously. I mean , it should work as a guideline , don't you think? I believe , setters must be flexible to any feedback & take only the logical ones into considerations rather blindly defending his rounds. Thnx for reading my comments. Have a nice day!

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

                Please don't think that I'm blindly defend my rounds. I'm accept some good ideas from comments and draw my conclusions to do the rounds better than they are now. Have a nice day and sorry if I'm offended you.

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

    You also doesn't notice that there are different parts of community participate in div2 and in div3.

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

      From your post : " Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy."

      I am pretty sure Not all Div-2 participants solved All the "too esay" problems , even some Div-1 participants struggled with E & F .

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

        Maybe some div-1 participants didn't solve E & F. But that doesn't prove that they struggled with E & F. It may also happen that they found E & F too easy to try. I personally found D to be tougher than E & F. F was very basic DP problem. E was also simple, just handling corner cases were difficult. I haven't learnt anything by solving E & F. But I have learnt from D.

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

Can anyone please explain the use of npos in solution B — "if (s[i + 1].find(s[i]) == string::npos) " ?

Cplusplus.com says that it is the greatest possible value for an element of size_t , What does it means ?

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

    It is almost the same as -1 (means "not found" or some similar). I use it just because of my habit. You can replace it with -1 and nothing will change.

    I can be wrong and maybe someone else will explain it better than me.

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

    Just complementing Vovuh's answer: since npos is unsigned, -1 actually corresponds to the largest possible integer value. Since it's greater than the size of any string, it never equals a valid position, and is thus returned to indicate a failed search.

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

In solve 988D:

			if (isl && int(res.size()) < 2) {
				res = { lx, x[i] };
			}
			if (isl && int(res.size()) < 2) {
				res = { x[i], rx };
			}

Maybe it would be more correct?:

                        if (isl && int(res.size()) < 2) {
				res = { lx, x[i] };
			}
			if (**isr** && int(res.size()) < 2) {
				res = { x[i], rx };
			}
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Woooops, yes, you are right! But surely this solution is also correct and the second if statement is useless :D It is because of you will check this pair of points when x[i] will be the right point and lx will be the left point.

    I will fix it anyway, thank you :)

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

      Nothing, but you again made mistake....:

                              if (isr && int(res.size()) < 2) {
      				res = { lx, x[i] };
      			}
      			if (isl && int(res.size()) < 2) {
      				res = { x[i], rx };
      			}
      

      You need to swap first line and 4th....

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

        Oh, I made the second mistake only in the Russian version of editorial, in English version all is fine :D Thank you, fixed again (I hope :D)

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

There is any other way to think/solve D?

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

    I think that the max size of set wont larger than 3,so you can enumerate each xi and each 2^n where n <= 32

    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<vector>
    #include<map>
    #define ll long long
    using namespace std;
    
    ll a[200005];
    ll ans[200005];
    ll tem[200005];
    ll pow2[33];
    
    void init(){
    	ll base = 1;
    	for(int i = 1; i <= 32; i++){
    		pow2[i] = base;
    		base *= (ll)2;
    	}
    }
    
    int main(){
    	init();
    	int n; cin >> n;
    	for(int i = 0; i < n; i++) cin >> a[i];	
    	sort(a, a + n);
    	int a1, a2, a3;
    	int len = 1; bool flag3 = false, flag2 = false;
    	for(int i = 0; i < n; i++){
    		for(int j = 1; j <= 32; j++){
    			ll dif = pow2[j];
    			int pos1 = lower_bound(a, a+n, dif+a[i]) - a;
    			int pos2 = lower_bound(a, a+n, 2*dif+a[i]) - a;
    			if(a[pos1] == dif + a[i] && pos1 < n){
    				flag2 = true;
    				a1 = a[i]; a2 = a[i] + dif;
    				//cout << pos1 << endl;
    				//cout << a[pos1] << " " << a2 << endl;
    				if(a[pos2] == 2*dif + a[i] && pos2 < n){
    					flag3 = true;
    					cout << 3 << endl;
    					cout << a1 << " " << a2 << " " << a[i] + 2*dif << endl;
    					return 0;
    				}
    			}
    		}
    	}
    	if(flag2){
    		cout << 2 << endl;
    		cout << a1 << " " << a2 << endl;
    	}
    	else{
    		cout << 1 << endl;
    		cout << a[0] << endl;
    	}
    	return 0;
    }
    
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Vovuh,In problem C why did you use stable_sort? Normal sort also passed. What is the difference? In the future at what kind of situations should we use stable sort?

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

Vovuh in F we can use another dp with O(a) memory and O(a2) time:

in case we have umbrella in i-th position: dp[i] = min i <= j (dp[j] + (j - i) * w[i])
if we don't: dp[i] = min(dp[i + 1], dp[i])

and when doing convex hull trick on this dp, we can see that slopes are decreasing, so we don't need additional structures to maintain convex hull. so this can be solved in O(a * log(a)) time

link: 38904415

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

Problem F — Someone can help me?, i can't find mi error :(.

My code

Thanks in advance c:

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

    If you have more than one umbrella at the same place, you should get the one with minimum weight

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

In problem D tutorial, how is k equal to L ?

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

    If we transform to the binary representation, any power of two is represented by 1 and number of 0's (may be zero) to the right of that 1, for example: 1 and 1000, which are equal in decimal to: 1 and 8, respectively.

    So, when you sum two different powers of two together, you will get a number which is represented in binary as two 1's and number of 0's (may be zero), for example:

    10000

    +

    00100

    =====

    10100

    So, the result is not a power of two.

    But there is one case that will give us a power of two from summing two powers of two, and it is summing a power of two to itself, like:

    01000

    +

    01000

    =====

    10000

    Hope it answered.

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

      Thanks for the answer, it cleared a lot. But why does the answer not exceed 3? it could have been dist(a, d) * 4 instead of 3.

      upd: ok, I got it, in case of abcde there's still a abcd triplet in there, so the distance between a and c will still be 3*2^k, and it will be still invalid.

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

        Welcome :).

        The equation dist(a, d) = dist(a, b) * 3 came from the proofs before it.

        In the same way in which the tutorial proved that dist(a, b) = dist(b, c), we can prove that dist(b, c) = dist(c, d). So, the following equation is hold:

        dist(a, b) = dist(b, c) = dist(c, d) ( = x, for example).

        And we know that: dist(a, d) = dist(a, b) + dist(b, c) + dist(c, d) = x + x + x = 3 * x. And from here, 3 came.

        And any changing in this 3 means that some changes in the previous parts of the proof were happened, for example:

        dist(a, d) = 4 * x can come from: dist(c, d) = 2 * x, which means that: dist(b, d) = dist(b, c) + dist(c, d) = x + 2 * x = 3 * x, which isn't a power of two, but in the problem, we need dist(b, d) to be equal to a power of two.

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

          Can you maybe also answer how the term of 10^9 came in the equation when calculating the complexity?

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

            Sorry, I cannot reply now. I'll try later (may be toworrow).

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

            You iterate over all powers of 2, from 20 until 2x with 2x ≤ 2 * 109.

            There are many of these powers.

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

Will the vector in problem C's solution too large? Cuz it maybe 2 * 1e5 * 2 * 1e5 elements...?

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

Why am i getting TLE on div 3 D when using map, and AC when using original binary search ?

Using binary search: https://codeforces.com/contest/988/submission/38916484

Using STL Map : https://codeforces.com/contest/988/submission/38916424

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

" You can also notice that the order of swaps doesn't matter and you can rearrange them in such a way that no leading zero appears on any step. " How to prove this or any kind of intuition behind this ?

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

    You can rearrange the operations in such a way that first of all you move the leftmost non-zero digit in the number to the left in order to keep the number correct after each of the next operation.

    But in general case you don't know which digit will be leftmost non-zero (there are too many cases that are depend on the digits you choose), so to make this problem much simpler you firstly move digits you choose to the right and then find the leftmost non-zero digit and move it to the left.

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

can anyone explain the 3rd case of 988F .

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

    Test Case:

    10 1 1
    0 9
    1 5
    

    the segment 0-9 is under rain and only haft an umbrella on the position 1 so you never can pass the position 0 without getting wet, so the output is -1

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

Can anyone tell, why http://codeforces.com/contest/988/submission/38851322 this solution didn't work for Problem C?

The approach given in the Editorial also fails in Python.

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

Why does the memory blow up on 7th test case? 38888128 (Problem B)

I know the complexity is O(n2)...but why does memory blow up?

Is it something to do with sorting string array?

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

guys can u give me link reference + solution using cordinate compression, how do you compress coordinates

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

I am sorry to bother every one .

But I have something trouble in this Div.3 C.

This is my code : https://codeforces.com/contest/988/submission/38961776

As you see , I hack my code ( use the DEBUG macro ) .

And find this code output is correct .

The testcase is too long to see , that is why I wonder someone help.

My way to sovle this problem :

Enum the sequence i and j , and enum the elements of sequence i .

As well known , if I confirm the Sum of I , the Sum of J , and the element in i , then I can calculate what the element in j is .

And I binary_search the j which I calculated .

And then , I can know is "YES" or not .


I clearyly know my code is too complex to pass , but I want to know , why I got the "Wrong answer" , rather than "Time Limited Exceed".


Thank you very much for everyone help :D!

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

    I know why I got an wrong answer. If I use the binary search , I have to sort the vector .

    But I sort the vector , the index of the vector have changed .

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

Probably a simple solution to E : http://codeforces.com/contest/988/submission/38965567 As we have only 4 options 00, 25, 50, 75 at the end Just count the place by which these digit is to be moved obviously taking care of leading zeroes at the beginning in case the swap is made.

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

Anyone explains me why my code is TLE?

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int n,m,cnt;
vector<pair<ll,pair<int,int>>> a;
int main()
{
    cin>>n;
    for (int i=0;i<n;i++){
		cin>>m;
		vector<int> x(m);
		for (int j=0;j<m;j++) cin>>x[j];
		ll s = accumulate(x.begin(),x.end(), 0);
        for (int j=0;j<m;j++){
			a.push_back(make_pair(s-x[j],make_pair(i,j)));
        }
    }
	sort(a.begin(),a.end());
    //for (int i=0;i<a.size();i++) cout<<a[i].fi<<" "<<a[i].se.fi<<" "<<a[i].se.se<<"\n";

	for (int i=0;i<a.size()-1;i++){
		for (int j=i+1;j<a.size();j++){
		cnt++;
		//cout<<cnt<<" ";
			if (a[i].fi==a[j].fi){
				if (a[i].se.fi!=a[j].se.fi){
					cout<<"YES\n";
					cout<<a[i].se.fi+1<<" ";
					cout<<a[i].se.se+1<<" "<<endl;
					cout<<a[j].se.fi+1<<" ";
					cout<<a[j].se.se+1;
					return 0;
				}
			} else {
				i=j-1;
				cout<<i<<endl;
				break;
			}
		}
	}
	cout<<"NO";
    return 0;
}

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

    if a.size() is 1e5 then 1e5*1e5=1e10 , it's bad : ).So , will give you TLE.

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

Can someone explain the problem with this approach for "Rain and umbrellas"?

let - dp[x][0] --> indicates that umbrella was not used for segment (x-1) to (x)

  • dp[x][1] --> indicates that umbrella was used for segment (x-1) to (x)

Now, dp[x][0]
= infinity (or invalid) --> segment (x-1) to x is under rain

= min( dp[x-1][0], dp[x-1][1] ) --> segment (x-1) to x not under rain

dp[x][1]
= (best wt umbrella uptil now) + dp[x-1][1] --> I continue carrying same umbrella

= (best wt umbrella uptil now) + min( dp[x-1][0], dp[x-1][1] )
--> I drop heavy wt umbrella and pick more lighter umbrella

Getting wrong answer. Not able to find whats wrong with the approach.

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

    The problem in your approach is best umbrella to be carried till position i may not be necessarily the best one for i+1 but other umbrella might help. For computing the optimal solution, you MUST consider all previous choices of umbrellas. This is the dynamic programming approach, what you BEST is actually greedy. Hope it helps.

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

      I got the scenario where my solution would fail . Thanks :)

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

      Hello rahul, Can you please tell me that in third problem the solution provided by editorialist makes the assumption that the variety of sums while removing each element and at the same time inserting into the vector does not grow very large otherwise can there be a case that the vector still accepts upto 10^9 elements in it or there could be memory limit excedeed?

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

Can anybody help me with this: http://codeforces.com/contest/988/submission/38960067 I can't find my mistake. Is stuck in testcase 5.

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

In problem F I use:

int dp[i] — the minimmum fatigue to get to position i,

bool rain[i] — true if position i is into a raining interval,

umbrellas[i] — the minimmum weight of an umbrella at position i, if there is no umbrella, umbrellas[i] = 0;

In my approach I calculate for each position i, what's the minimmum fatigue of getting there using the umbrella at position j (j <= i):

dp[i] = min( umbrellas[j] * (i — j) + dp[j — 1]) for each j from i to 0;

I can't see where my idea fails, still stuck in testcase 5.

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

    Not reading carefully the problem caused me multiple WA5, specifically this lines:

    he must carry at least one umbrella while he moves from x to x+1 if a segment [x,x+1] is in the rain (i.e. if there exists some i such that li≤x and x+1≤ri).

    Hope you don't come across the same mistake

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

988F — решение bigcat111(python3), намного проще чем O(a⋅(n+m)). Круто решил, че сказать.

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

Can anyone help me out how sort function work here in 988C .i am beginner here.

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

Can anybody help with this code please, i don't understand why it is not working. problem 988F. https://ide.geeksforgeeks.org/cUWXmWZsWM

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

Can somebody explain the error in this code for Problem E? Or provide a test case where it fails to produce the expected output? It is giving me wrong answer verdict on some test case. Here is the link to my solution:- https://ide.geeksforgeeks.org/pA25wT6HpW

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

For problem C you can do it in O(k) time. Specifically O(n + k), but since sum of n = k it will be O(k). To do it, you can use the 2sum trick, i.e. reduce it to problem a + b = 0 where a and b are in two separate arrays.

Let H be a hash map which maps an int to a pair of values (k, i) where k is the sequence and i is the element, i.e. h[s] = (k, i) which tells us the sum of the k'th sequence subtract the i'th element is equal to s.

Iterate through each sequence, calculate the sum of the sequence, call it s. For each element in the sequence, a, check if s — a[i] exists in the hashmap. If it does, we have a solution. After we have checked the entire sequence, map all of these values we checked into the hashmap.

i.e. the hashmap considers all sequences (and elements) from 0 to i — 1 (where i is our current sequence). We do not have to store every possible (k, i) in the hashmap since we only need one solution.

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

about Problem D: why the size of the answer set can be 1?