MAXIMUM DRAWS

PROBLEM: Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

SOLUTION:
- Đầu tiên ta cần quan tâm đến nguyên tắc Pigeonhole. Có thể phát biểu nguyên tắc này qua ví dụ:

Nếu chúng ta đặt N con chim bồ câu vào M thùng container, với N>M ( Khi N=M+1 thì có một một container chứa 2 con chim bồ câu ) thì chắc chắn sẽ có ít nhất một thùng phải chứa hơn một con chim bồ câu.

Quay trở lại vấn đề trên, theo đề bài ta giả sử có N đôi vớ ( mỗi đôi 2 chiếc vớ ) trong ngăn tủ của Jim ( các đôi vớ có màu khác nhau). Áp dụng nguyên tắc trên ta thấy rằng trường hợp xấu nhất tức số lượng chiếc vớ mà Jim phải rút lớn nhất đến khi tìm được 2 chiếc vớ cùng màu là N+1. Mỗi chiếc vớ tương ứng với 1 con chim bồ câu trên và ta có N màu khác nhau tức tương ứng có N container khác nhau.

FULL CODE:

Với t là số trường hợp ta test, n là số lượng đôi vớ.

Edited by Bùi Ngọc Tài

Đọc tiếp »

FIND THE POINTS

PROBLEM: Consider two points,p=(Px,Py)  and q=(Qx,Qy) . We consider the inversion or point reflection,r=(Qx,Qy) , of point p across point q to be a  rotation of point p around q .

SOLUTION:
Trong mặt phẳng tọa độ Oxy. Theo đề bài, Q sẽ là trung điểm của P và P'.
Tính chất: (xP+xP')/2=xQ và  (yP+yP')/2=yQ.

Áp dụng tính chất trên ta dễ dàng tìm được tọa độ điểm P' khi đã biết vị trí 2 điểm còn lại trong không gian Oxy.

FULL CODE:



Time complexity: O(1).

Edited bye me.

Đọc tiếp »

Bitwise Hacks for Competitive Programming

1.Làm sao để set một bit trong số " num":
- Nếu chúng ta muốn set một bit tại một vị trí n trong số num, chúng ta có thể dùng toán tử OR ( | )
- Đầu tiên , chúng ta dịch trái số 1 với số bit dịch là n: 1<<n.
- Sau đó sử dụng toán tử OR tại vị trí n. Sở dĩ toán tử OR được dùng vì nó set một bit mà không quan tâm đến giá trị của từng bit trong dãy nhị phân của số " num ".

num=0100, set bit 1 tại vị trí 1 ( pos=1 ) . Tưởng tượng num giống như mảng, tức set bit 1 tại vị trí num[1], sau khi set sau num=0110 tức bằng 6.

2) Làm sao để unset/clear một bit tại vị trí n trong số " num "

- Gỉa sử rằng chúng ta muốn unset một bit tại vị trí n trong số " num" do đó chúng ta phải nhờ sự giúp  của toán tử AND ( &).

- Đầu tiên chúng ta dịch trái số 1 với n bit dịch hơn nữa cũng dùng toán tử NOT (~) để unset kết quả của shifted "1 ".

- Sau khi clear sau xong kết quả của shifted " 1", ta thực hiện nó với số " num " bằng toán tử AND (&).

num=0111, kết quả của 1<<pos là 1110, sau khi thực hiện toán tử NOT ta được 0001, thực hiện AND với num ta được 01110.Vậy là với pos=1, ta đã thực hiện xong unset.

3) Toggling một bit tại vị trí n:

- Toggling có nghĩa là nếu bit tại trí n đang là có giá trị là 0 thì sẽ turn lên 1 và ngược lại. Sử dụng toán tử XOR. Do đặc điểm của XOR giữa 2 bit luôn cho kết quả 0 nếu 2 bit có cùng giá trị.

num=0100, kết hợp với (1<<pos=0010) bằng toán tử XOR ( ^ ), ta được 0110.ở đây ta xem num như mảng và Toggling tại pos=1 thì xem như tại num[1].

4) kiểm tra xem tại vị trí n đang là set hay unset:

num=0101 và 1<<pos=0001. Kết quả khi thực hiện toán tử AND=0001, dùng kiểu bool nên bit=1. Xem num như mảng, tức kết quả có được cho thấy tại  num[0], giá trị bit đang set.

5) Stripping off the lowest set bit ( Loại bỏ bit thấp nhấp được set lên 1 )

Ở ví dụ trên num=7=0111, ta mong muốn loại bỏ bit được set lên 1 cuối cùng, ta lấy 7-1=6=0110, sau đó AND num, ta được 0110.
xét ví dụ với num=14=1110, một cách diễn đạt khác, phép tính num-1=14-1=1101 có thể được diễn giải theo thao tác trên bit như sau: xét từ bit trái của numsang phải, nếu gặp bit được set lên 1 cuối cùng thì đảo lại thành bit 0 và kể từ đó, đảo tất các bit sau bit cuối cùng được set lên 1, tức ta sẽ được kết quả 1101=13, thực hiện AND với num ta đã hoàn thành việc loại bỏ bit cuối cùng được set lên 1.

6)Getting lowest set bit of a number( lấy bit được set thấp nhất)

Ta thấy num=10=1010, ta mong muốn get bit được set cuối cùng, tức mong muốn đạt được kết quả là 0010. Đầu tiên đảo số num thành số âm bằng 2 cách:
+ Dùng 1's complement( biến num thành số bù 1)+ 2's complement(+1 để thành số bù 2) tức phép toán ~num+1
+ Dùng - num.
Ta thực hiện 1  trong 2 cách trên, sau đó lấy kết quả trên AND với num ta được kết quả mong muốn ban đầu là 0010.


Tham khảo: geeksforgeeks
Edited by me " NÓI THẬT, LÀM THẬT ! "

Đọc tiếp »

INTERESTING FACTS ABOUT BITWISE OPERATOR IN C

Trong ngôn ngữ C, có 6 toán tử xử lý trên bit, Các phép toán xử lý trên bit:

& ( AND ): lấy 2 số như toán hạng thực hiện phép AND trên mỗi bit tương ứng của 2 số.Kết quả từng phép xử lý trên cặp bit bằng 1 nếu cả 2 đều là 1.

| ( OR ):Tương tự trả về 1 nếu một trong 2 bit bằng 1.

^ ( XOR ): Trả về 1 nếu 2 bit khác nhau.

~ ( NOT ): Đảo ngược tất cả các bit.

<< (Dịch trái): Dịch trái số bit n của toán hạng đầu tiên. Toán hạng thứ 2 quy định số n bit dịch.

>>(Dịch phải): Dịch phải số bit n của toán hạng đầu tiên. Toán hạng thứ 2 quy định số n bit dịch.

! NOTE:

• Toán tử dịch trái và dịch phải không dùng cho số âm (negative numbers):

-Kết quả không được xác định nếu có bất cứ toán hạng nào negative numbers.
Vd: -1<<1 hay 1<<-1.

-Tương tự số lượng bit dịch nếu vượt quá size of integer thì không thể xác định được kết quả.
Vd: 1<<33.

• Toán tử XOR thì được sử dụng phổ biến trong các cuộc phỏng vấn kỹ thuật.

-Nó thì được dùng  để giải quyết nhiều vấn đề.
Xét ví dụ sau: cho một danh sách các số mà ở đó tất các số đều có tần xuất xuất hiện chẵn ngoại trừ một số. Hãy tìm giá trị của số có số lần xuất hiện lẻ.

Mình tâm đắc nhất đối với chức năng đặc biệt này của XOR. Great !

• Những toán tử xử lý trên bit không nên được dùng trong cùng vị trí với toán tử logic.

- Kết quả của một logical operator  ( &&, || và !) là 1 hoặc 0. Nhưng kết quả trả về của toán tử bit là một giá trị kiểu integer. Toán tử logic chỉ trả về là 0 (false) hoặc 1 (true). Các toán hạng thực hiện toán tử logic,  nếu là số 0 thì nó xem là false và tất cả các số khác 0 xem là true. Xem ví dụ bên dưới:

• Toán tử dịch trái và dịch phải tương đương với với phép nhân và phép chia.

-Ở chú ý đầu tiên, ta đã nói 2 toán tử trên chỉ làm việc với số dương (positive numbers)

-Dịch trái tương ứng với phép nhân ( 19*2=38 ) và dịch phải tương ứng với phép chia (19/2=9).

• Toán tử & có thể được dùng để kiểm tra nhanh là số chẵn hay lẻ.

Gía trị trả về của phép toán x & 1 là khác 0 nếu như x là số lẻ, nếu chẵn thì là 0.

• Toán tử ~ nên được sử dụng một cách cẩn thận

Kết quả khi thực hiện toán tử t ~ trên số nhỏ có thể cho ra kết quả một số lớn nếu kết quả được lưu với kiểu dữ liệu không dấu.Và có thể thành số âm nếu được lưu với kiểu dữ liệu có dấu.

ÁP DỤNG: bài toán LARGEST PRIME FACTOR ta sẽ thay việc check tính chia hết và thực hiện phép chia cho 2 bằng cách áp dụng toán tử dịch bit sang phải. Gíup chương trình nhanh hơn, do số lần lập của bài này vẫn còn ít nên mình không thể đo được time chạy của thuật toán để thấy được khác biệt.

Tham khảo: geeksforgeeks.

Edited by me.

Đọc tiếp »

LARGEST PRIME FACTOR

PROBLEM: The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

SOLUTION: Bài này thuật toán cũng khá đơn giản ( Có lẽ sẽ có thuật toán tối ưu hơn, mong bạn đọc góp ý), cái khó duy nhất có lẽ làm sao để lưu trữ một số quá khủng như vậy (600851475143). Đầu tiên ta xem qua các kiểu dữ liệu quen thuộc:

Rõ ràng các KDL trên không thể lưu trữ con số trên, ta dùng thư viện inttypes.h hoặc cstdint.

FULL CODE:

! NOte: Cách xuất con số kiểu int64_t hay  uint64_t.

printf("%d" PRId64"\n",t);

printf("%d" PRIu64"\n",t);


với t là tên biến.

Mong bạn đọc góp ý ! Xin cảm ơn.

EDITED BY ME " NÓI THẬT,  LÀM THẬT !"

Đọc tiếp »

EVEN FIBONACCI NUMBERS

PROBLEM: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

SOLUTION: Giải pháp của mình dùng khá nhiều biến. 3 biến pre_1, pre_2 và term để lần lượt lưu 3 giá trị đó là số fibonacci và 2 số phía trước nó. Mỗi vòng lặp là 3 biến này được cập nhật giá trị mới.

FULL CODE:

Mong nhận được sự góp ý từ bạn đọc !

Edited by me.

Đọc tiếp »

MULTILES OF 3 AND 5

PROBLEM: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

SOLUTION:

+Bài toán thì rất đơn giản thôi nhưng chỉ cần chú ý nếu một số đồng thời là bội của 2 số 3 và 5 thì biến result chỉ cộng một lần.

vdL: 15 là bội của 3 và 5, trong quá trình xét duyệt, biến result sẽ cộng 2 lần số  15, ta sẽ trừ bớt đi 15 trong điều kiện if cuối.

! Đoạn code từ dòng 8-17 có thể thay bằng if (!((i%3)||(i%5)) ( góp ý bởi anh Nguyễn Hoàng Phúc ).

By me.

Đọc tiếp »