Supermagzzz's blog

By Supermagzzz, history, 13 days ago, translation, In English

All problems were invented MikeMirzayanov and developed by me Supermagzzz and Stepavly.

1472A - Cards for Friends

Editorial
Solution

1472B - Fair Division

Editorial
Solution

1472C - Long Jumps

Editorial
Solution

1472D - Even-Odd Game

Editorial
Solution

1472E - Correct Placement

Editorial
Solution

1472F - New Year's Puzzle

Editorial
Solution

1472G - Moving to the Capital

Editorial
Solution
 
 
 
 
  • Vote: I like it
  • +147
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it -65 Vote: I do not like it

How the editorial posted 2 years ago? If the contest is running.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    2 "Hours" ago.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You can write blogs and not publish them. In this case, it is so the author can get a fast editorial out — by pre-writing the editorial but not making it public yet.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You wrote "years" instead of "hours":)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    problem D was almost same as this one.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why in 1472G - Moving to the Capital you can't go in first sample:

6->2->5->1
corresponding d[i] is
[2]->[1]->[2]->[1]

so there is exactly one step of kind 2.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To calc the distances you need to consider the direction of the edges.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    You use road with d[2] -> d[1] twice. It's not allowed

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I use different roads. Are you talking about same distances change?

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes, you use road with this distances twice

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh, I got where is my mistake. I mixed up two kinds. Actually [2]->[1] is second kind of move. I thought it is first kind. shame.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Your move from 6->2 is a move of the second kind (dist 2 to dist 1) The move from 5->1 is also a move of the second kind (dist 2 to dist 0).

    Therefore, you should stop at city 2 — a distance of 1 from the capital.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah,I have the same question.

»
13 days ago, # |
  Vote: I like it -37 Vote: I do not like it

DIV 3 PROBLEM C VIDEO TUTORIAL LINK https://www.youtube.com/watch?v=7FFzXk-brRU I have tried my best to give you guys proper intuition of this dp problem. Hope you guys will enjoy this video !!!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how can editorial be posted if hacking phase is still ongoing

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone please explain d

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    For D you only have to justify to yourself why taking the biggest number is always the best choice to make on your turn. The editorial actually does a pretty job of this, but think of it like this — either you take the biggest item left, and it matches your parity (i.e. add it to your score), or it doesn't (your opponent doesn't gain from that item on their turn — also good for you). It's simple to see that therefore a player should ALWAYS take the biggest item (i.e. sort the array and check each move).

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks got it : )

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, really simple explanation, even i wasn't able to understand editorial's solution.

      Thanks again !!

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In the code though I saw that the if condition simply added or minused from result based on it's eveness or oddness. Shouldn't it be based on whose turn it was instead? Cause Alice can take an odd number and result wouldn't change.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the index takes care of alice/bob turn...after sorting it in reverse order...the even index corresponds to alice and the odd index corresponds to bob

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yeah, i misread it

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually the solution was so simple that I spent 20 mins trying to prove it but still submitted this method without proving it because I couldn't find any other better method

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another way to look at it:

    At each point the player wants to maximise the distance between the scores of one another.

    You may be tempted to look for parity while picking the numbers, but if the goal is to simply maximise the distance then you increasing your score is equal to hindering the others progress.

    therefore at each point you pick The largest number which has a potential to reduce the difference between two scores.

    I hope this makes sense.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the approach for B (non DP approach)?

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it -46 Vote: I do not like it

    h

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are two cases

    • sum is odd(definetly no)
    • sum is even if sum is even there can be two cases
    1. even= even+even (can always be divided equally)
    2. even= odd+odd.
      in second case if there is no zeroes then and only then it cant be divided other wise its always YES
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the odd+odd part?

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if both parts are odd then there must be atleast two onez their to make both parts equal.

        For ex: 6=3+3 if it doesn't consist of any both part can't be equal (it will be like (2,4) ) because by only 2's we can't make a odd number.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Odd means even+odd So, dividing it by odd+odd It means if sum/2 is odd, there has to be atleast 1 ones in the array. As, 2 is even

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Simple solution — let's iterate through how many candies of weight 2 we will give to Alice, then the remaining weight should be filled by candies of weight 1. If there are enough of them, then we have found a way of division. How is this true ? If we take the case of 1 1 2 2 2, then Alice will get 2 2, while Bob will get 2 ,1 and 1.

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello jiggly_puff Lets consider the test case 1 1 2 2 2 then As you have writted by yourself Alice will get {2,2} and bob will get {1,1,2} now total weight of alice candies = 4 toatl weight of bob candies = 4 , hence it will return YES as alice_weight = Bob_weight

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Not the best solution, but probably might be easier to understand:

    https://codeforces.com/contest/1472/submission/103314992

    So you can use it as a base for a further optimization.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Approach for problem B.
    Let the number of 1's is one & the number of 2's is two .
    Let total sum = one + 2 x two.

    Casework:

    Case 1

    Case 2

    Case 3

    Case 4.1

    Case 4.2

    You can also see my solution here : 103195164

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lets say s represents the sum of all elements, If s is odd then its totally impossible to split it into two equal halves

    Otherwise if s / 2 odd then you need to have atleast one 1 in the array to make the odd half

    so the answer is no if (you have a odd total) or (a even total but odd half and no ones with you), else answer is yes

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a method based on some observations. You can have a look at my code here. If the sum is odd, obviously there's no way of distributing them in equal halves. Also, if you have no 1's and an odd number of 2's, you again can't do it. In all other cases, you can always come up with a solution, just try out some test cases yourself!

»
13 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Problem B is really similar to Div-2A Kitahara Haruki's Gift (https://codeforces.com/problemset/problem/433/A)

Great Contest Overall

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain last testcase of Problem G.

For node 3 , shouldn't the ans be 1

we can go

3 (2) --> 4 (3) ---> 2 (1)

value in brackets is the corresponding d values

3--> 4 is of type 1

and

4--> 2 is of type 2

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much, now I can solve E, F and G tasks!

»
13 days ago, # |
  Vote: I like it +20 Vote: I do not like it

A way to avoid repeating the algorithm in E, is to always have H < W for every i. So just swap H and W for some person, if H > W.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain a little bit more ? thanks in advance.

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      Now I got it. the condition for the person i to be placed in front of the person j can be rewritten like this : min(h_i, w_i) < min(h_j, w_j) and max(h_i, w_i) < max(h_j, w_j) This means you can compare like that.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple solution — let's iterate through how many candies of weight 2 we will give to Alice, then the remaining weight should be filled by candies of weight 1. If there are enough of them, then we have found a way of division. How is this true ? If we take the case of 1 1 2 2 2, then Alice will get 2 2, while Bob will get 2 ,1 and 1.

»
13 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Here are my attempts to explain solutions in video form after messing almost everything up (this seems to happen more and more often recently...)

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

on G,can someone explain why (dist[u] must <dist[v]),my code doesn't add this condition and i got WA. Thanks!

if (!used[v] && dist[u] < dist[v]) { dfs(v, g, dist, dp, used); } (In the DFS function)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because you can use only the first option from the statement as much times, as you want. We build the new graph, with edges that satisfy this condition. The second option we check by DP.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, This is my Dfs function. Where did I perform the second operation twice?
      mark : stores the final answer.
      d : stores the distance from root.

       void Dfs (int t){
      vis[t] = true;
      for(auto u: g[t]){
      if(!vis[u]) Dfs(u);
      if(mark[u] < d[u]){
      if(d[u] > d[t]) mark[t] = min(mark[t], mark[u]);
      else mark[t] = min(mark[t], d[u]);
      }
      else mark[t] = min(mark[t], d[u]);
      }
      }

      Adding that conditon you mentioned, gives me an AC. Can you please tell, where am I going wrong? Thanks

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      I am stuck in the same situation. Even without dist[u] < dist[v] condition, we seem to be ensuring that 2nd condition is only counted once because

      if (dist[u] < dist[v]) { // Only count dp[v] if it's not bridge
         dp[u] = min(dp[u], dp[v]);
      } else {
         dp[u] = min(dp[u], dist[v]);
      }
      
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial for G is very smooth. Great work Supermagzzz and Stepavly.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know how people solve problem like today's D so fast !! sed lyf :((

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B Video Editorial link :https://www.youtube.com/watch?v=ZVLnPd0_3BU I have tried my best to explain with intuition and corner case.I hope you will enjoy this video !!!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What a fast editorial! Really helpful; Thank you!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder with B they did not include the alternate solution with DP

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please help me to resolve MLE in this solution for Problem C

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your dp size is 20000 instead of 200000

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you're passing the vector by value, so each time you call solve() a new copy is created. Pass it by reference or make it global.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this dp solution gives WA on B.I thought it is equal sum partition. https://codeforces.com/contest/1472/submission/103310451

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I came across an ID in this round which was submitting solution with wrong answer for a particular corner case. FOR eg if n==123234 then print "NO" , this was done so that it could be hacked by another IDs. :p

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me why my code gets a WA(I get why it might get TLE but no WA): 103300499

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    wrong answer jury found the answer, but participant didn't (test case 11)

    This is a comment of your code, so you can look for test case 11(it is visible) and see why it doesn't work. EDIT: you're only looking for elements with smaller X but a correct answer could also be element whose X is larger Y is smaller and so when it is laid sideways than it could fit in the element that you are checking. So your for loop J should go from 0 to n (i.e. check all elements) P.S. even if you did this you would get TLE

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why my solution is showing WA. My logic is obvious. One can easily get that after seeing my code. Submission

Thanks in advance for helping :)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think its because you didn't sort the arrays. You should always take largest number, and even if you divide numbers in odd and even you should sort the array and look for larges numbers. I used a similar approach 103227720. Hope this helps.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah.. Thanks I get it. I didn't sort the array (T_T) Literally if you see my commented solution below it i had sorted the array. But i missed while writing new one. I thought i have sorted the arrays. Why these things happen to me (T_T)

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I didn't actually understand your code, but I think the approach is similar. So hopefully this will be helpful!

    Explanation for D

    Let's observe first, when it's Alice's turn, she either blocks(selects the biggest odd number so the maximum point that Bob can take decreases) or takes the biggest even number.

    It's also similar for Bob, he either tries to block Alice by selecting the biggest even number(so the maximum point that Alice can take decreases) or takes the biggest odd number.

    Why this is optimal?

    Let's take this case as an example: $$$ \text {N = 4, } \ $$$ $$$\text{A: {5 3 4 6}}$$$

    1- Alice starts, now there are 2 options, blocking 5 or taking the 6.

    1.A- If she blocks the Bob, then Bob will also block her and she'll lost 1 points because of herself. And it'll stay at "Tie" when it's Alice's turn(3rd turn) again, thing is, if Alice had choosen to take 6, she would be on the lead now(check 1.B)

    1.B- If she takes the 6, then Bob will take the 5, and now it's Alice's turn(3rd) again, and now she is on the lead because of her decision.

    2- It's the 3rd turn, Alice 1 — Bob 0, and the array is {3,4}

    2.A- Alice can choose taking the 4 or blocking the 3, if she blocks the Bob, then Bob will also block her in the next round, so the final points would be (1 — 0)

    (It's true but not optimal, check 2.B)

    2.B- Now if Alice chooses taking the 4, Bob will take the three in the next round and the final points would be (5 — 3)

    Because the difference is higher, 2.B is more optimal for Alice. But, because of Bob has no action over the 1st turn of Alice, it's also optimal for him too.

    I hope this helps. Now for the coding phase,

    Code part

    My code for D

    Basically what this code does is, if $$$\text{i is even}$$$ it means it's Alice's turn, and if the current biggest value is even, she takes it, if it's odd, she blocks it.

    Opposite case for Bob.

    Note: I wrote this 5 minutes before I went to sleep, so if there are mistakes, forgive me and correct me please.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem G? Why do we have to change the graph? Why can't we apply dp on the graph with cycles?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have applied dp only my friend. You can see my submission. Reply here if you didn't get the logic.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I enjoyed the last dp problems of this contest :)

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone else feel that E was too much implementation heavy?

I thought about exactly this solution but with 30 mins remaining.
Then dropped the idea thinking that it might have some better segment tree solution instead of so much implementation. lol

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Actually, it is not (at least for me).

    It could be implemented using a segment tree in about 30 ~ 40 lines of code.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

G was cool, E took me a while but it was fun too. Overall good problems!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it good to write an editorial while the hacking phase is still on?? I don't think so.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a bit tough contest

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Are we allowed (yet) to ask inquiries regarding hacks for this round?

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me how ans of this test case of ques d is TIE.

3 2 1

I guess here bob should win. First alice chooses 2, then bob goes with 3 . Then at end alice chooses 1 and removes it. So bob wins here(since score of bob is 3 and alice score is 2).

How is it draw?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IF Alica pick 3 first, then if Bob pick 1 Alica wiil win because in next turn she will pick 2(Bob_score = 1, Alica_score = 2), if Bob picked 2 insted of 1, Alica will be left with 1 (Bob_score = 0, because he piced even number, Alica_score = 0, because she picked odd number). Then answer is TIE.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be done by top-down approach?

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is this Solution got hacked? It is almost same as the Editorial. Please let me know as I don't wanna to repeat the same mistake again. Thanks in advance !

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, I was wondering the same thing as well. My solution (and many other Java solutions of a similar format) were also hacked (and ultimately received TLE), but I cannot find any apparent inefficiencies.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I heard Java sort uses quick sort. Quick sort in a worst case takes $$$O(N^2)$$$ complexity in an anti quick sort test.

»
13 days ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

Is this Dp forces ?

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have two implementations for E which I think are easier than the one in the editorial.

A : With comments, Without comments

B : With comments, Without comments

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Frustrating , Frustrating .... Can't believe it i wasted more than 1 hour , to solve D and never noticed variable was crossing integer range , So guys always check if range is crossed or not :(

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In the first test case of the given example of question E,

Test case:

3

3 4

5 4

3 3

Ans: -1 3 -1

Why is it -1 for the first pair? 3,3 can be placed in front of 3,4 right? Am I missing something?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because the height and weight have to be strictly less than the person behind. 3 is less than 4, but 3 is not less than 3.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

DP Contest :)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is only 2 problems I solved with dp and I think this is enough. Problems which have dp tag also have some other solutions this contest

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

cf 693 1st question please help me , on what test case my code fails because I think that my code is right Its humble request thanks in advance

include <bits/stdc++.h> using namespace std;

long long count(int n){ long long c=0; while(n%2==0){ n=n/2; c++; } return c; }

int main() {

int t; cin >> t; while (t-- > 0) { int w, h; long long n; cin >> w >> h >> n;

string s = "";

if (n == 1)
{
    s = "YES";
    //continue;
}
else if (w % 2 == 1 && h % 2 == 1)
{
    s = "NO";
    //continue;
}
else if ((w % 2 == 0 && h % 2 == 1))
{ 

    long long x1 = 2*(count(w));
    if (x1 >= n)
    {
        s = "YES";
    }
    else
    {
        s = "NO";
    }
    //continue;
}
else if ((w % 2 == 1 && h % 2 == 0))
{
    long long x2 = 2*(count(h));
    if (x2 >= n)
    {
        s = "YES";
    }
    else
    {
        s = "NO";
    }
    //continue;
}
else
{   long long a1=2*(count(w));
    long long a2=2*(count(h));

    if (a1*a2 >= n)
    {
        s = "YES";
    }
    else
    {
        s = "NO";
    }
    //continue;
}
cout << s << endl;

}

return 0; }

  • »
    »
    13 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    U multiplying count (w/h) by 2. Rather, make it like this-

    long long x1/x2 = pow (2,count (w/h))

    And in, a1/a2 u r multiplying it.. i don't know if it works or not.. but u can give it like this

    long long a1= pow (2,count (w)+count (h))

    then, just check if a1>=n

    Reason- suppose u can cut 3 times, u can make 8 papers. But your answer gives 6 papers

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code give correct answer on the test cases given by codechef .

      In this I use 5 condition 1st if n==1 if n is one then ans is yes 2nd if w and h is odd and n is not 1 then ans is NO 3rd if w is even and h is odd then I count how many times w is divided by 2 ,and finally multiply by 2 For example w= 4 and h =7 then max=4 4th case is vice versa of 3rd 5th case if both w and h is even then I count how many times w and h is divided by 2 ,and and multiply both by 2 For example w=4 and h=8 then max=24

      But when I submit the code it is saying wrong output on test cases 2 Please help

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I made the changes that I told you to make and it is giving me AC.

        Here you go

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you so much Finnaly accepted I need one suggestion from you Suppose I gave a codeforces contest and solve 2 question and I got stuck in 3rd question Then should I only have to see the 3rd question editorial or how many questions should I have to up solve I mean that how I improve myself Any tip from your side

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I literally did the same thing for problem D — 103294044

Can anyone help me how to optimise this, because I got tle

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Quoting some lines in your code :

    while (n>0):
            maximum = max(arr)
    

    Finding max in an array takes O(n) time, and you are doing that operation for n times, that means your code is effectively getting to a complexity of O(n^2). But the constraints on n is (1 ≤ n ≤ 2 * 10^5), so for O(n^2) your code would have to do (2 * 10^5) * (2 * 10^5) = 4 * 10^10 operations per second. But normal CPUs can do only about 10^8 operations per second. Hence you are getting a TLE.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh ryt! So would it be better if I first sort and then use them? or is there any other way? which is even better than sorting and using

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        First Sorting and then using would work fine. I am also linking my solution to the problem so that you may take reference (Although it's pretty much the same what editorial says) — 103483268. If my answer helped you in any way, please do vote a like!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I took a different approach for A, first I reduced the width and height to minimum it could be. Thus I have the width and height of the smallest card. I can use it find the area. Now I divide the area of the original card with the area of the smallest card. Now I have the number of cards I can create.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For D first test case my code is giving right output in my pc whereas on codeforces it gives wrong output 103274282

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    else if (o[j]>=e[i] && !fl) { sumb+=**o[i];** --j; fl=!fl; }

    Maybe this is causing some problem

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was given similar problem as D in one of my interviews and I couldn't think of greedy approach, could only come with DP approach and was rejected. Now I solved it with so much ease in comfortable environment. Hate interview pressure.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain E?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    1. Ask everyone to stand (make $$$h_i \leq w_i$$$ for every $$$i$$$).
    2. Sort them based on $$$h_i$$$ then $$$w_i$$$.
    3. Now we know that the $$$i$$$-th person is at least as tall as all of the people who come before him ($$$h_i \geq h_j$$$ for every $$$j < i$$$).
    4. Iterate through everyone and find the largest $$$j$$$ such that $$$j$$$-th person is strictly shorter than the $$$i$$$-th person ($$$h_i > h_j$$$). As they are already sorted, now we know that the $$$i$$$-th person is also taller than all of the people who stand in front of $$$j$$$-th person.
    5. Now we have $$$j$$$ possible candidates that can be placed in front of $$$i$$$-th person. We no longer have to check whether they are shorter than $$$i$$$-th person or not, because we already know that from the previous step.
    6. We need to find among the $$$j$$$ possible candidates, is there a person who is thinner than the $$$i$$$-th person. There could be more than one person who fits the criteria, so we will just greedily pick the thinnest person among those $$$j$$$ people and check if the thinnest person is thinner than $$$i$$$-th person.
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D (language used : JAVA 11) , I am getting TLE in testcase 10 with this snippet of code

while(t-->0){ int n = ni();

       int arr[] = new int[n];
       for(int i=0; i<n; i++){
         arr[i] = ni();
       }

       Arrays.sort(arr);
       int k=0;
       long a=0, b=0;
       for(int i=n-1; i>=0; i--){
         k++;
         if(k%2 !=0 ){
          if(arr[i]%2==0)
              a+=arr[i];
         }
         else{
          if(arr[i]%2!=0)
              b+=arr[i];
         }
       }
       if(a==b)
         pn("Tie");
       else if(a>b)
         pn("Alice");
       else
         pn("Bob");

    }

and getting AC with this snippet of code

while(t-->0){ int n = ni();

       Integer arr[] = new Integer[n];
       for(int i=0; i<n; i++){
         arr[i] = ni();
       }

       Arrays.sort(arr, Collections.reverseOrder());
       long a=0, b=0;
       for(int i=0; i<n; i++){
         if(i%2 ==0 ){
          if(arr[i]%2==0)
              a+=arr[i];
         }
         else{
          if(arr[i]%2!=0)
              b+=arr[i];
         }
       }
       if(a==b)
         pn("Tie");
       else if(a>b)
         pn("Alice");
       else
         pn("Bob");

    }

Can anyone help me to know what is the cause?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly what you are not able to understand?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In first code I sort the array in non decreasing order and I traverse the array from last for chosing the number for alice and bob

      and in second I sort the array in non increasing order and I traverse the array from starting for chosing the number for alice and bob

      Both are about same approaches nearly while first one is getting TLE and second one is AC

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please use ruffle sort (Randomized quick sort to avoid quick sort worst case)-: My Code in case it helps-: `package Div3_693;

    import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Random;

    public class D {

    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    
        int tc=Integer.parseInt(br.readLine());
    
    
        for(int tt=0;tt<tc;tt++) {
            br.readLine();
            String[] line = br.readLine().split(" ");
    
    
            int[] arr=new int[line.length];
            for(int i=0;i<line.length;i++){
                arr[i]=Integer.parseInt(line[i]);
            }

    // Arrays.sort(arr); ruffleSort(arr); long ascore=0,bscore=0;

    boolean turn=true;
            for(int i=arr.length-1;i>=0;i--){
                if(turn){
                    if(arr[i]%2==0){
                        ascore+=arr[i];
                    }
                }else{
                    if(arr[i]%2==1){
                        bscore+=arr[i];
                    }
                }
    
                turn=!turn;
            }
    
            if(ascore>bscore) System.out.println("Alice");
            else if(bscore>ascore) System.out.println("Bob");
            else System.out.println("Tie");
    
    
        }
    
    
    
    }
    
    static void ruffleSort(int[] arr){
        Random r=new Random();
        for(int i=0;i<arr.length;i++){
            int j=r.nextInt(arr.length);
            int k=r.nextInt(arr.length);
            int temp=arr[j];
            arr[j]=arr[k];
            arr[k]=temp;
        }
        Arrays.sort(arr);
    }

    } `

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1472/submission/103236341 this is my solution of D main idea is what person must bring max(his parity, opposite parity(it means not give this element to enemy))

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem E be solved with monotone stack? Think the array to be circular, then for each element find the next element so that (h1 < h2 and w1 < w2) or (w1 < h2 and h1 < w2)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can provide better sol for Problem E or any video

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I am facing some problems with D. Even-Odd Game. I have read the editorial as well as the solution provided. I think I am doing the exact same thing given in the solution: always selecting the biggest available number for either player and adding or subtracting it from a global sum depending on who the player is and the parity. However, I am getting wrong answer on test case 3. ~~~~~

include <bits/stdc++.h>

using namespace std;

int main() { int t, n; cin >> t;

for(int i = 0; i < t; ++i)
{
    cin >> n;

    int a[n];

    for(int j = 0; j < n; ++j)
    {
       cin >> a[j];
    }

    int size = sizeof(a) / sizeof(a[0]);

    //sort array in ascending order
    sort(a, a + size);

    int score = 0;

    int num;

    int turn = 0;

    for(int j = n-1; j >= 0; --j)
    {
       num = a[j];

       //Alice Turn
       if(turn % 2 == 0)
       {

         if(num % 2 == 0)
          score += num;
       }
       //Bob Turn
       else
       {
         if(num % 2 == 1)
          score -= num;
       }

       ++turn;
    }


    if(score > 0)
       cout << "Alice\n";
    else  if(score < 0)
       cout << "Bob\n";
    else
       cout << "Tie\n";

}

return 0;

} ~~~~~

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this round. I like problem G very much, it is the classic Codeforces' style task. Quality of this round was much better than previous five or even more.

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D i have used erase for deleting the element and it has failed, but i see solution with same logic but using pop_back() instead of erase getting their solution accepted. I want to know that whether the time complexity of erase more than pop_back() or are they same in c++ ?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a different solution for F, where I keep a offset between the top and bottom pointer, and use some case analysis. Time is O(mlogm).

»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it

As the problem D has a trival solution, I have faced a false plagarism accusion on it.

"Your solution 103217882 for the problem 1472D significantly coincides with solutions lit2019039/103212550, whohet/103217882."

This question has a really trival solution and hence is clearly a coincidence. Please help and remove this plagarism mark. This is literally a coincidence, as the problem really have same solution. My solution link https://codeforces.com/contest/1472/submission/103217882

Match solution link https://codeforces.com/contest/1472/submission/103212550

Please have a look as problem really have a trival solution

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How does the code which was giving RE on testcase 4 with a slight modification in the comparator function (used for sorting) gives AC(aka happy new year). The change simply is using "<" instead of "<=". any input in this regard is highly appreciated

code with AC VERDICT:https://codeforces.com/contest/1472/submission/103375747

code with RE on test4 :https://codeforces.com/contest/1472/submission/103375782.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I bealive comparator function should be unique. Meaning if A > B then B < A. In your case with <= you are saying that at that if A == B then a could be before or after B which should not be possible because then sorting is not unique. I.E. if your functions returns A < B it should also return !(B < A)

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I believe when you say "A<=B" that would mean that if A and B are equal then A should be before B , Although I understand what you are trying to infer, and I think that it could be right but that would depend on the sorting algorithm, furthermore if it was the case that A and B are repetitively compared with each other, shouldn't it result in a TLE instead of RE?

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I bealive it works that if you compare A and B, than comparator automaticly compares B with A, and it should yield same results. In your case it gives A before B in first, and B before A in second which is contradictory. And so it gives an error.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          alright that makes sense. thanks a ton. have been struggling with it for a while now. thanks!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I felt E was harder than F. I spent wayy too long on E. Shouls have attempted F first.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is there a "Tie" in the second test at problem D?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Each player takes the largest number so their opponent can't take it. So Alice takes 3, then Bob takes 2, than Alice takes 1, after that score is 0:0. This is optimal for both players. If Alice takes 2 in first turn then Bob will take 3 and win, so she has to take 3 herself. Same logic aplies after first move.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody please explain C ?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you be a bit more specific as to what you didn't understand?

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please help me out for question D. My submission is showing runtime error on testcase 1 but it works fine on my ide

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah, just select g++ 17 instead of whatever variant you're selecting right now, also your logic fails the further test cases.

    incase you need to see the correct code similar to yours, you can go through mine :https://codeforces.com/contest/1472/submission/103348877 however even this is a too slow code and can be made better by using pop_back instead of erase. but anyway it passes the test cases. :)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You pass odd.size() - 1 as a parameter — size() (in many implementations) returns an unsigned 64-bit value, so if it's 0 the result after subtracting will be the highest representable value. However, that is converted to a signed long long, and since the value is greater than can be represented in a long long, the value is implementation-defined.

    You can cast the result from size() to a signed type first.

»
12 days ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Is there any way that I can uphack my solution to G. It's linked here 103279910. I have tested it on custom invocation on CF and I know there is definitely a case that makes it TLE. I waited out the hack phase since I wanted to keep my rating, but now I don't see the option to hack it anymore.

EDIT: I think you have to be 1900+ to uphack. Here is my generator that would cause my solution to TLE. https://pastebin.com/uYxwMnYz

Any1 who is eligible to uphack, go for it :)

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Link1 Link2

Problem E.

Link1 solution is accepted wherease link2 is not. The only diff between the 2 solutions is that for pair(hi,wi) whose hi is least is being calculated differently:-

In link1: let the main loop take care of everything

In link2: comparing all (hj,wj) with (hi,wi) for second condition [wj < hi && hj < wi = > ans[i] = j] [Since first condition can never be satisfied]

Why does link2 solution fail?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone link a good video solution for E? thanks

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://codeforces.com/contest/1472/submission/103375747 this happens to be a self explanatory code.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for me it is always hard to understand other people's code, can you please elaborate how did you solve it? did you follow editorial's method or your own different method?

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        same here, anyway I guess the code they've provided is too complicated and involves a lot of things like binary search etc. i have rather written a much simple code. here is how I did it

        1. make a vector having 3 fields -> height, width and index

        2. before populating the vector sort the height width in decreasing order OR just swap height with width if width>height.

        3. now sort the vector populated above, such that the first field (height) is the dominating factor, in case 2 elements have same height then compare width.

        4. After step 3 you'd be having a pretty much sorted vector. Now the only thing that remains is going through the sorted vector(left to right), and keeping a check of a the smallest width encountered till now (as heights are already sorted they need not be checked), however one edge case needs to be verified, the minimum value of width could be of a element having same height as the current element, hence i've used another variable for it,

        5. for every element having index(3rd field) 'i'if above condition is met by a previously encountered element having index 'j' then save ans[i]=j; else ans[i]=-1;

        I guess I might have missed a few/many things (lemme know if you know any further explanation).

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the DP state/solution for D no. problem? I can just feel the greedy approach. But problem tag shows DP too.

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Another way to think about E:

We can think about the pairs $$$(h_i, w_i)$$$ and $$$(w_i, h_i)$$$ as points on a 2D plane.

Then the problem becomes: for each point $$$P(h_i, w_i)$$$, find if there is any point that lies completely inside the rectangle that is formed by the origin $$$O(0, 0)$$$ as its bottom left corner and $$$P$$$ as its upper right corner.

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

I've uploaded my post-contest stream to YouTube: https://youtu.be/nCSLlTCDnDs

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please point out what is the mistake in this solution 103260792 for problem D? I hope this is the correct place to ask... Thanks!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use long long instead of int for storing the sum as the range of int is small for storing sum in worst case.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why my code is giving TLE for 1472E — Correct Placement.

I have swapped w and h whenever w>h while storing the inputs in a vector. I have then sorted the vector, found index of hj for every hi such that hj<hi using binary search. I have stored the index of the smallest value of w from indexes 0 to i in the sorted vector in an array b. At last, I choose w for every hj from the array in O(1) after checking the required condition.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For D how can this input be a tie? 3 2 1

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alice will pick 3 in his first move(because he picks 2, then bob will pick 3 and wins thereafter), Then bob will pick 2(same reason for 1). Then alice will pick 1 at end. Both will have 0pts at the end.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1472/submission/103513913 Can anyone tell me what is wrong with this? It is for the Problem G.

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone who solved D explain thought process/mental steps leading to solution?

Is there any general approach to similar problems?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please help me,I Am getting different answer in different online compilers. (Problem B) (link to my solution: https://codeforces.com/contest/1472/my) Thanks.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    first of all you used a variable 'z' for size of array , and also you used it as variable to count number of 2 present , and also after correcting this , your code will not give right answer for test case — {2,2,2,1,1}

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem E VIDEO TUTORIAL LINK : https://www.youtube.com/watch?v=M8jqjbJjoxA I HAVE TRIED BY BEST TO EXPLAIN WITH PROPER INTUITION(twopointer + dp)SO THAT YOU CAN UNDERSTAND EASILY . I HOPE YOU GUYS WILL ENJOY THIS VIDEO !!!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV 3 PROBLEM C VIDEO TUTORIAL LINK https://www.youtube.com/watch?v=7FFzXk-brRU I have tried my best to give you guys proper intuition of this dp problem. Hope you guys will enjoy this video !!!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find the complexity of this code:103390550? It just barely passed the 4s time limit.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me why my problem C solution is having a memory exceeded limit? What should i change to make it more memory efficient? 103327344 — Here i thought i used dp to max it faster but my other solution(103317010) without dp was quicker. Can anyone explain why this is?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E from my view:

  • Always assume that w<h, (if found w > h, we want to swap them), sort the array of (w, h)s in ascending order, we may want to save index (for tracking indexes)

  • Traverse the sorted array from left to right, for each i-th pair (w, h), i.e. (wi, hi), the problem becomes searching for j (j = 1..i-1) where wj < wi and hj < hi Now that we have wj <= wi for any j in 1..i-1, we only needs to binary search for upper bound of j which wj not exceed wi-1, let's call the bound is k

  • The only problem is we want to search for some j in 1..k where hj < wi. Let's construct a min array in such a way that min[k] = min { hj, 1 <= j <= k }, we also want to maintain 'argmin' array to store index which contains min

Then, result of finding j where hj < wi is j = argmin[k]

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain the DP approach from problem B?

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

I cant stand the fact that the dude on problem E invite n friends 1<= n <= 2 * 10^5 to celebrate new year! Guys we are in corona virus pandemic we should be more carefull! Imagine what will happen after 14 Days if there was someone with corona in the party! Be more carefule stay home and code, stay safe :D

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Simpler solution for F: 103672111

  1. Sort the blocked cells by x, y
  2. Pair the adjacent(after sort) blocked cells in disjoint pairs.
  3. Between blocked ceils within the same pair: distance has to be odd(or opposite color in chess grid as described in editorial)
  4. Between the second cell from ith pair and first ceil from i+1th pair: they cannot be on the same column. Otherwise it's going to block the flow of white cells, which is going to create an odd number of white cells in both side, which is impossible to fill.
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem G: can someone explain on what basis the second kind kind of action is taken?

for example :

// if there are cities "A", "B" and "C" of distance 3 having a road to city "D" of distance 4, and with 2nd kind of action city "D" can become of distance 1 making all cities "A", "B", "C" and "D" of distance 1.

// we have city "A" of distance 3, has a road to city "E" of distance 4 that can be reduced to distance 0 with 2nd kind of action, making "A" and "D" of distance 0.

which one should be chosen??

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

for 1472D - Even-Odd Game it shows a dp tag , but I am not able to solve with dp if anyone has solved with dp please post ur solution

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry I am a noob...but what will be the complexity of this algorithm??

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there is a graph tag in problem C?

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i need help..! submission to D.

Please find what is wrong with this code Your text to link here.... i am not able to find any error.! it is giving runtime error.!