machinepainter's blog

By machinepainter, history, 4 years ago, In English

I really like the fact that the test cases are visible on Codeforces after the contest. However it happens sometimes that a single test case is containing multiple tests, and the test cases are not able to list all the tests so they are usually then followed by ...

So, it would be extremely useful if the Checker comment includes the test case along with wrong output on test case #x

Full text and comments »

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

By machinepainter, history, 5 years ago, In English

Based on the problem in GeeksForGeeks here. I came across a solution here.

The question is as follows

Given an array arr[] of N integers. Do the following operation n-1 times. 
For every Kth operation:

Right rotate the array clockwise by 1.

Delete the (n-k+1)th last element.

Now, find the element which is left at last.

If (n-k+1)th last element doesnt exist, delete the first.

Test Cases -

Input

2

4

1 2 3 4

6

1 2 3 4 5 6

Output

2

3

Explanation - Testcase 2: A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, 3, 4, 5} and delete the last element that is {5} so A = {6, 1, 2, 3, 4}. Again rotate the array for the second time and deletes the second last element that is {2} so A = {4, 6, 1, 3}, doing these steps when he reaches 4th time, 4th last element does not exists so he deletes 1st element ie {1} so A={3, 6}. So continuing this procedure the last element in A is {3}, so outputp will be 3.

Can someone please help me understand the solution. Primarily I need help in the following block:

if(n==1) cout<<arr[0]<<endl;
else if(n%2) {
    ll ind = n-3;
    ind = floor(ind/4);
    ind = 3+ind;
    cout<<arr[ind-1]<<endl;
} else {
    ll ind = n-2;
    ind = floor(ind/4);
    ind = 2+ind;
    cout<<arr[ind-1]<<endl;
}

Full text and comments »

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

By machinepainter, history, 5 years ago, In English

I was going through the following question

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

I tried writing a dp and a greedy solution for this problem, but none of them worked. Unfortunately the site from where I am practising this question also does not have a correct solution. Can someone please suggest a solution to this problem or is this also NP-hard like polygon partition ?

Complete Problem Statement

Full text and comments »

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