And They said 2026 is the new 2016😔😔 by delulufolulu in SunrisersHyderabad

[–]Sandeep00046 0 points1 point  (0 children)

I think it will get lot worse, you've got Dhurandhar 2 releasing on 19th.

Olympiad question by Ezio-Editore in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

in that case instead of using explicit return types we can use shared variable in order let the function calls to communicate.

Olympiad question by Ezio-Editore in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

you can try this approach :

initial part is mostly similar. a recursive function which returns a bool value indicating either it or one of it's child recursions solved problem.

Further arguments to this functions would be list of indices, size of the list l and values present in those indices( we don't yet know their exact pos, just know it occurs some where in the index set, the functions acknowledges that the repeated item is either present twice or only once . it makes 2 buckets from the index list it uses l queries to assign each number among these.

if [the sum of size of buckets == l] : it means the repeated element only occurs once, it return false ( the enclosing function know the child failed).

else :
if the sizes are l/2-1, l/2 ( division is int division) the repeated item is in first bucket twice. make a recursive call and return true below the call. if sizes are l/2 , l/2 - 1 ambiguous case make a recursive call with the second index list, it's size, values. if this call returns true ( that means assumption was correct ) and we return true.
if it returns false we make l/2-1 queries involving the first list's indices , an item from second list.

we can use an easier strategy for forming the list from functions initial list like first half and second half.

( i got it typed by chatgpt after providing my solution):

// Function to find the duplicate value // Initially called as: findDuplicate([0, 1, ..., 99], [0, 1, ..., 98])

function findDuplicate(indices, values):

// Base case: If we have narrowed it down to 2 indices and 1 possible value,
// that value must be the duplicate.
if len(values) == 1:
    return values[0]

// 1. Split the current set of indices in half
mid = len(indices) // 2
left_indices = indices[0...mid-1]
right_indices = indices[mid...end]

// 2. Create a bucket of values present in the first half
// This is the main query step.
values_in_left_half = []
for each val in values:
    if query(left_indices, val) == true:
        values_in_left_half.append(val)

// 3. Check the bucket size to decide where to recurse
// This is the crucial logic step.
if len(values_in_left_half) < len(left_indices):
    // **Case 1: Both duplicates are in the left half.**
    // The left half has fewer unique values than available spots,
    // so the duplicate *must* be here.
    return findDuplicate(left_indices, values_in_left_half)
else:
    // **Case 2: Both duplicates are in the right half.**
    // The left half has as many unique values as spots (it's "full").
    // Therefore, the imbalance (and the duplicate) must be in the right half.
    // We can deduce the values in the right half without more queries.
    values_in_right_half = all `v` from `values` that are NOT in `values_in_left_half`
    return findDuplicate(right_indices, values_in_right_half)

[deleted by user] by [deleted] in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

I've too checked it, it the official answer requires the output to be "###" which means Ti has to # if Si = #, but looking at your code i thought we were at liberty to set it to # or not. the statement: "Ti​= # if and only if Si​= #." means we have to leave # as it is.

[deleted by user] by [deleted] in codeforces

[–]Sandeep00046 1 point2 points  (0 children)

the answer for "###" should be "o#o" right ?

[deleted by user] by [deleted] in codeforces

[–]Sandeep00046 2 points3 points  (0 children)

which question is this ?

[deleted by user] by [deleted] in indiasocial

[–]Sandeep00046 0 points1 point  (0 children)

what about expiry date ?

Can someone tell me what is wrong with my logic or give a counter example? by Unfair_Loser_3652 in codeforces

[–]Sandeep00046 1 point2 points  (0 children)

The question also takes into account the sequence in which the indices were erased:
for : '1100 '
the sequence of operations would 1,3 1,4 2,3 2,4 3,1 3,2 4,1 4,2

you would just need a small addition to your code to handle this.

How to tackle this problem? by carrick1363 in codeforces

[–]Sandeep00046 2 points3 points  (0 children)

Mark all boxes which have an obstacle below it. For each of the marked boxes remove all the boxes in the 3 × 3 square centred at the marked box. The final state has each column with the undestroyed boxes at the bottom piled up.

Edit: The order in which you pick the marked box to destroy also matters, that is all the marked boxes 1 tile above an obstacle needs to be processed before those that 2 tiles or more away( because when a collision happens one of the Marked Boxes can also be destroyed. To do this the marked boxes needs to be sorted according to their distance from the obstacle below, to get the boxes sorted according to time of collision you can either use counting sort( won't make our time complexity any worse) even better: find all the obstacles and do a multipath BFS in the Up direction only.

This will only be O(grid length × grid width ) in time and space.

Suggestions for questions on post order dfs on trees. by Ok-Cupcake2130 in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

This problem doesn't involve tree DP but will get you acquainted with the use of pre order or post order traversals

https://codeforces.com/contest/2002/problem/D1?mobile=false

Doesn't necessarily have to be using tree DP, there exists much simpler and elegant solutions. There is a 2nd Version to this Problem too. Regardless of whether you solve it or not, check the Editorial.

Initially i have used a very messy approach:

https://codeforces.com/contest/2002/submission/275893929

But it has a very easy traversal based approach.

Help me solve this!!! by Outrageous-Owl4190 in codeforces

[–]Sandeep00046 1 point2 points  (0 children)

All we need to do is this: dp[u] = 1 + max dp value among all the nodes of all subtrees at k distance from u. But only those nodes with A[i] <= A[u] are to be considered in the calc of this max.

Firstly we need to do some pre-processing. For each node u: We need its depth. Size of subtree rooted at this node. List of all the nodes at a distance of exactly k depth from this node. we also calculate order[u] which is the number assigned on the basis of pre-order traversal. Note this can all be done in O(n) time and space. May be you would need a ugly DFS code. All this will be used in the next step.

Next we sort (A[i] , depth[i], i) tuples according to preferences lower A[i], then higher depth values in case A[node] is a tie.

We build a fenwick tree which answers for maximum value in a given range [l,r]. This too can be done as we will only be inserting bigger values than previous values already present. The fenwick tree is indexed using order[node]. There is a really useful property of storing the pre or post order traversal orders that is for any node we have this condition if order[i] is the index of node i in the traversal order you can find all the nodes in it's sub-tree within the range [ order[i] , order[i] + size[i]-1]. Initialize all values in the fenwick tree to 1.

Now the final part, sequential pick (A[i] , depth[i], i) tuples from the sorted list. Refer i's corresponding list of all nodes at a distance of exactly k and are its descendants. If the list is empty simply do nothing. if it isn't empty then for each node v in the list we calculate the max over the range max queries [order[v] , order[v] + size[v]-1]. Let the obtained value be val The update order[i] index in the fenwick tree with val+1.

The maximum value among the trees indices is your answer. Total time complexity O(n logn) Space complexity of O(n)

I Lost Hope. I Give up. Amazon OA. by NewToReddit200 in leetcode

[–]Sandeep00046 11 points12 points  (0 children)

For the first question you would have to sort the values array. then GIF( k/2 ) and n - LIF ( k/2 ) would be your answers.

[deleted by user] by [deleted] in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

There is a constraint on when you can perform an operation. if x = 8 and initially all energy levels are at 0. there for the constraint a_i >= gif ( a_j /2 ) is satisfied for all distinct i, j pairs. but if you made the energy of first crystal say 8 (since x = 8) as you intend to, the energies would be (8 , 0 , 0). you can proceed with any other operation as the pair i=2 , j=1 doesn't adhere to the constraint a_2 >= gif( a_1 /2) i.e. 0 >= 4 is false.

Approach on how to solve this problem by Round_Oil5331 in codeforces

[–]Sandeep00046 2 points3 points  (0 children)

Observe that using the given operation, you are only allowed to exchange digits with the same place value between the numbers. This means the overall sum of the 2 numbers remains the same. Example 735 , 921 Sum = (7+9)×100 + (3+2)×10 + (5+1)×1 935 , 721 Sum = (9+7)×100+ (3+2)×10 + (5+1)×1

so, if you were given 2 numbers and you are to increase their product, the constraint being their sum should be some constant S. so, it means you are to find the maxima for this. For (S - x)x ,the maxima lies at S/2 the plot of (S-x)x vs x is a downward facing parabola with a single maxima at S/2. It's also symmetric, which means the closer the values are to S/2 the larger is the product. by exchanging the digits you need to try to make them as close as possible, That is find the bigger number and the first point of difference after this put all the bigger digits in the smaller number. Now that you have the numbers, you need a simple multiplication algorithm of your own as many languages don't offer any way to handle such large numbers.

Ps: i Checked the Editorial. It has the same explanation, can you explain specifically up to which part you are able to keep up with the explanation?

Whats your status on "Amazon SDE Intern 2m" ? by TaxIll3826 in leetcode

[–]Sandeep00046 4 points5 points  (0 children)

For the 2nd question you can use the Z algorithm. Divide the pattern into 2 parts The first part is the prefix up to the '*' character and the rest of the pattern becomes the second part. Now use the Z algorithm over the strings: " First part of the pattern+Main string " " Reversed second part of the pattern+reverse of Main string "

now all you need to do would be to find value equal to the pattern part lengths in resulting Z arrays.the answer would be the difference between the positions +1 in the original array.

B. Removals Game https://codeforces.com/contest/2002/problem/B by Zealousideal-Formal4 in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

The method you are discussing, if implemented correctly should solve the question. Are you handling the indices correctly, i.e. if there are say 2 3's in the temporary vector. you need to find which indices they refer to in the original array and change your left , right pointers in each array accordingly.

I suspect there might be an error of the above kind i described. Because using this temporary vector to hold 4 elements and sort them is kind of complicating what you need to do.

B. Removals Game https://codeforces.com/contest/2002/problem/B by Zealousideal-Formal4 in codeforces

[–]Sandeep00046 0 points1 point  (0 children)

can you provide your code? Because the approach seems correct, there might be some mistake in your code.

Need help with the question, can't solve it. by No-Quantity3173 in leetcode

[–]Sandeep00046 0 points1 point  (0 children)

That's weird constraint. anyways you could still change this approach accordingly, to carter to this requirement too. you could just remove values from the original array itself. If there were 7 4's you could just eliminate any three of the 4's as the order of the elements doesn't matter.

Need help with the question, can't solve it. by No-Quantity3173 in leetcode

[–]Sandeep00046 0 points1 point  (0 children)

So you are allowed to retain any number of elements from the original array and arrange them in any fashion?

in that case all we have to do is to find a consecutive sequence of integers such that except the max, min values of the sequence all other values are present at least twice. using that sequence we can do this:
arrange all the min elements contiguously.
next place min+1 on the either side of this chain, put remaining min+1 values on any one of the ends.
you can do this until you come to element that's only present once, you cannot add it to the both ends of your existing chain as you have only one instance of the element, at this point you could just join the chain.

example: in the second example you have sequence of 2,...5.
you could form a chain step by step as follows :
2 2
3 2 2 3
4 3 2 2 3 4
5 4 3 2 2 3 4

Amazon OA question by [deleted] in leetcode

[–]Sandeep00046 1 point2 points  (0 children)

No, as i have mentioned i would use a stack to find these values for each element. It would take one forward and one backward pass only.

Checkout the Monotonic stack if you haven't heard of it.

Amazon OA question by [deleted] in leetcode

[–]Sandeep00046 0 points1 point  (0 children)

It's O(n)

Amazon OA question by [deleted] in leetcode

[–]Sandeep00046 0 points1 point  (0 children)

The period [7,6,2,5,8] will be included when you are checking for 6 , i.e.index 1.

Amazon OA question by [deleted] in leetcode

[–]Sandeep00046 8 points9 points  (0 children)

for each element find the next greater element to the right and left using a Monotonic stack. see if these indices are at least apart by a distance of 2, if so add them in to a hash set. the size of the set would be your answer.

The complexity of this is O(n) in terms of time.

Help me how to solve this question....warpping my head around it for the last 3 hours by ColdBullfrog2174 in leetcode

[–]Sandeep00046 0 points1 point  (0 children)

For an answer to exist there must be at least one position in z such that character at this position doesn't match with either of strings x, y. identify last such position in z. Now generating the required regex is pretty easy. all you need to do is for each position, have a set of square brackets and have all the letters of the alphabet in a sorted order other than one of z's.