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.

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

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!

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,

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.

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.

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.

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