Saksham_Sahgal's blog

By Saksham_Sahgal, history, 2 months ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By Saksham_Sahgal, history, 3 months ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Saksham_Sahgal, history, 4 months ago, In English

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?

How to reach the Conclusion -

Conclusion -

Hence if xor is zero B Wins , else A wins

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By Saksham_Sahgal, history, 5 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Saksham_Sahgal, history, 5 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By Saksham_Sahgal, history, 5 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By Saksham_Sahgal, history, 5 months ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

By Saksham_Sahgal, history, 7 months ago, In English

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;
        size_t answer = 0;

        for (int i : myVector)
        {
            answer ^= hasher(i) + 0x9e3779b9 +
                      (answer << 6) + (answer >> 2);
        }
        return answer;
    }
};

Full text and comments »

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

By Saksham_Sahgal, history, 7 months ago, In English

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)

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it

By Saksham_Sahgal, history, 7 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Saksham_Sahgal, history, 8 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By Saksham_Sahgal, history, 9 months ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Saksham_Sahgal, history, 10 months ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

By Saksham_Sahgal, history, 14 months ago, In English

Link to my submission

My approach was to map characters 'a' with the first character in the string then ,'b' with the second character in the string .. and so on , then while taking input of the N strings I converted those string(X) to a mapped string(Y) (each character conveted to its mapped value) and stored that mapped string(Y) in a multiset key with vaue as the original string(X), i did this as multiset will sort the keys lexographically and then i just printed the values of the map,

the first two given testcase gives right ans , but i dont understand why all other testcases give WA.

ps. i also solved it with custom comparator function which got AC(As expected) , but i don't understand why this approach gives me WA

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it