Saturday, February 10, 2018

Akash and GCD 1

Problem link: Akash_gcd_1

We need to perform query based on given function F, that

F(x) = GCD(1, x) + GCD(2, x) + ..... + GCD(x, x)
Where GCD is the Greatest Common Divisor
Now in the problem, given an array A of size N, there are 2 types of queries:
  1. C X Y: Compute the value of F(A[X]) + F(A[X+1]) + F(A[X+2]) + .... + F(A[Y]) (mod 10^9+7)
  2. U X Y: Update the element of A[X] = Y
Solution:

At first we need to pre compute the value of F(x). Also we need help of Euler's Totient Function for this purpose. You can learn Euler Totient from here: Euler's Totient
Also we need to compute summation of GCD(i,n) for i = 1 to n. If you don't know how to do that, see here: GCD summation

This problem can be solved by segment tree. But as we only need prefix sum and simple update query, we can also solve it using binary indexed tree. As binary indexed tree is easy to code and simple, it's preferable.

Code:

Notice at line 86, the computed value might go negative less than 10^9+7. So we used a while loop to check while the value is below zero, we will add the mod value to make it positive. If we checked the negative value mod in the qeury function, this wouldn't be necessary.

Thursday, February 8, 2018

OpenGL: National Parliament of Bangladesh 3D Model

In my final year Graphics Lab, I implemented a 3D model of National Parliament of Bangladesh using OpenGL.

If you don't have glut installed in your codeblocks, then see this link :OpenGL installation


Features:

  • Day-night mode ( press 'n' OR 'N' )
  • Intensity changing ( press 'i' )
  • Fog mode ( press mouse right and left key )
  • Sun-moon show ( press 's' OR 'S' OR 'm' OR 'M' )
  • Light mode ( press 'l' )
  • Zoom mode ( press 'z' to zoom, 'x' to unzoom )
  • Text show ( press 't' to show text: "National Parliament of Bangladesh" )
  • Rotation mode ( press 'e' OR 'E' , 'r' OR 'R' to rotate camera )
  • Up-down mode ( press 'd' OR 'D' to down the camera, 'u' OR 'U' to uplift it )
  • Arrow keys to roam freely
Special Features:

  • Water flowing done by addinng 10 different images of a sample water flow. I used timer funtion to update the images (texture) and show them in output. Then it seems like the water is really moving
  • Same thing goes for flag moving
  • Also I used same technique to move trees [ though it doesn't look so good :( ]
Snapshots:





It's just a sample 3D model I implemented. Though it's really tough using OpenGL to draw as realistic as you want, but it is still fun to code :)
Here is the github link to the project. You can take a peek if you like.

link: https://github.com/sifatshishir/National-Parliament-3D-using-OpenGL

If you have problems running the project, you can follow these steps:
  • 1) create a project on codeblocks. 
  • 2) add all the header files and corresponding .cpp files, and non coding files such as .bmp, .bin, .txt and so on.
  • 3) Copy the texture code from main and bring to your project main.
  • 4) Run.
  • 5) If it works, good. else, go to 6
  • 6) left click on the project folder name which will on the left side under the project tab. click add files and select all of the files in 2.
  • 7) select in both debug and release and save.
  • 8) If it runs, good, else, go to 9.
  • 9) go to the project, then properties. from there, go to build target.
  • 10) change the execution working dir to your folder/bin/debug
  • 11) run
  • 12) if it works, fantastic, or else to go 13
  • 13) copy the .bmp .txt. bin files (non coding files) and place in your folder/bin/debug. delete all the .o from your folder/obj/debug and copy the .bmp .txt. bin files (non coding files).
  • 14) run



Tuesday, February 6, 2018

Toph: Range Product

Problem link: Range Product

Solution:

Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).

Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.

Toph: XOR Master

Problem link: XOR Master

Solution:

In this problem we are given N integers. We have to count the number of pairs (i,j) (1<=i<=j<=N) for which A[i] XOR A[j] will contain at least 1 in it's bit pattern.

Say for the case here:
4
1 2 2 2

Here are 3 such pair that A[i] XOR A[j] has at least one 1 in it's bit pattern. They are:

1 XOR 2 = 01(Binary of 1) XOR 10(Binary of 2) = 11 (has two '1's) ; for three 2's, and a single 1, we get 3 such pair of (1,2)

But as we can see, 2 XOR 2 = 10 XOR 10 = 00, here no '1' is present. So this will not be counted.

So, how can we solve this? Firstly, see that one integer can get at least one '1' in it's bit pattern if it is XOR-ed with any integers except itself. So, a simple binary search with upper_bound technique can be really helpful to find solution in O(log N). For frequent values, we can store them in a map data structure that is built in C++ function.


Thursday, February 1, 2018

Toph: Horrible Queries

Problem link: Horrible Queries

Solution:

In this problem, we will be given some integers from 1 to 50. And also integer L,R,K. We need to find how many unique values have at least K occurence in the subarray between L & R, where L<= R.
As numbers can only be between 1 to 50, we can implement this simply without the use of segment tree. What we need to do is that, we will create 50 array of size N (each for 1 to 50 integers) to compute the occurence of every integers in a cumulative way. Then for each query, we will simply check for every integers if cumulative sum (occurence of that integer) of that integer in given range is at least K or not. Then we will simply increase the counter to get our answer. Try to implement it any way you like keeping in mind about the cumulative frequency of occurance. Then you can check my code below.