Mate in 3 - problem 27

White to move and mate in 3

Mate in 3 - problem 26

White to play and mate in 3

UVa 12532 - Interval Product | Solution

Problem Overview:

Name: UVa 12532 - Interval Product
Link: http://uva.onlinejudge.org/external/125/12532.html
Time Limit: 2s
Memory Limit:

---

My suggested solution:

Difficulty: Medium
Hint: This problem can also be solved by IT algorithm, but BIT is chosen because it's easy and fast to code. Obviously, there are an observation: the result of a product command of all integers between I and J will be zero if at least one of them is zero, it will be positive if the number of negative integers is divisible by 2, and it will be negative otherwise. There are 2 initial binary indexed trees, one stores the number of zeros (zero-tree) and other keeps the number of negative integers (nega-tree). With every integer read from input, the zero-tree should be adjusted by +1 at its position if it is a zero, and if it is a negative integer, the nega-tree should be updated. The changing query can be divided into 2 steps: removing an array element and inserting another element right there. The trees should be updated right after each step. Now, every product command from I to J can be easily calculated by counting the number of zeros and negative integers between I and J based on the observation above.
Complexity: There are K commands, each of which is a change or a product command. The update function and the range sum function can be done in O(logN). So the complexity is O(K * logN)
Algorithm: BIT
Related problem:

Một bài viết trên facebook của tôi

Vừa nãy khi mình đứng dưới vòi sen nước nóng, mình mãi mê nghĩ về một điều đến nỗi mà dùng nhầm chai sữa tắm Axe để gội đầu và vớ chai dầu gội Romano để tắm (làm đại sứ thương hiệu cho hãng này nên lâu lâu phải quảng cáo cho họ tí). Lý do này đủ thú vị để mình chia sẻ điều mình nghĩ lên facebook làm kỷ niệm sự kiện ngớ ngẩn đêm Giáng Sinh.

Nó đây.

Khi mọi chuyện xung quanh bạn đột ngột trở nên tồi tệ, bạn nghĩ mình bị dồn vào chân tường, lúc ấy bạn chỉ mong cuộc đời ban cho bạn một lối đi, dù chỉ là một con đường mòn, để bạn thoát ra khỏi tình thế bế tắc đó.

Rồi khi bạn đã đi được tới một con đường đá, nhìn qua bên kia sông, thấy người ta chạy xe trên đường nhựa sao êm quá, có thể bạn sẽ trách cuộc đời sao chỉ cho bạn đi trên một con đường, mà lại là con đường đầy sỏi đá không được êm ái như người ta, trách sao bạn đã chạy mòn bánh xe mà không có chiếc cầu nào để qua sông.

Mate in 3 - problem 25

White to play and mate in 3

Mate in 3 - problem 24

 

White to play and mate in 3

Đeo đuổi đến cùng ước mơ

Khi vào Google, gõ dòng chữ: CTU.Optimists, trong 0.23 giây, kết quả tìm kiếm cho hơn 208 nghìn kết quả liên quan đến đội tuyển đạt Giải nhất cuộc thi Lập trình sinh viên quốc tế ACM/ICPC của Trường Đại học Cần Thơ. Niềm vui nhân đôi, khi biết tin đội sẽ là đơn vị duy nhất đại diện Việt Nam dự thi vòng chung kết ACM/ICPC toàn cầu tại Nga vào cuối tháng 6-2013.

Phút 89…

Dù cuộc thi Lập trình sinh viên quốc tế ACM/ICPC vòng loại châu Á, tại điểm thi Hà Nội, đã kết thúc hơn một tháng nay nhưng dư âm vẫn còn "nóng hôi hổi" với Đội tuyển CTU.Optimists (gồm các thành viên: Lâm Phan Việt, sinh viên ngành Máy tính và Truyền thông K35; Lương Văn Đô, sinh viên ngành Khoa học máy tính K36; Trần Thanh Tú, sinh viên ngành Kỹ thuật phần mềm K34 và Thạc sĩ Nguyễn Cao Hồng Ngọc, Huấn luyện viên của đội). Đội trưởng Lâm Phan Việt xúc động nói: "Hôm xướng danh đội của chúng tôi đoạt giải Nhất vòng loại khu vực châu Á tại điểm thi Hà Nội, cả đội vui mừng đến nổi không nói nên lời…".

ACM/ICPC điểm thi Hà Nội năm nay tuân thủ tiêu chuẩn của cuộc thi ACM/ICPC quốc tế. Các thí sinh phải giải toán trên máy tính bằng tiếng Anh. Mỗi đội được phát 1 đề thi có 8-10 bài, cùng làm việc trên 1 PC trong 5 giờ. Các bài thi phải sử dụng ngôn ngữ lập trình C/C++, Java. Kết quả được chấm hoàn toàn tự động bằng công cụ chấm thi và công bố tại khu vực thi. Cuộc thi đòi hỏi thí sinh phải có khả năng lập trình, tư duy thuật toán rất tốt. Điều quan trọng, các thành viên trong đội phải thật "ăn ý". Đô kể: "Trong 4 giờ thi đầu, cả đội chỉ giải được 2/10 bài thi. Đội xếp đồng hạng 17, đứng thứ tự 25. Lúc ấy, chúng tôi rất lo lắng, bởi chỉ còn 1 giờ thi nữa và đội giỏi nhất hiện đã giải được 4 bài. Chúng tôi tự nhủ phải cố gắng. Khi đó, máy chấm thi báo kết quả đáp án bài giải thứ 3 của đội đúng. Cả đội lấy lại tinh thần, chúng tôi chia nhau mỗi người một việc, cố gắng sửa và cải tiến các bài đang làm dang dở. Rồi máy báo kết quả đúng 4 bài. Bài thứ 5, chúng tôi hoàn thành khi chỉ còn khoảng 20 phút cuối". Tú tiếp lời: "Giải được bài cuối cùng là nhờ vào kinh nghiệm của Việt. Chính kinh nghiệm và sự quyết đoán của bạn đã giúp đội toàn thắng trong cuộc thi". Thạc sĩ Nguyễn Cao Hồng Ngọc phấn khởi nói: "Ngồi ngoài phòng thi, tôi rất sốt ruột. Sau 4 giờ thi đầu, lúc bảng điểm đóng băng (không còn cập nhật kết quả để giữ bí mật), đội chỉ giải được 2 bài, chưa đúng với thực lực của đội. Đến khi đội ra ngoài phòng thi, nhìn Việt đưa bàn tay 5 ngón (ngụ ý làm được 5 bài tập), chúng tôi chỉ biết ôm nhau khóc vì quá vui mừng!".

Mate in 3 - problem 23

White to move and mate in 3

Mate in 3 - problem 22

White to play and mate in 3

Mate in 3 - problem 21

This problem is about Queen + Knight + Bishop combination. Have fun!

White to play and mate in 3.