Grid L – Codeforces Round 1093 (Div. 2)

Problem Summary

Roger has:

• $p$ straight unit segments
• $q$ L-shaped pieces (each L uses 2 unit segments, one horizontal and one vertical)

He wants to use all pieces to build a rectangular grid of size $n \times m$.

A grid $n \times m$ contains:

• Horizontal edges: $H = m(n+1)$

• Vertical edges: $V = n(m+1)$

So the total number of unit edges in the grid is:

Available edges are:

So we must satisfy:

If no such $n, m$ exist, output $-1$.

Main Observation

Starting from:

Multiply by $2$ and add $1$:

Left side becomes:

But:

So we get the identity:

Let:

Then the problem becomes:

Divisor Transformation

If we find divisors $a$ and $b$ such that:

Then:

So:

Since $S$ is always odd, its divisors are also odd, meaning $(a-1)$ and $(b-1)$ are always divisible by $2$.

So the task becomes:

Find any divisor pair $(a,b)$ of $S$ giving positive integers $n,m$.

Extra Constraint (Important)

Even if the total number of edges matches, we must also ensure we can place all $q$ L-shaped pieces.

Each L-piece consumes:

• $1$ horizontal edge
• $1$ vertical edge

So we need:

and

Where:

If either fails, then this $(n,m)$ is not valid.

Algorithm Used in the Code

For each test case:

1. Read $p, q$
2. Compute:

3. Find divisors of $S$ by looping from $3$ to $\sqrt{S}$ (only odd divisors)

4. Store divisor candidates inside a linked list

5. For each divisor $a$ in the list:

   • Compute $b = S/a$
   • Compute:

• Compute $H$ and $V$
• Check if $q \le H$ and $q \le V$

6. If found, print $n$ and $m$
7. Otherwise print $-1$

Why Use a Linked List Here?

Normally, you could just check divisor pairs directly.

But in this solution we kept the same skeleton:

• store divisor candidates inside a linked list
• traverse the linked list to test possible $(a,b)$ pairs

So it matches the structure: InsertAtEnd(), diviseurs(), tempNode, etc.

Complexity Analysis

We search divisors up to:

And:

So:

This is very fast.

• Time complexity: $O(\sqrt{S})$ per test case
• Memory complexity: $O(k)$ where $k$ is the number of stored divisors

Final C Code

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <math.h>
4

5
typedef struct Node{
6
    int value;
7
    struct Node *next;
8
}Node;
9

10
typedef Node* NodePtr;
11

12
void PrintList(NodePtr head)
13
{
14
    while(head)
15
    {
16
        printf("value %d\n",head->value);
17
        head=head->next;
18
    }
19
}
20

21
int InsertAtEnd(NodePtr *ptrHead,int value)
22
{
23
    NodePtr head=*ptrHead;
24
    NodePtr tempNode=(NodePtr)malloc(sizeof(Node));
25

26
    if(!tempNode) return -1;
27

28
    tempNode->value=value;
29
    tempNode->next=NULL;
30

31
    if(head==NULL)
32
    {
33
        *ptrHead=tempNode;
34
        return 1;
35
    }
36

37
    while(head->next!=NULL) head=head->next;
38
    head->next=tempNode;
39
    return 1;
40
}
41

42
NodePtr diviseurs(NodePtr head,int number)
43
{
44
    for(int i=3;i<=sqrt(number);i+=2)
45
    {
46
        if(number%i==0)
47
        {
48
            InsertAtEnd(&head,i);
49

50
            int other=number/i;
51
            if(other!=i) InsertAtEnd(&head,other);
52
        }
53
    }
54
    return head;
55
}
56

57
int main()
58
{
59
    int t;
60
    scanf("%d",&t);
61

62
    while(t--)
63
    {
64
        int p,q;
65
        scanf("%d %d",&p,&q);
66

67
        int S=2*(p+2*q)+1;
68

69
        NodePtr head=NULL;
70
        head=diviseurs(head,S);
71

72
        NodePtr tempNode=head;
73

74
        int n=-1,m=-1;
75
        int found=0;
76

77
        while(tempNode!=NULL)
78
        {
79
            int a=tempNode->value;
80
            int b=S/a;
81

82
            if((a-1)%2==0 && (b-1)%2==0)
83
            {
84
                n=(a-1)/2;
85
                m=(b-1)/2;
86

87
                int H=m*(n+1);
88
                int V=n*(m+1);
89

90
                if(q<=H && q<=V)
91
                {
92
                    found=1;
93
                    break;
94
                }
95
            }
96

97
            tempNode=tempNode->next;
98
        }
99

100
        if(found) printf("%d %d\n",n,m);
101
        else printf("-1\n");
102
    }
103

104
    return 0;
105
}

Takeaways

The trick is transforming:

into the factorized form:

Then it becomes a divisor search problem.

After getting $(n,m)$, we must also verify that the $q$ L-shaped pieces fit:

This is the full reasoning behind the solution.