priy1712's blog

By priy1712, history, 8 months ago, In English

The info I am given : block_ID, block_width, block_height as well as how the cuts between the rectangles are(horizontal or vertical); for example two rectangles can be joined by a horizontal cut or a vertical cut. See above picture for greater clarity(H symbolizes horizontal cut and likewise V for vertical cuts). The order of cuts on the blocks can be represented as a normalized polish expression or a skewed binary tree.

What i tried till now : I tried using a stack based approach where I would push the digits in the polish expression into a stack and would pop the top 2 elements from the stack when I came across a character(H OR V) and then join these 2 blocks (take max of height and add the widths for vertical cuts and vice versa for horizontal) and push this new 'edited' block into the stack again.The issue arises when I try to join the plots of 2 different subtrees.

Code for the same :

def plot_floorplan_area(blocks, polish_expression,num_blocks):
    # Initialize the plot
    curmax=num_blocks
    fig, ax = plt.subplots()
    ax.set_xlim(0, xmax+5) 
    ax.set_ylim(0,ymax+5) 
    ax.set_xlabel('Width')
    ax.set_ylabel('Height')
    ax.set_title('Floorplan')
    x, y = 0, 0
    stack=[]
    for c in polish_expression:
      if c.isdigit():
        stack.append(int(c))
        c=int(c)
        c-=1
        curwid=blocks[c][1]
        curht=blocks[c][2]
        left_bottom=(x,y)
        rect = Rectangle(left_bottom, curwid, curht, linewidth=1, edgecolor='r', facecolor='none')
        center_x = left_bottom[0] + curwid / 2
        center_y = left_bottom[1] + curht / 2
        ax.text(center_x, center_y, str(blocks[c][0]), ha='center', va='center', fontsize=12)
        ax.add_patch(rect)
      elif c=='H':#horizontal cut.
        el1=stack.pop()
        el2=stack.pop()
        el1-=1
        el2-=1
        curwid=max(blocks[el1][1],blocks[el2][1])
        curht=blocks[el2][2]+blocks[el1][2]
        rect = Rectangle(left_bottom, curwid, curht, linewidth=0, edgecolor='none', facecolor='none', alpha=0)
        x+=curwid
        y+=curht
        curmax+=1
        stack.append(curmax)
      elif c=='V':
        el1=stack.pop()
        el2=stack.pop()
        el1-=1
        el2-=1
        curht=max(blocks[el1][2],blocks[el2][2])
        curwid=blocks[el2][1]+blocks[el1][1]
        rect = Rectangle(left_bottom, curwid, curht, linewidth=0, edgecolor='none', facecolor='none', alpha=0)
        x+=curwid
        y+=curht
        curmax+=1
        stack.append(curmax)
    plt.grid(True)
    plt.show()

Structure of a row of the blocks matrix : {ID,width,height,area} .

Could anyone tell me alternate approaches/corrections to the existing approach as this one is yielding wrong outputs.

Example of a polish expression : 1 2 V 3 H 4 5 6 V H 7 V H. It is basically the post order traversal of the above tree.

This is what the final floorplan should look like.

Full text and comments »

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

By priy1712, history, 8 months ago, In English
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ci(n) cin>>n
#define co(n) cout<<n
#define nl '\n'
#define r0 return 0
#define LLMAX LLONG_MAX
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define printstr(s) for(int i=0;i<(int)s.size();i++) { cout<<s[i];}
typedef std::pair<int, int> pp;
typedef long long ll;
typedef std::vector<ll> vl;
typedef std::vector<std::pair<int, int>> vp;
typedef std::vector<int> vi;
typedef std::unordered_map<int, int> unmap;
typedef std::unordered_set<int> unset;
typedef std::unordered_set<char> unsetc;
using namespace std;


const int max_size = 100005;
vector<bitset<1005>> b(max_size);//matrix of bitsets.
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // unordered_map<ll, ll> mp;
    // mp.reserve(1024);
    // mp.max_load_factor(0.25);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll n, q;
    ci(n); ci(q);
    for (int i = 1; i <= n; ++i)
    {
        ll k;
        ci(k);
        for (int j = 0; j < k; ++j)
        {
            ll item; ci(item);
            b[i].set(item);//in stock.
        }
    }
    while (q--)
    {
        int curquery;
        ci(curquery);
        // co(curquery); co(nl);
        if (curquery == 1) //have to replace items in a shop
        {
            ll shop; ci(shop);
            ll k;
            ci(k);
            // const int curk = k;
            bitset < 1005> items;
            items.reset();
            for (int i = 0; i < k; ++i)
            {
                int x; ci(x);
                items[x] = 1;
                b[shop] &= items;//the common ones will stay 1.
                //others will become 0.
            }
        }
        else
        {
            ll l, r; ci(l); ci(r);
            ll k; ci(k);
            bitset < 1005> items;
            items.reset();
            for (int i = 0; i < k ; ++i)
            {
                int x; ci(x);
                items[x] = 1;//items he is willing to sell. the shopkeepers
                //will buy only if their intersection with the chef is 0.
                //that is , no common items
            }
            bitset<1005> cur;
            cur.reset();
            ll res = 0;
            for (int i = l; i <= r; ++i)
            {
                cur = b[i];
                cur &= items;
                if (cur.count() == 0)
                {
                    res++;
                }
                cur.reset();
            }
            co(res); co(nl);
        }
    }
    r0;
}

The above code compiles fine and gives the correct output too on my local machine but its TLEIng when I submit it to the OJ, could anyone help me out? thanks. The problem statement : https://www.codechef.com/problems/T30?tab=statement

UPD: it works fine on codeforces custom invocation too.

Full text and comments »

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

By priy1712, history, 11 months ago, In English

I am currently a newbie ,started giving contests about a month ago and I am mostly able to solve div2 and div3 A and B problems in the contests I have given till now. But that is where I get stuck , I am not able to solve the C problems. Edit: reached pupil after Div3 916

Full text and comments »

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