CerealCodes II Novice |
---|
Finished |
A binary string is a string that only contains 0 and 1. Mythreya wants you to make a binary string for him.
Mythreya defines the palindromicity of a binary string $$$s$$$ of length $$$n$$$ as the number of differences between a binary string $$$s$$$ and its reverse. More specifically, the palindromicity is the number of indices $$$1 \leq i \leq n$$$ such that $$$s_{i} \neq s_{n-i+1}$$$.
Determine if you can find a binary string of length $$$n$$$ with palindromicity of $$$k$$$, and if so output one such string for Mythreya.
The first line will contain $$$t$$$ ($$$1 \leq t \leq 10^4$$$), the number of testcases.
The next $$$t$$$ lines will each contain two integers $$$n, k$$$ ($$$1 \leq k \leq n \leq 2 \cdot10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2\cdot10^5$$$.
For each testcase, output NO if there does not exist a string containing only $$$0$$$ and $$$1$$$ with a palindromicity of $$$k$$$. Otherwise, output YES and a string of length $$$n$$$ satisfying $$$k$$$ on two separate lines.
34 27 38 6
YES 0111 NO YES 10101000
In the first testcase 0111 has a palindromicity of $$$2$$$, since it has exactly $$$2$$$ differences with 1110 at positions $$$1$$$ and $$$4$$$.
It can be shown there is no way to construct a valid string for the second testcase.
Problem Credits: Mythreya Dharani
Name |
---|