# codechef

Chodechef long challenge problems

## CodeChef: May Long Challenge | An Interesting Sequence | ISS | Solution

View on Codechef Zanka finds fun in everyday simple things. One fine day he got interested in a very trivial sequence. Given a natural number kk, he considers the sequence Ai=k+i2Ai=k+i2 so that the terms arek+1,k+4,k+9,k+16,…k+1,k+4,k+9,k+16,… Now to make things more interesting, he considers the gcdgcd of consecutive terms in the sequence, then takes the sum of the first 2k2k values. More …

## CodeChef: May Long Challenge | King Killing | KKLING | Solution

View on Codechef In a faraway kingdom there are NN cities numbered 11 to NN connected to each other in the form of a tree. The city numbered 11 is the kingdom where the king resides. A city is called a leaf if it is not the kingdom and it has exactly one adjacent city. Each leaf city has an assassin. The enemies …

## CodeChef: May Long Challenge | Valid Paths | VPATH | Solution

View on Codechef You are given a tree with NN nodes numbered from 11 to NN. A set SS of nodes is called valid if there exist two vertices uu and vv (possibly, u=vu=v) such that every node in SS lies on the simple path from uu to vv. Count the number of valid sets modulo 109+7109+7. Two sets are different if one node is included in one set and not in the …

## CodeChef: May Long Challenge | Tree House | THOUSES | Solution

View on Codechef There is a large tree house in an unknown world. It is ruled by the great emperor KZS. It consists of NN nodes numbered from 11 to NN in which the people of that world reside. The nodes are organized in a tree structure rooted at node 11. You need to assign values to the nodes according to the …

## CodeChef: May Long Challenge | Modular Equation | MODEQ | Solution

View on Codechef Given integers NN and MM, find the number of ordered pairs (a,b)(a,b) such that 1≤a<b≤N1≤a<b≤N and ((M mod a) mod b)=((M mod b) mod a)((M mod a) mod b)=((M mod b) mod a). Input The first line contains an integer TT, the number of test cases. Then the test cases follow. The only line of each test case contains two integers NN, MM. Output For each testcase, output in a single line the answer to the problem. Constraints 1≤T≤10001≤T≤1000 …

## CodeChef: May Long Challenge | Tic Tac Toe | TCTCTOE | Solution

View on Codechef Tic-tac-toe is a game played between two players on a 3×33×3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol XX and the other player uses the symbol OO. The game continues until there …

## CodeChef: May Long Challenge | Xor Equality | XOREQUAL | Solution

View on Codechef For a given NN, find the number of ways to choose an integer xx from the range [0,2N−1][0,2N−1] such that x⊕(x+1)=(x+2)⊕(x+3)x⊕(x+1)=(x+2)⊕(x+3), where ⊕⊕ denotes the bitwise XOR operator. Since the number of valid xx can be large, output it modulo 109+7109+7. Input The first line contains an integer TT, the number of test cases. Then the test cases follow. The only line of each …

## CodeChef: May Long Challenge | Golf | LKDNGOLF | Solution

View on Codechef It’s a lockdown. You’re bored in your house and are playing golf in the hallway. The hallway has N+2N+2 tiles numbered from 00 to N+1N+1 from left to right. There is a hole on tile number xx. You hit the ball standing on tile 00. When you hit the ball, it bounces at lengths of kk, i.e. the tiles covered by …

## CodeChef: April Long Challenge | Worthy Matrix | KAVGMAT | Solution

View on Codechef Chef found a matrix AA with NN rows (numbered 11 through NN) and MM columns (numbered 11 through MM), where for each row rr and column cc, the cell in row rr and column cc (denoted by (r,c)(r,c)) contains an integer Ar,cAr,c. This matrix has two interesting properties: The integers in each row form a non-decreasing sequence, i.e. for each valid ii, Ai,1≤Ai,2≤…≤Ai,MAi,1≤Ai,2≤…≤Ai,M. The integers in each column also form a non-decreasing sequence, i.e. for …

## CodeChef: April Long Challenge | Chef and Dice | SDICE | Solution

View on Codechef Chef has NN 6-sided standard dice. Each die has dimensions 1×1×11×1×1. Since Chef is bored during the quarantine, he decides to stack dice for fun. First, Chef forms four vertical stacks of dice (not necessarily with the same height; empty stacks are allowed) on his table, which together make up a pile of dice with …