2 "Hours" ago.

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.

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

problem D was almost same as this one.

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

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

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.

yeah,I have the same question.

That's ok.

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

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.

h

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

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.

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.

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:

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

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!

Distance to 4 is equal to 2 by 1>5>4, not 3.

Can someone explain why 6->2->5->1 isn't a valid path for the first testcase of the sample input for problem G? I'm pretty confused cause we go 6(2) -> 2(1) -> 5(2) -> 1(0).

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

this makes question very easy. thanks

How is this not true?

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.

Donald trump complaining even on someone solving a problem faster. Not surprising.

Your dp size is 20000 instead of 200000

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.

I had two use greedy approach for this but I am willing to know it's do solution and fault in my code. Thanks in advance.

Name of the ID please.

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

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.

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

I hope this helps. Now for the coding phase,

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

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

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

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

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.

Yes , link to my submission https://codeforces.com/contest/1472/submission/103216440

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.

Thankx Bro ! your A with comments was easy to understand!

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.

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

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

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.

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

Maybe this is causing some problem

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.

Have a look at the video by galen_colin: https://www.youtube.com/watch?v=p5FNuXJoLDk&t=1054s

Exactly what you are not able to understand?

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

} `

I wrote my solution here.

Make score long long

See this and this.

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)

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.

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

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

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.