hunter_of_alts's blog

By hunter_of_alts, 2 weeks ago, In English

Google-forces round 810 :

Google-forces round 808 :

Google-forces round 805 :

This shows nowadays we need to learn Chinese language and improve our searching skills, But this isn't fair, MikeMirzayanov What's your opinion about this?

P.S : Every single thing I say in the comments is just my opinion and never wanna insult any country/organization/person and etc.

Read more »

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

By hunter_of_alts, 3 weeks ago, In English

You are given a number $$$n$$$, And we have two functions, We declare $$$P(S)$$$ for a set of numbers, product of all the numbers in the set, Also we declare $$$F(S)$$$ for a set of numbers, sum of all the numbers in the set, You have the set {$$$1, 2, 3, ... , n$$$} you have to calculate

$$$\sum_{i=1}^{2^{n}-1}(F(S_i)/P(S_i))$$$

for all non empty subsequences of {$$$1, 2, 3, ... , n$$$}, in the other words you have to provide a solution that calculates sum of $$$F(S)/P(S)$$$ for all non empty subsequences.

For example the answer for $$$n = 2$$$ is this :

  • for {$$$1$$$} sum is $$$1$$$ and product of numbers in it is $$$1$$$ so $$$F($$${$$$1$$$}$$$)/P($$${$$$1$$$}$$$)$$$ is $$$1/1 = 1$$$

  • for {$$$2$$$} sum is $$$2$$$ and product of numbers in it is $$$2$$$ so $$$F($$${$$$2$$$}$$$)/P($$${$$$2$$$}$$$)$$$ is $$$2/2 = 1$$$

  • and for the last non empty subsequence {$$$1, 2$$$} sum is $$$3$$$ and product of the numbers in it is $$$2$$$ so $$$F($$${$$$1, 2$$$}$$$)/P($$${$$$1, 2$$$}$$$)$$$ is $$$3/2 = 1.5$$$

So the answer for $$$n = 2$$$ is $$$1 + 1 + 1.5 = 3.5$$$

Constraints :

$$$1 \le n \le 10^6$$$

Solution

Hope you enjoy the problem, I'll share my approach's proof after $$$24$$$ hours!

Read more »

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

By hunter_of_alts, 4 weeks ago, In English

Hello, The main reason of newbies' fear from XOR is bad reference in the problem statements to explain XOR and other bitwise operations (Authors usually put Wikipedia reference) and newbies mostly can't understand what's XOR, today I wanna explain something about bitwise operations for this group of coders with simple language :

1- Bitwise OR :

In this operation the system compares bits in same index in binary representation and if at least one of the bits was $$$1$$$ it returns $$$1$$$ otherwise $$$0$$$, Also it is written as | in C++.

For example :

  • Bitwise OR of $$$6$$$ and $$$3$$$ is :

  • $$$6 = 110$$$ in binary representation and $$$3 = 011$$$.

  • $$$6$$$ | $$$3 = 7 = (110$$$ | $$$011 = 111)$$$

  • Note : If in any index a number doesn't have enough bits system supposes that there's a $$$0$$$ bit in that index in binary representation of that number.

2- Bitwise AND :

As it's guessable from it's name if all bits in same index were $$$1$$$ system return $$$1$$$ otherwise $$$0$$$, Also it's written as & in C++.

For example :

  • Bitwise AND of $$$10$$$ and $$$3$$$ is :

  • $$$10 = 1001$$$ and $$$3 = 0011$$$

  • $$$10$$$ & $$$3 = 1 = 1001$$$ & $$$0011 = 0001$$$.

3- Bitwise XOR :

In this operation system compares bits in same index and if odd number of them were $$$1$$$ it returns $$$1$$$ otherwise $$$0$$$, Also it is written as xor or ^ in C++.

For example :

  • Bitwise XOR of $$$3$$$ and $$$5$$$ and $$$8$$$ is :

  • $$$8 = 1000, 5 = 0101, 3 = 0011$$$.

  • $$$8$$$ ^ $$$5$$$ ^ $$$3 = 14 = 1000$$$ ^ $$$0101$$$ ^ $$$0011 = 1110$$$.

I hope it would be helpful for you 💗 💗 (BTW if you noticed any typo let me know).

PS : As people say in the comments I've added some educational problems about this topic, If you had problems about this topic please write down in the comments Thanks.

Read more »

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