Enigma27's blog

By Enigma27, 13 months ago, In English

1208A — XORinacci

The sequence is $$$a$$$, $$$b$$$, $$$a\oplus b$$$, $$$a$$$, $$$b$$$, $$$a\oplus b$$$ $$$\cdots$$$

Since, the sequence has a period of $$$3$$$, $$$f[i] = f[i \mod 3]$$$.


1208B — Uniqueness

After removing a sub-segment, a prefix and a suffix remain, possibly of length $$$0$$$. Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set to keep track of the elements.

Time complexity: $$$O(n^2 \cdot log(n))$$$


1208C — Magic Grid

Divide the grid into four quadrants. Assign distinct integers to the first quadrant from $$$0$$$ to $$$(\frac{N^2}{4} - 1)$$$. Copy this quadrant to the other three. This way XOR of each row and column becomes $$$0$$$.

Now, to make numbers distinct among the quadrants, multiply the numbers by $$$4$$$. Add $$$1$$$, $$$2$$$, and $$$3$$$ to the numbers in $$$1^{st}$$$, $$$2^{nd}$$$ and $$$3^{rd}$$$ quadrants respectively. The XOR of each row and column would still remain $$$0$$$ as $$$N/2$$$ is also even but the elements will become distinct while being in the range $$$[0, N^2-1].$$$

Another approach in this problem is to use a $$$ 4 \times 4$$$ grid given in the sample itself and replicate it in $$$N \times N$$$ grid by adding $$$16, 32, 48 \cdots $$$ to make the elements distinct.

Of course, there are multiple ways to solve the problem. These are just a few of them.


1208D — Restore Permutation

Approach 1

Let us fill the array with numbers from $$$1$$$ to $$$N$$$ in increasing order.

$$$1$$$ will lie at the last index $$$i$$$ such that $$$s_{i} = 0$$$. Find and remove this index $$$i$$$ from the array and for all indices greater than $$$i$$$, reduce their $$$s_{i}$$$ values by $$$1$$$. Repeat this process for numbers $$$2, 3, ...N$$$. In the $$$i^{th}$$$ turn, reduce the elements by $$$i$$$.

To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

Time complexity: $$$O(N \cdot log(N))$$$

Approach 2

For every i from $$$N$$$ to 1, let's say the value of the $$$s_{i}$$$ is x. So it means there are $$$k$$$ smallest unused numbers whose sum is $$$x$$$. We simply put the $$$k+1$$$st number in the output permutation at this $$$i$$$, and continue to move left. This can be implemented using BIT and binary lifting.

Thanks to Vladimirr.Petrunko for expressing the solution in the above words.


1208E — Let them slide

For every array $$$i$$$ from $$$1$$$ to $$$N$$$, let us maintain 2 pointers $$$L[i]$$$ and $$$R[i]$$$, representing the range of elements in $$$i_{th}$$$ array, that can be accessed by the current column index $$$j$$$.

Initially all $$$L[i]$$$ and $$$R[i]$$$ would be set equal to 0.

As we move from $$$j_{th}$$$ index to $$$(j+1)_{th}$$$ index, some $$$L[i]$$$ and $$$R[i]$$$ would change. Specifically, all those arrays which have $$$size \ge min(j,W-j-1)$$$ would have their $$$L[i]$$$ and $$$R[i]$$$ change.

Since overall movement of $$$L[i]$$$ and $$$R[i]$$$ would be equal to $$$2 \cdot$$$ size_of_array($$$i$$$). Overall change would be of order of $$$O(\sum a[i])$$$. For every array we need range max query in $$$(L[i], R[i])$$$.

We can use multisets/ segment trees/ deques to update the answers corresponding to an array if its $$$L[i], R[i]$$$ changes. This way we can get complexity $$$O(N)$$$ or $$$O(N \cdot log(N))$$$ depending upon implementation.


1208F — Bits And Pieces

The idea is to first fix some $$$a[i]$$$ and try to get the bits which are off in $$$a[i]$$$ from any $$$2$$$ elements to the right of $$$i$$$. Since, we need to maximize the value, we will try to get higher bits first. What we need now is, for every number $$$x$$$ from $$$0$$$ to $$$2^{21}-1$$$, the $$$2$$$ right most positions such that the bits present in $$$x$$$ are also present in the elements on those positions. This can be done by iterating over submasks(slow) or SOS-DP(fast).

Once we process the positions for every $$$x$$$, let us fix some $$$a[i]$$$ and iterate over the bits which are off in $$$a[i]$$$ from the highest to the lowest. Lets say the current maximum we have got is $$$w$$$ and we are going to consider the $$$y^{th}$$$ bit. We can get this bit if the $$$2$$$ positions for $$$w|2^{y}$$$ are to the right of $$$i$$$ else we can not.

The final answer would be the maximum of $$$a[i]|w$$$ over all $$$i$$$ from $$$1$$$ to $$$N$$$.

Time complexity $$$O((M+N)\cdot logM)$$$ where $$$M$$$ is the max element in the array.


1208G — Polygons

If we choose a polygon with side length $$$l$$$, it is profitable to choose polygons with side lengths as divisors of $$$l$$$ as well, because this will not increase the answer.

So our final set would be such that for every polygon with side length $$$l$$$, we would have polygons with side length as divisors of $$$l$$$ as well.

All polygons should have at least one common point in the final arrangement, say $$$P$$$ or else we can rotate them and get such $$$P$$$. For formal proof, please refer this comment by imp.

Let us represent points on the circle as the distance from point $$$P$$$. Like for $$$k$$$ sided polygon, $$$0$$$,$$$\frac{1}{k} ,\frac{2}{k} ,…\frac{k-1}{k}$$$.

Now the number of unique fractions over all the polygons would be our answer, which is equal to sum of $$$ \phi (l)$$$ over all side lengths $$$l$$$ of the polygons because for $$$l$$$ sided polygon there will be $$$\phi(l)$$$ extra points required by it as compared to its divisors.

One observation to get to the final solution is $$$\phi(l) \ge \phi(divisor(l))$$$. So, we can sort the side lengths by their $$$\phi$$$ values and take the smallest $$$k$$$ of them. This will minimize the number of points as well as satisfy the property of our set.

NOTE: We can not consider polygon of side length $$$2$$$. This can be handled easily.

Tutorial is loading...

Read more »

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

By Enigma27, history, 19 months ago, In English

I would like to invite you all to the International Coding Marathon 2019, under the banner of Technex'19, IIT (BHU) Varanasi.

Technex is the annual techno-management fest of Indian Institute of Technology (BHU), Varanasi organized from March 8 — 10, 2019.

International Coding Marathon is the flagship event of Byte The Bits, the set of programming events organized under Technex. ICM is brought to you by Mentor Graphics. It will take place on Friday, 8th March 2019, 21:00 IST. The contest will be held on Codechef.

The problemset has been prepared by hitman623, dhirajfx3, _shanky, drastogi21 and me (Enigma27). We would like to express our heartiest thanks to navpun31 and prakhar28 for their constant help in preparing the contest.

Prizes -

Overall 1st — INR 15,000

Overall 2nd — INR 10,000

India 1st — INR 9,000

India 2nd — INR 5,000

IIT(BHU) 1st — INR 6,000

IIT(BHU) 2nd — INR 4,000

IIT(BHU) Freshmen 1st — INR 1,000

Some of our previous contests :

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined)

Participants will have 2 hours 30 minutes to solve 7 problems. The scoring will be ICPC style.

Contest Link

Good luck everyone! Hope to see you on the leaderboard.

UPD — Contest begins in 1.5 hours

UPD1 — Contest begins in 15 minutes

UPD2 — Contest has ended. Congratulations to the winners. They will be contacted soon.

We deeply regret the inconvenience caused due to the problem ICM03. We will try to avoid such things in the future.

Editorials will be uploaded soon. Feel free to discuss the problems in the comment section.

UPD3 — The editorial is up.

Array Got Some Moves
Bob and his strict Mom
Snorlax hates working out
Yet Another Counting Problem
Good Sequence

Read more »

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

By Enigma27, history, 2 years ago, In English

Hi, Codeforces Community!

Codefest'18 — a diverse roster of high-quality programming competitions by Department of Computer Science and Engineering, IIT(BHU), Varanasi is excited to present Perplexed — the constrained programming event.

Perplexed is one of the most innovative events of CodeFest, whose target is not only gauge a contestant's coding abilities but also how one tackles different situations and constraints. The problemset will include all mind-boggling coding problems, ranging from code obfuscation to stricter memory limits, character limits, time limits, etc

The contest will take place at HackerRank. This contest will be an individual event with a duration of 3 hours, from Aug/31/2018 21:00 IST. With the creativity that the problems will naturally encourage and INR 50,000 at stake, there is absolutely no reason for a programmer to not give this one a shot!

The contest has been prepared by GT_18, code_kika, Rmatrix and me(Enigma27).

Prizes -

1st Prize-Rs.20000

2nd Prize-Rs.12000

3rd Prize-Rs.8000

1st in India-Rs.6000

1st in IIT(BHU)-Rs.3000

1st in 1/2 year in IIT(BHU)-Rs.1000

UPD : Contest has ended

Overall Winners

  1. tourist
  2. Golovanov399
  3. marcin_smu

India First : hitman623

Read more »

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