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:

• Contest Link: https://www.codechef.com/CODL2023

• Contest Date: 26 October 2023, 20:00 IST

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.

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));

//Filling answers for initial states
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);

//Filling answers for initial states
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);

//Filling answers for initial states
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.

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.

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

Rounds in Pradnya:

• Wildcard Round: The wildcard round is open to both junior and senior teams, and the top 5 teams from each category will enter directly to the programming round (Round 2). This round will be conducted online on CODECHEF platform. The wildcard round will include programming questions where the participants can code using any programming language of their preference. Teams that qualify wildcard round will be exempted from participating in the multiple-choice questions round (Round 1).

• Round-1 (MCQ Round): The first round is the MCQ round where the participants will be given a mix of multiple-choice and short answer questions. All students whose colleges are located within the Pune district are required to attend this round in person at the PICT Campus on April 21st. For students residing outside of Pune district, there is an option to take the round in hybrid mode. The information regarding scheduled slots for this round will be communicated to the participants one day before the event.

• Round-2 (Programming Round): Winners in MCQ based round, and wild card winners are eligible for the Programming contest. Some Coding Problem statements will be allotted to each category i.e. Junior and Senior level. This round is held on an online programming platform. All students whose colleges are located within the Pune district are required to attend this round in person at the PICT Campus on April 22nd. For students residing outside of Pune district, there is an option to take the round in hybrid mode. The information regarding the timings for the contest will be communicated to the participants one day before the event.

• Round-3 (Judging Round): The top 5 teams qualifying round 2 will enter the judging round. During the judging round, the five teams will be evaluated by the judges based on their solutions from round 2. The judges will then select the top three winning teams. All students whose colleges are located within the Pune district are required to attend this round in person at the PICT Campus on April 22nd. For students residing outside of Pune district, there is an option to take the round in hybrid mode.

The last date for registration is 14th April 2023.

Refer to website (www.pictinc.org) for more details.