### Saksham_Sahgal's blog

By Saksham_Sahgal, history, 2 months ago,

It has become a trend for all contests , that A , B , Cs will almost always be constructive , and even after solving a lot of these questions , I mostly seem to get stuck or sometimes take a lot more time than usual to solve these questions.. I just feel like , i'm stuck and can't improve any further, can anyone help?

• +2

By Saksham_Sahgal, history, 3 months ago,

I recently started learning python , so I was looking for some C++ STL equivalents in Python. is there any way i can achieve a similar functionality of —

Set and Maps in python with —

insert (log n)
delete (log n)
find (log n)


as fas a I Understand Python Standard Sets are not sorted and are implemented using Hash-Tables (similar to unordered-Sets in C++) has —

insert (O(1) average case , Worst case O(n) [when large no of values have same hash value])
delete (O(1) average case , Worst case O(n) [when large no of values have same hash value])
find (O(1) average case , Worst case O(n) [when large no of values have same hash value])


I know there is a third party package called sortedcontainers which has some C++ equivalents —

std::set    sortedcontainers.SortedSet
std::multiset   sortedcontainers.SortedList
std::map    sortedcontainers.SortedDict

but I want to get these funcionalities without installing any third party packages (because those would be local to my environment), and I want to submit to codeforces.

can anybody help?

• 0

By Saksham_Sahgal, history, 4 months ago,

## What is Nim Game and how it is played?

• It is a game in which two players play optimally turn by turn .
• In each turn a player can choose only one pile and remove any number of stones (at least one) from that pile.

• The person who is unable to make a move looses , hence the player who makes the last move wins.

• determine which player wins the game.

### How to decide who will win?

• To decide who will win the initial configuration of the piles matter.
• If the xor of all elements of the array is non-zero , then person starting the game will win.

• If the xor of all elements of the array is zero , then other person will win.

• Proof

### Why it works ?

• if the xor if all elements is zero then if we make any moves , the xor of all elements will definitely become non zero .
Why?
• If the xor of all elements is non zero , then we can either make the xor non-zero again , or make the xor zero.
• There definitely exists atleast one way to make xor zero again.

Why?

## Conclusion -

Hence if xor is zero B Wins , else A wins

• +13

By Saksham_Sahgal, history, 5 months ago,

Is there any website/tool that displays heatmaps and other related statistics of a profile of Codechef?

• +1

By Saksham_Sahgal, history, 5 months ago,

Can anyone tell me how the output of Test case 3 of Problem is —

9 9 9 15 15 6 -1 -1 6 -1 -1 -1 -1 6 15

and not —

9 9 9 -1 8 6 -1 -1 6 -1 -1 -1 8 6 8

the as far as i understand — i have to perform N moves , where -

1. Draw the topmost card from the deck. Let X be the integer written on it.
2. Then i will find a stack of upfacing cards with the smallest integer greater than or equal to X written on and and i will put this X card into that stack .
3. if there is not such stack then i will put this card into a new stack.
4. if any stack has k cards i will eat that stack.

for input —

15 3 3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

According to me the steps should look like —

• 3 (new stack)
• 3 14 (two new stacks)
• 3 14 15 (three new stacks)
• 3 ( 14 9 ) 15 (9 goes to stack 2)
• (2 3) ( 14 9 ) 15 (2 goes to stack 1)
• (2 3) ( 6 14 9 ) 15 (6 goes to stack 2)
• now stack 2 to is eaten because it has size = 3 (therefore 6 , 14 , 9 is eaten at step 6)
• (2 3) (5 15) (5 goes to stack 3)
• (2 3) (13 5 15) (13 goes to stack 3)
• now stack 3 to is eaten because it has size = 3 (therefore 13 , 5 , 15 is eaten at step 8)
• .
• .
• . -and so on..

can anyone tell me where i am getting it wrong? thanks in advance

• +2

By Saksham_Sahgal, history, 5 months ago,

Even after a lot of Practice why do I perform well in virtual contest but fail to perform well in real contests? . How can I overcome the fear of rating fall , and learn to perform well under pressure ? Does anyone have any suggestions that would help?

I had been giving some virtual contests , and i see i mostly perform well in them , and get a good rank , but in actual contest i almost always end up performing bad , even though i know i could have easily solved those questions if i was not under pressure .

Any suggestions for overcomming this would be really helpful :>

• +4

By Saksham_Sahgal, history, 5 months ago,

I get this when i submit code —

but when i run my exact same testcase in test against custom input window i get —

which is the correct output.

here is my submission — Submission

what am i doing wrong?

• -18

By Saksham_Sahgal, history, 7 months ago,

can anyone tell me how to make a custom hash for an —

unordered_set< pair < unordered_set<vector< int > , hashFunction > , vector< int > > >

where hashFunction is a custom hashFunction for unordered_set<vector> .

here it is —

struct hashFunction //hash function for unordered set

{

size_t operator()(const vector<int> &myVector) const

{
std::hash<int> hasher;

for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
}
}
};

• -9

By Saksham_Sahgal, history, 7 months ago,

Given a weighted undirected graph , a source vertex(s) and x distinct vertices as Delivery Location (d1 , d2 , d3 .. dx) assuming that each rider travels at 1m/s what is the min time required to complete all the deliveries if you have M drivers originating from the source simultainously , and also the path followed by them.

( it is guarented that reaching all delivery locations from the source vertex is possible )

input format -

n m s M                            //n vertices , m edges , s is the source vertex , M no of drivers

v11 v12 w1                         //vertices connected with weight w

v21 v22 w2

..

vm1 vm2 wm

x                            // no of delivery locations 1<= x < n

d1 , d2 , d3 , d4 .... dx               //delivery vertices (d[i] != s for all 1 <= i <= x)

output format - (M+1 lines first line should contain the min time required and all others M lines should include paths followed by drivers from 1 to M)

t               //min time to complete all deliveries

1->3->5               // path followed by first delivery guy

1->2->1->5               // path followed by second delivery guy

1->               path followed by third delivery guy (it may be possible that this delivery person didn't moved so his path finished at source only)

(all paths should start from source only)

• +21

By Saksham_Sahgal, history, 7 months ago,

given a NxM integer matrix and i1,j1,i2,j2

such that i1 < i2 and j1 < j2

tell in O(1) that whether all elements in the rectangular submatrix formed by (i1 , j1) , (i1 , j2) , (i2 , j1) , (i2 , j2)

contains all same elements or not .

example —

input —

6

0 1 1 1 0 1

4 4 4 4 1 0

1 2 2 4 2 4

1 1 2 2 2 4

4 4 4 4 2 4

4 4 4 4 4 0

4 0 5 3 // zero based indexing , i1 , j1 , i2 , j2

output — yes

• 0

By Saksham_Sahgal, history, 8 months ago,

Given a Binary String and a number x , tell whether there exists a continuous substring with ( no of zeros — no of ones ) = x output its index l to r (0 based indexing) eg —

string = 1 1 0 0 1 0 0 1 0 0 1 0 1 1

x = 3

output — (you can output any possible l to r)

YES , from index 2 to index 6

OR

YES , from index 2 to index 8

• +5

By Saksham_Sahgal, history, 9 months ago,

Can anyone help me figure out what is wrong in my Code , the poblem is pretty straight forward and i Implemented it using PBDS , but i am getting WA in 5 added Testcases . Here is my submission Link — Submission

• 0

By Saksham_Sahgal, history, 10 months ago,

i recently encountered a problem — 1208B - Уникальность

I have use a simple Binary search approach for that problem

I have 2 submissions , both are using Binary search and both have same worst case time complexity of O(N^2 log^2(N)) but one gives TLE and the other gets AC

AC submission — 146479295

TLE Submission — 146333083

can anyone tell me why this is happening?

• -19

By Saksham_Sahgal, history, 14 months ago,