### Jamshed11's blog

By Jamshed11, history, 4 months ago,

Hello Codeforces!

Craving for a coding challenge? Get ready because Pulzion Tech or Treat is throwing a feast full of Codelicious treats for you to dig your fangs into.

I invite all of you to join and take part in Codelicious, the worldwide coding challenge featured in Pulzion Tech or Treat, the annual flagship event of PICT ACM Student Chapter.

You will be served 6-8 problems in a time frame of 2 hours to solve and savor them.

Special thanks to yashss1, admiralpunk111, harshpatil2104, vijaymunde_02, Nachiket, adsulswapnil27, Shreekar11 for their valuable contribution.

Registrations:
Only registrations via the website will be considered valid and will be eligible for the prizes. To register, please refer to our website: https://pulzion.co.in/

Contest Details:

Global Prizes:
Rank 1 from leaderboard: 100 USD
Rank 2 from leaderboard: 75 USD

Indian Prizes:
Rank 1: Rs 6000
Rank 2: Rs 4000

Pulzion App: https://shorturl.at/xCJLU

NOTE: Prizes are subject to change under unavoidable circumstances. Management is not responsible for the change in the pool. Final decision lies in the hands of the organizers. In case any country has any restrictions on prize money transfer we shall not be responsible.

• +43

By Jamshed11, 5 months ago,

If you are someone who writes normal DP code first and then converts it to space optimized one, you can use this trick.

If our problem involves n * k states for DP, and at any point our state transition involves only moving from dp[i][x] to dp[i][y] or from dp[i][x] to dp[i + 1][y] i.e from i th layer to i th or i + 1 th layer, we can solve it in O(k) space.

But many times I first write code that uses O(n * k) space and then I optimize the space complexity. (It's easier for debugging)

Code that uses O(n * k) space looks something like this:

vector<vector<ll>> dp (n+1, vector<ll> (k+1));

dp[0][0] = 1;

for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < k; j++)
{
//State transitions from i th layer to i th or i + 1 th layer
dp[i][j+1] += dp[i][j];
dp[i+1][j+1] += dp[i][j];
}
}


E.g. 224168964

To convert this code to use O(k) space, I create 2 1-D vectors named dp and newDp and replace every occurrence of dp[i] with dp and every occurrence of dp[i+1] with newDp, and at the end of the first for loop I assign dp = newDp.

Code that uses O(k) space looks something like this:

vector<ll> dp (k+1);

dp[0] = 1;

for (ll i = 0; i < n; i++)
{
vector<ll> newDp (k+1);

for (ll j = 0; j < k; j++)
{
//State transitions from dp to dp or newDp
dp[j+1] += dp[j];
newDp[j+1] += dp[j];
}

dp = newDp;
}


E.g. 224028960

Instead of doing all these replacements I came up with a better idea.

The idea is my code will be very similar to the code that uses O(n * k) space. The only difference will be at the start of the i th layer I will assign memory to i + 1 th layer and when I am done with the i th layer I will release memory of i th layer i.e in the first for loop at the beginning I will do dp[i+1].assign(k + 1, 0); and at the end I will do dp[i].clear(); dp[i].shrink_to_fit();

Code that uses O(k) space using this trick looks something like this:

(It actually uses O(max(n, k)) space)

vector<vector<ll>> dp (n+1);

dp[0].assign(k + 1, 0);
dp[0][0] = 1;

for (ll i = 0; i < n; i++)
{
dp[i + 1].assign(k + 1, 0);

for (ll j = 0; j < k; j++)
{
//State transitions from i th layer to i th or i + 1 th layer
dp[i][j+1] += dp[i][j];
dp[i+1][j+1] += dp[i][j];
}

dp[i].clear();
dp[i].shrink_to_fit();
}


E.g. 224031624

Note: Only using dp[i].clear(); will still give you MLE as it only removes all elements from the vector but the underlying storage is not released. You need to use dp[i].shrink_to_fit(); to actually release the memory.

• +45

By Jamshed11, history, 10 months ago,

Recently I had to create large Test Cases for trees so I came up with an idea that involved the use of PBDS / Ordered Set.

So I created 2 pbds. One pbds for storing nodes I have included in the tree and the other for storing the remaining nodes. I will take 1 random value u from the first pbds and another random value v from the second pbds and then print u and v (i.e add edge between u and v). Then erase v from second pbds and insert it in first pbds cause now v is also included in the tree. I used pbds as it allows me to take any random value from it and also erasing it in log n time.

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define pbds tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>

void treeTCgenerator()
{
ll numberOfNodes = 1e5;

srand(time(0));

cout << numberOfNodes << "\n";

pbds includedInTree;
pbds notIncludedInTree;

ll root = 1;//almost centroid

//uncomment the below line to create random root
//root = ((ll) rand() * rand()) % n + 1;

includedInTree.insert(root);

for (ll i = 1; i <= numberOfNodes; i++)
{
if(i != root){
notIncludedInTree.insert(i);
}
}

for (ll i = 0; i < numberOfNodes - 1; i++)
{
ll r = rand();
ll incSize = includedInTree.size();

r %= incSize;

auto itU = includedInTree.find_by_order(r);
ll u = *itU;

r = rand();

ll notIncSize = notIncludedInTree.size();

r %= notIncSize;

auto itV = notIncludedInTree.find_by_order(r);
ll v = *itV;

notIncludedInTree.erase(itV);
includedInTree.insert(v);

cout << u << " " << v << "\n";
}
}


Time Complexity: n * log n

The first value you insert in the first pbds will be close to the centroid of the tree.

Using srand(time(0)) is important otherwise it will create the same tree again and again. If you want to create a test case that involves multiple test cases then call srand(time(0)) function in your main function and remove it from treeTCgenerator function. Cause if we don't remove it then it will get called for each test case. And calling srand(time(0)) again and again also causes the problem of getting repeated random values from rand() function.

Here I have used cout for printing values. You can directly print these values in a file also.

If there are better methods for creating TC for trees please let me know.

• +9

By Jamshed11, 11 months ago,

Hello Codeforces!

Pune Institute of Computer Technology (PICT) would like to invite you all to Pradnya 2023.

Pradnya is a programming event that puts the programmer’s logical thinking and problem-solving skills to the test using programming languages.

Team Size: Maximum 2 members
Date: 21 to 23 April 2023
Total Prize Pool: 50000 INR +
Registration Fees For Indian Citizens: 100/- INR per team
Registration Fees For Out of India Citizens: 0/- INR per team

Eligibility Criteria:

• Junior Level: This category is open for all students who are pursuing first or second year of any undergraduate degree/course.

• Senior Level: This category is open for all students who are pursuing third or final year of any undergraduate degree/course.

Register (For Pradnya Event), FE/SE/TE/BE Coding Competition for National Entries (FOR INDIAN CITIZENS) https://pictinc.org/register/events/pradnya

Register (For Pradnya Event), FE/SE/TE/BE Coding Competition for International Entries (FOR OUT OF INDIA CITIZENS) https://forms.gle/7MDV7tSo6sjP2KqC7