Năm 2020

 Đáng lẽ bài này phải post lên Facebook, nhưng mình viết trên này cho dễ định dạng.

Codechef December Challenge 2020 - Division B

 Trước hoặc trong những giờ deadline căng thẳng, mình thường mở coding contest lên và dành nhiều chất xám + thời gian cho nó, trong khi đáng lẽ ra nên dành cho những deadline hay bài tập kia.

Contest này làm được 4 bài, đáng lẽ ra thời gian viết cái editorial này mình nên ngồi đọc sách để làm quiz thì lại bỏ thời gian ra ngồi gõ cạch cạch viết blog. Ngạc nhiên chưa.

Và làm được 4 bài là do đề dễ, không phải do mình giỏi.

Educational Codeforces Round 98 (Rated for Div. 2) - A & C

Deadline ngập đầu xong tự rước thêm deadline vào thân, xong tự dưng buổi tối lại ngồi gõ code contest.

Vẫn như mọi khi, code nhiều nhưng vẫn thiếu não.

Tân sinh viên

Mình đã từng là tân sinh viên.

Codeforces Round #677 (Div. 3) - Problem A, B, C & E

Đây là Div.3 với đề dễ nên giải được nhiều. Quan trọng là nhiều bao nhiêu cũng không đủ, vẫn ngu.

Bubble Cup 13 - Finals [Online Mirror] - problem G

G. Years

Lược dịch: Trong một sứ mệnh du hành vũ trụ, người ta phát hiện bằng chứng đã từng tồn tại nền văn minh ở một hành tinh nọ. Họ may mắn tìm được một quyển sách ghi toàn bộ năm sinh và năm mất của các cư dân đã từng tồn tại trên hành tinh này và điều thú vị là những con số được ghi trong sách đều nằm trong khoảng (1, 10⁹)! Do đó, hành tinh này được gọi là Longlifer.

Để biết nhiều hơn về dân số trong quá khứ của Longlifer, các nhà khoa học cần xác định năm mà có nhiều cư dân còn sống nhất, cũng như dân số của Longlifer vào năm đó. Nhiệm vụ của bạn là giúp các nhà khoa học giải quyết vấn đề này!

Educational Codeforces Round 96 (Rated for Div. 2) - Problem A & B

Như mọi lần trước, vẫn làm nhiều nhưng vẫn ngu.

Cheat MateQuiz

MateQuiz is a site that allows you to create a quiz and challenge your friend's knowledge about you. This site's advantage is it does not require Facebook connection before creating a new quiz / submitting an answer.

For educational purposes only.

This is a sample quiz link.

Grakn Forces 2020 - Problem A

Làm chơi ai ngờ tụt rating

Codeforces Round #673 (Div. 2) & Codeforces Round #674 (Div. 3)

Đây là 2 bài trong 2 contest khác nhau, gom lại 1 post cho nó đỡ ngắn.

Codechef September Lunchtime 2020 - Division 2

Một thầy trong trường mình từng bảo, "chỉ khi nào các em vứt bỏ được sự thông minh, khi đó các em mới làm Toán được". Tối hôm qua mấy cái problem này là Toán, nhưng thực ra chỉ cần suy nghĩ đơn giản tí là xong.

Dù là làm việc gì cũng phải suy nghĩ cẩn thận nhưng mình lại là một giống loài đặc biệt gì đấy luôn làm hỏng những gì đơn giản nhất bằng cách phức tạp hóa vấn đề đến một mức độ mà bản thân mình cũng ngạc nhiên là làm sao lại suy nghĩ làm gì cho cực. Đến khổ/

Codeforces Round #671 (Div. 2) problem A & D1

Lâu lắm mới dám quay lại làm Codeforces. Nhưng cái vấn đề vẫn là làm nhiều vẫn ngu, vô thưởng vô phạt.

Trỏ subdomain về Blogger

Bài viết dành cho các bạn chỉ có domain mà không có host như mình, với điều kiện là bạn được toàn quyền truy cập vào DNS Zone để có thể chỉnh sửa DNS cũng như các records của domain.

Thật ra là nhiều chỗ post tutorial này rồi nên mình cũng viết cho vui để sau này có trục trặc gì thì nhìn lại thôi chứ cũng chẳng có ai đọc đâu. Vậy nhé.

Đặt vấn đề: mình có một tên miền, tạm gọi là example.com. Vì tài chính có hạn, mình muốn example.com là email host và cùng lúc làm blog domain. Muốn như thế, bằng một cách xử lý cồng kềnh, mình sẽ trỏ một subdomain, tạm gọi là blog.example.com về blogger và giữ nguyên example.com làm email host.

Vấn đề phát sinh: do mình không mua host nên không được hỗ trợ cPanel aka không có chức năng hỗ trợ tạo subdomain. Vì vậy mình sẽ phải tự tạo subdomain bằng các công cụ chỉnh sửa domain records. Về nguyên tắc là chỉ cần tạo một subdomain xong thì cứ trỏ subdomain đó về Blogger giống như trỏ domain về Blogger, thế là xong.

1. Trỏ domain về Blogger

Để trỏ domain về Blogger thì bạn làm theo hướng dẫn trong post này là ok. Mình không viết lại vì tutorial đã quá rõ ràng rồi, viết lại thì càng thêm sai thôi.

Tuy nhiên, ta có một chút thay đổi và nếu bạn để ý thì sẽ thấy rõ: hướng dẫn bên trên đang trỏ domain về Blogger trong khi ta đang cần trỏ subdomain về Blogger cơ mà?

Thật ra cách giải quyết khá đơn giản: tại ô domain bạn cứ điền nguyên subdomain vào, trong trường hợp này là blog.example.com.

Khoan, subdomain này đã tồn tại đâu mà trỏ về?

2. Tạo subdomain

Ở bước cơ bản để trỏ domain về Blogger, bạn sẽ tạo 2 CNAME records: www và secret key. Bây giờ, hãy thay record www bằng subdomain của bạn và mọi việc hoàn tất rồi đó.

Nếu bạn chú ý tấm hình bên trên thì Blogger cũng hướng dẫn cách này rồi, chỉ là việc tạo subdomain nó hơi rối nếu như bạn chỉ mua domain mà không mua host như mình rồi lại tìm cách tạo subdomain tới lui, trong khi chỉ cần đọc kỹ một chút hướng dẫn là ổn.

3. Tổng kết.

Đến đây bạn sẽ cần đợi một chút (~ 1h) để mọi thứ hoạt động tốt. Chú ý là bạn đang trỏ subdomain về Blogger bằng cách thay thế CNAME www thành subdomain của bạn, nên truy cập vào www.example.com sẽ không được nhé. Muốn có www thì phải có vài magic khác, nhưng mình sẽ không đề cập đến trong post này để tránh loãng post.

Mong các bạn vui/

* example.com vẫn truy cập bình thường và chỉ được dùng làm ví dụ trong post này.

Shitpost đêm khuya #9: Cúi đầu

Ngày mai là giỗ ông nội mình. Bây giờ là 12h kém 15 đêm, mình vẫn ngồi đây lọ mọ viết.

Free domain của GitHub Student Pack sắp hết và mình đã tìm được một bến đỗ mới. Chỉ có điều là email trên tên miền này nhìn khá giống mail spam thôi, nhưng miễn mình thích thì được, xấu đẹp không quan trọng.

Codeforces Round #666 (Div. 2) - A

Đi quân sự vẫn fail

Vui

August Lunchtime 2020 Division 2

Vừa xem lại rating trên Codechef mới phát hiện NOV19B bị đánh dấu đạo bài, trong khi mình vắt óc làm mới AC được có 2 bài, đã khiếu nại mà không biết có được giải quyết hay không. Nhưng có một điều mình sure kèo là mới bị đánh đạo bài gần đây, vì NOV19B diễn ra hồi tháng 11 năm ngoài mà lần cuối cùng mình vào Codechef là August Challenge đầu tháng 8 thì kết quả NOV19B của mình vẫn chưa bị gì.

Chả hiểu làm ăn kiểu gì vậy nữa, công sức người ta làm như thế mà đánh đạo bài như thật huhu.

Educational Codeforces Round 94 (Rated for Div. 2) - Problem A

> Write blog

> No one gaf

Actually, this is a big achievement for me anons, since I wrote this blog for me and only me to read.

Codechef August Challenge 2020 - Division 2

> Finished finals

> Go home

> gatheredfamily.png

> Sleep

> Wake up

> 3rd day at the dorm, 1 week to go

I'm suffering from the finals right now anons.

Educational Codeforces Round 93 - Problem A&B

> Joined contest

> Solved 2 out of 7

> pain.png

> Monday is the first day of last week before I travel back home

Idk anons, may be this is the last nice week?

Codeforces Round #664 (Div. 2) Problem A & B

> Be me, have final tests and still spending time to do competitive programming.

Don't. Seriously, don't.

A. Rainbow Dash, Fluttershy and Chess Coloring - Codeforces Round #662 (Div. 2)

Link đề bài trên Codeforces.

A. Remove Smallest (Codeforces Round #661 (Div. 3))

 Link đề bài trên Codeforces

A. Common Prefixes - Codeforces Round #659 (Div. 2)

Link đề bài trên Codeforces.

CHEFSTEP - July Lunchtime 2020 Division 2

Link đề bài trên Codechef

Tóm tắt đề bài: Chef chỉ đi được những quãng đường lớn hơn hoặc bằng và chia hết cho độ dài một bước chân của Chef. VD: mỗi bước của Chef dài 5 đơn vị, khi đó Chef chỉ đi được các quãng đường 5, 10, 15 (còn nữa) đơn vị và không đi được các quãng đường 4, 6, 9, 11, 12 (còn nữa) đơn vị.

Hướng dẫn: Duyệt, những số chia hết và lớn hơn hoặc bằng K thì output 1, còn lại output 0.

Link code mẫu (C++).

Happy coding!

A. Common Subsequence - Codeforces Round #658 (Div. 2)

Link đề bài

Tóm tắt đề bài: Cho 2 mảng A và B. Tìm một dãy con chung (khác rỗng) của A và B sao cho dãy con này có ít phần tử nhất.

Một cách diễn đạt khác: Vì dãy con có ít phần tử nhất mà không rỗng của A và B có 1 phần tử nên bài toán này thực chất là đi tìm 1 phần tử chung của 2 dãy A và B, không quan trọng thứ tự xuất hiện của phần tử chung đó.

Hướng giải: Có nhiều cách khác nhau để cài thuật giải, chung quy vẫn là tìm một phần tử xuất hiện trong cả 2 dãy A và B. Nói chung là cài kiểu gì (miễn đừng điên quá) cũng AC.

Code mẫu mình để ở đây.

Mình càng ngày càng bận, từ bài tập trên lớp đến đồ án, đôi khi là mấy cái dự án con con để thỏa mãn cái nhu cầu của bản thân. Nên mình sẽ không dịch bài nữa, chỉ tóm tắt lại thôi nhé. 

1385B - Codeforces Round #656 (Div. 3)

Link đề bài trên Codeforces.

Tóm tắt: bạn được cho một mảng có kích thước 2*n. In ra màn hình mảng kích thước n gồm các phần tử của mảng 2n bên trên sao cho mỗi phần tử chỉ xuất hiện 1 lần theo đúng thứ tự trong mảng 2n bên trên.

Ví dụ:

Input:

5

2

1 1 2 2

4

1 3 1 4 3 4 2 2

5

1 2 1 2 3 4 3 5 4 5

3

1 2 3 1 2 3

4

2 3 2 4 1 3 4 1

Output:

1 2 

1 3 4 2 

1 2 3 4 5 

1 2 3 

2 3 4 1 

Giải thích:

Ở bộ test đầu: [1, 1, 2, 2] có 2 phần tử khác nhau là 1 và 2, theo đúng thứ tự xuất hiện trong mảng đầu sẽ là [1, 2]

Ở bộ test thứ 2: [1, 3, 1, 4, 3, 4, 2, 2] có 4 phần tử khác nhau là [1, 2, 3, 4], theo đúng thứ tự xuất hiện trong mảng đầu sẽ là [1, 3, 4, 2].

Hướng dẫn giải:

Bài này chỉ duyệt mảng đơn giản. Sử dụng unordered_set, set hay map để lưu các giá trị đã xuất hiện trong mảng. Cuối cùng chỉ cần một mảng lưu lại các phần tử này theo đúng thứ tự xuất hiện của chúng là ổn.

Link code mẫu

FACEFRND - Friends of Friends

Link đề bài trên SPOJ

Đề bài:

Bob hay lên mạng xã hội chơi và giờ Bob đang thắc mắc: không biết khai niệm "Bạn của Bạn (Friends of Friends)" trong mạng xã hội đó là sao? Nếu $X$ là bạn của Bob, $Y$ là bạn của $X$ nhưng $Y$ không phải là bạn của Bob thì $Y$ là một người "Bạn của Bạn" của Bob. Bạn được yêu cầu tìm số lượng người "Bạn của Bạn" của Bob. (Mỗi người trong mạng xã hội đó được định danh bằng một ID 4 chữ số).

Input:

Dòng đầu tiên chứa một số nguyên $N\ (1 \leq N \leq 1000)$ là số lượng người trong danh sách bạn bè của Bob. Tiếp sau đó là $N$ dòng:

• Đầu mỗi dòng là ID người bạn của Bob.
• Tiếp sau đó là số nguyên $M\ (1 \leq M \leq 100)$ là số lượng người trong danh sách bạn bè của người đó.
• Tiếp sau đó là $M$ ID lần lượt là ID của từng người bạn (ngoại trừ Bob).

Output:

In ra một số nguyên duy nhất - số lượng người "Bạn của Bạn" của Bob.

Ví dụ:

Input:

$3$
$2334$ $5$ $1256$ $4323$ $7687$ $3244$ $5678$
$1256$ $2$ $2334$ $7687$
$4323$ $5$ $2334$ $5678$ $6547$ $9766$ $9543$

Output:

$6$

Hướng dẫn giải

Từ ví dụ bên trên, ta có thể chỉ ra được những người "Bạn của Bạn" trong ví dụ là $3244, 5678, 6547, 7687, 9543$ và $9766$. Tổng quát về cách giải: ta ghi những ID là bạn của Bob (ID đầu tiên mỗi dòng) vào 1 mảng, ghi những ID còn lại vào một mảng. Nếu ID trong mảng bạn Bob tồn tại trong mảng còn lại thì ID đó không được tính là "Bạn của Bạn".

Bài này tiện nhất là dùng STL set vì tìm kiếm sẽ nhanh hơn, kiểu dữ liệu cũng nên để là string thay vì int vì ID vẫn có thể có số 0 ở đầu. Code mẫu mình để ở đây.

Chốt:

Happy coding!

Install & configure Atom for C/C++ learning.

(Written in English, since I've just got Grammarly installed and curious to see how it works). 

Since I came to college, many friends have asked me: "what IDE is that? looks so cool/nice/awesome, how can I install it?". So I decided to write this small (but to be honest, not short) tutorial, digging in how to install Atom text-editor, customise and install further extensions for C/C++ learning. 

Note that this is not a complete, detailed tutorial. I just give you some YouTube and other pages link, then you'll do steps yourself since other tutorials are more detailed than what I can write. 

Let's get started. 

The reason why I choose Atom 

Atom installation is quite simple, but the configuration to make it supports C/C++ is some kind of complex itself. 

I choose Atom in a coincidence. Before learning C++, I was a PHP/JavaScript developer. At that time, I used Sublime Text 3 (of course, without a license). Then, I've to choose for another editor, which is free and easy to use, also have packages support PHP and have a nice-looking theme. Randomly, a guy I watched on YouTube was using Atom, and yes, I tried and fall in love with it. 

First, let's dig into installing. 

Installing Atom. 

This step is actually very simple, just like how you install other software: go to the homepage, download the installation file, run the installation file, wait for a couple of minutes and boom, done. 

Maybe you missed this fact: Atom is an open-source project, a.k.a you can find the source code of Atom on GitHub. Further, Atom is made by GitHub. So, don't hesitate to have a look at the Atom project on GitHub and join the Atom community. 

Atom homepage: https://atom.io

Atom project on GitHub: https://github.com/atom/atom

After installation, we'll move on to customise Atom. 

Customisation. 

When you got to Atom project page on GitHub, you'll see the description line: "The hackable text editor". That tells everything: you can "hack" Atom aka have some coding stuff to make Atom become what you want, using CSS.

I'm not currently doing any Atom customising stuff, except having some CSS overwritten to increase line-spacing. Here's how I did it: 

In Settings (usually can be open with `Ctrl + <` hotkey), choose Open Config Folder. 

In `style.less`, customise your style with CSS. 

Notice that this is not Atom's default theme. Here's what I'm using: 

- UI: atom-material-UI. 

- Syntax: atom-material-syntax. 

- Font: Fira Code. 

- Icons: file-icon. 

For installation: each plugin has their own Installation section, you can have a look at them to find out more. Since these tutorials are so detailed, I'll not go further on this.

With Atom customisation, you can go further by have a glance at this Atom Flight Manual: https://flight-manual.atom.io/

So, installed and customised, but we're installing Atom for C/C++ developing. So, 

C/C++ development. 

Now we get into the main problem. As I've mentioned above, Atom is a text editor, unlike Visual Studio having C/C++ compiler integrated, you must install a third-party compiler to compile and run C/C++ code. 

My settings: 

• Compiler: MinGW. 
• Packages: gpp-compiler (for compiling C++ code) + linter + linter-gcc2 + linter-ui-default (flagging errors live). 

For compiler installation, look at this video. Packages installation is the same as installing themes. 

At here, congrats! You've now joined the Atom C/C++ community! 

Final 

As I've said at the beginning, this post is mostly about links and YouTube videos. If I wrote a tutorial, it will not as detail as those existing tutorial out there. So linking them is the best way here. Notice that this is the configuration for learning only. For professional C/C++ development, you should use a proper IDE (e.g Visual Studio, Eclipse, ..etc).

Hope the ones who are asking "what is your text editor, Quan?" can found something useful in this post. 

Farewell. 

(This post got 99pts in Grammarly, with 4 premium alerts on Improper Formatting, Word Choice, Incomplete Sentences and Closing Punctuation). 

Chuyện đêm tháng 6.

(Wall of text, không có hình).

Cốc cafe nhà Nội

Ba năm cuối Tiểu học mình ở nhà nội cho gần trường. Hai ông bà có hẳn một quy trình lặp đi lặp lại mỗi buổi sáng: sáng bố đưa mình xuống nhà ông bà; mình trông nhà, ông chở bà đi chợ (hoặc hôm nào ông đi họp thì bà đi bộ), tiện thể ông sẽ mua 1 tờ báo; ông bà đi chợ về, mình đi sang lớp học thêm gần nhà ông bà; mình học thêm về thì bà đã nấu xong cơm trưa. 

Lúc nào cũng vậy, nấu cơm xong là bà sẽ tự pha 1 cốc cafe sữa, pha thêm cho mình 1 cốc Milo vì trẻ con uống cafe không tốt. Đến một ngày, Milo hết mà bà quên mua thêm. Thế là mình được uống ké cafe sữa của bà, và đó là lần đầu tiên mình uống cafe.

Công thức pha cafe của bà cũng chẳng có gì đặc biệt: cafe hòa tan pha đường hoặc thêm tí sữa, sau đó đập nhuyễn đá bỏ vào. Bà bị bệnh tiểu đường, hay tụt đường huyết nên cốc cafe sữa mỗi buổi trưa là để phòng tụt đường huyết đột ngột. Tất nhiên là bà mình có uống thuốc điều hòa đường, và lượng đường trong mỗi cốc cafe của bà là vừa đủ.

Nhiều người bảo là cafe hòa tan uống không bằng cafe pha phin. Mình cũng có thời gian nhận xét y chang như vậy. Cấp 2 rồi cấp 3, mình không ở nhà nội nữa mà về nhà ở ngoại thành. Trường mình vẫn gần nhà nội hơn, nên đôi khi trống tiết hoặc tan học sớm là mình lại đi bộ về nhà nội. Nội chiều ý mình, pha cafe đen sẵn, đến khi mình về là tự pha sữa và đập đá vào thôi.

Cốc cafe nhà nội, ở nhà nội

Cafe là để nhấm nháp chứ không phải là một thức uống giải khát thông thường.

Ông mình mất năm 2011. Bà sống một mình từ đó đến nay. Bà buồn nhiều lắm, nhưng theo thời gian bà cũng nguôi ngoai dần. Hồi ông mới mất, cứ cuối tuần là mình lại xuống ở với bà vào cuối tuần cho bà đỡ buồn. Lúc nào cũng vậy, vẫn là một ca cafe sữa hòa tan, mình chơi game, bà xem phim.

Đến cấp 3, trường cấp 3 mình lại gần nhà mình hơn, nên việc đi bộ về nhà nội là điều không tưởng. Năm lớp 11 mình học nghề gần nhà nội, mỗi chiều tan học mình lại ghé qua nhà nội một chút, vẫn là ca cafe sữa đá nhuyễn, nó tiếp thêm cho mình chút năng lượng để buổi tối học Lý, Hóa.

Lên đại học, cafe đen chỉ có ở những quán xa xôi tít trong trung tâm Sài Gòn. Ở Thủ Đức, cafe chỉ là cafe pha sẵn đặc quánh hoặc cafe hòa tan. 

Nhiều buổi tối mình pha 1 cốc cafe hòa tan, mua gói sữa chế vào khuấy lên. Mùi cafe hòa tan đưa mình quay trở lại lúc lớp 3. Trong đầu mình lại hiện ra hình ảnh cậu bé mở cổng rào, chào ông đang đứng phơi quần áo, chạy vào bếp chào bà đang đứng phi hành. Bà chỉ tay vào cốc cafe còn nóng, bảo là "nội mới pha đó, con tự đập đá vào đi".

Đến bây giờ suy nghĩ của mình có chút thay đổi: cafe dù là hòa tan hay nguyên chất, nó vẫn là cái kỷ niệm gì đó rất đặc biệt đối với mình. Nó không chỉ là thức uống giải khát để uống như nước lã. Mỗi khi mình uống cafe là mình lại hoài niệm về một thời rất xa, về những người còn và đã mất.

Trưa nay mình về quê, lại ghé nhà nội đầu tiên. Mình không báo trước cho nội biết. Nội gặp mình cũng bất ngờ và vui lắm. Sau khi ôm hôn cháu mình, bảo mình cởi vớ ra cho đỡ nóng chân, câu tiếp theo nội bảo, sau bao nhiêu năm, vẫn là "nội có pha cafe trong nhà đó".

Mất file mã nguồn!

Một sự cố do mình, dù hy hữu nhưng đã xảy ra, mà mình nghĩ nên ghi lại để sau này không ngu người mà mắc phải nữa.

LIFTME - Lift Requests (Codechef April Cookoff 2020 - Divison 2)

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: Một cái thang máy đang ở tầng 0 (tầng trệt). Mỗi truy vấn bạn sẽ nhận vào 2 tham số d và f, theo đó thang máy sẽ đi đến tầng d để đón người và trả ở tầng f. Trong mỗi truy vấn thang máy sẽ không dừng lại ở tầng nào, aka phải thực hiện hết truy vấn này đến truy vấn khác. Đếm số lượng tầng mà thang máy đã đi qua, biết rằng đi từ d đến f sẽ đi qua | f - d | tầng.

Giải thích output mẫu:

• Ở truy vấn thứ 1: 1 2, thang máy ban đầu ở tầng 0 -> 1, rồi từ 1 -> 2 => 2 tầng.
• Ở truy vấn thứ 2: 0 1, thang máy đang ở tầng 2 -> 0, rồi từ 0 -> 1 => 3 tầng.
• Ở truy vấn thứ 3: 1 0, thang máy đang ở tầng 1 -> 0 => 1 tầng

Tổng cộng: 6 tầng.

Hướng dẫn: Bài này duyệt cơ bản, điểm bắt đầu của truy vấn sau là điểm đích của truy vấn trước. Kiểu dữ liệu để long là dư sức AC.

Link code mẫu (C++)

Happy coding!

Codechef April Long Challenge 2020 - Division 2

Contest lần này đánh vào number theory khá nhiều nên mình solve được tận 5 bài :D Cơ mà số lượng bài nhiều quá, viết editorial trong 1 post thì hơi khoai nên mình sẽ chia ra nhiều post rồi dẫn link lại post này:

Bài 1: CARSELL - Sell All The Cars

Bài 2: COVIDLQ - COVID Pandemic and Long Queue

Bài 3: STRNO - Strange Number

Bài 4: UNITGCD - Unit GCD

Bài 5: SQRDSUB - Squared Subsequence

Happy coding!

SQRDSUB - Squared Subsequence

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn được cho một mảng A gồm N phần tử. Một đoạn "tốt" là một dãy các phần tử liên tiếp có tích biểu diễn được dưới dạng hiệu của hai số chính phương. Đếm số lượng đoạn "tốt" trong mảng A.

Khái niệm "đoạn con" sử dụng trong bài được định nghĩa là dãy các phần tử liên tiếp. Một phần tử cũng được tính là một đoạn con.

Hướng dẫn giải: Để một số có thể biểu diễn dưới dạng hiệu của hai số chính phương thì số đó phải là số lẻ hoặc là bội của 4 (để tập trung vào giải thuật, phần chứng minh các bạn đọc thêm trên MathExchange: chứng minh một số lẻ bất kỳ có thể được biểu diễn dưới dạng hiệu của hai số chính phương và chứng minh một số là bội của 4 có thể biểu diễn dưới dạng hiệu của hai số chính phương). Trái lại, một số chẵn mà không chia hết cho 4 sẽ không thể biểu diễn dưới dạng hiệu của hai số chính phương.

(*) Từ phần xanh lá, ta có thể đưa bài toán về bài toán "đếm số lượng đoạn không thể biểu diễn dưới dạng hiệu của hai số chính phương (U)", sau đó dùng tổng số lượng đoạn con có thể tạo trừ đi U sẽ thu được kết quả cần tìm.

Tổng quát: số lượng đoạn con có thể tạo từ một dãy N phần tử là . 

Để một đoạn con có tích chia hết cho 2 nhưng không chia hết cho 4, ta chỉ cần xác định vị trí của các phần tử mà biểu diễn dưới dạng tích các số nguyên tố của nó chỉ có 1 số 2 duy nhất, gọi là số neo. 1 số chẵn nhân với 1 số lẻ ra một số chẵn, mà số chẵn ban đầu không chia hết cho 4 dẫn đến kết quả sau khi nhân số lẻ cũng sẽ không chia hết cho 4. Do vậy, công việc của ta là đếm số lượng số lẻ ở 2 bên của số neo, tính tổng số lượng đoạn con có thể tạo thành.

Cần chú ý là nếu 2 bên của số neo không có số lẻ nào thì độ dài dãy đó bằng 1. Làm theo (*) là ta có được kết quả đề bài.

CU;WTF?: tìm trong mảng A những số chia hết cho 2 mà không chia hết cho 4. Với mỗi số đó, đếm xem bên trái có bao nhiêu số lẻ, bên phải có bao nhiêu số lẻ, cộng 2 cái đó lại, cộng thêm 1 là số 2 đứng giữa. Tính theo công thức  là tìm được tổng số đoạn con dạng U. Lặp lại đến hết mảng A, rồi lấy tổng số đoạn con của mảng A trừ tổng số đoạn con dạng U là ra kết quả.

Bài này không khó nhưng cài thuật ad-hoc rất khó.

Code mẫu (C++)

Happy coding!

UNITGCD - Unit GCD

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn có 1 quyển sách được đánh số từ 1 đến N. Mỗi ngày bạn được đọc một số trang nhất định sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau. Tìm số ngày ít nhất để đọc hết cuốn sách cũng như cách đọc trong từng ngày. Chú ý là mỗi ngày bạn được đọc một số trang sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau, nghĩa là mỗi ngày bạn phải đọc ít nhất là 2 trang.

Hướng dẫn giải: Đây là Nguyên lý Chuồng bồ câu (hay Nguyên lý Dirichlet) trong Toán rời rạc. Từ 1 đến N, cứ 2 số nguyên liên tiếp sẽ tạo thành 1 cặp số nguyên tố cùng nhau. Số ngày tối thiểu để đọc hết N trang sách là trang - cũng là số cặp số nguyên tố cùng nhau không lặp lại có thể chia được. Trong đó, trường hợp N lẻ chúng ta có tập kết quả lớn nhất gồm 3 phần tử {1, 2, 3}, còn lại là các cặp nguyên tố cùng nhau. Công việc cần là phân loại theo điều kiện N và in kết quả ra thôi.

CU;WTF (Cannot Understand, WTF?): in ra các tập 2 phần tử. Ví dụ: N = 4 => {1, 2}, {3, 4}. Nếu N lẻ thì in 3 phần tử đầu rồi cứ in 2 phần tử làm tới. VD: N = 5 => {1, 2, 3}, {4, 5}; N = 9 => {1, 2, 3}, {4, 5}, {6, 7}, {8, 9}. Chú ý trường hợp N = 1 thì chỉ in ra 1 phần tử thôi.

Code mẫu (C++)

Happy coding!

STRNO - Strange Number

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn được cho 2 số nguyên dương X và K. Xác định xem tồn tại một số nguyên dương A sao cho A có đúng X ước số, trong X ước số đó có K ước số là số nguyên tố.

Ví dụ: với X = 4, K = 2, ta có thể tìm được A = 6. Số 6 có 4 ước (1, 2, 3, 6), trong đó 2 ước (2, 3) là số nguyên tố.

Hướng dẫn giải:

Lý thuyết: Phân tích một số nguyên A ra thừa số nguyên tố  (với p là một số nguyên tố). Khi đó tổng số ước N bằng .

Ở đây A chỉ có đúng K ước nguyên tố, nghĩa là trong đa thức   tồn tại ít nhất K đa thức có dạng . Để giải được bài này, ta cần phải đếm xem có thể phân tích X thành số nguyên tố bao nhiêu lần. Mỗi số nguyên tố của X sau khi phân tích sẽ ứng với một đa thức  , và nếu tổng số đa thức >= K thì ta có thể xây dựng được số A.

Code mẫu (C++)

Happy coding!

COVIDLQ - COVID Pandemic and Long Queue

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: Có một dãy N chỗ đứng, chỗ thứ i được đánh dấu là "1" nếu có người đứng và "0" nếu không có ai đứng. Khoảng cách giữa chỗ thứ i và i + 1 là 1 feet. Dịch COVID đang hoành hành, mỗi người được khuyến khích phải đứng cách nhau 6 feet trở lên (>= 6 feet). Xác định xem trong hàng đó có người nào vi phạm khoảng cách an toàn hay không?

Hướng dẫn giải: bài này duyệt bình thường, kiểm tra 2 vị trí liên tiếp có người đứng (aka 2 số "1" liên tiếp) cách nhau bao xa, nếu < 6 feet thì vi phạm. 

Code mẫu (C++)

Happy coding!

CARSELL - Sell All The Cars

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn có N chiếc xe và cần phải bán hết N chiếc xe đó, mỗi năm chỉ được bán 1 chiếc. Chiếc xe thứ i có giá P[i] đồng, sau mỗi năm thì giá của mỗi chiếc xe sẽ giảm đi 1 đồng. hãy tìm cách bán sao cho đến khi bán xong chiếc xe cuối cùng bạn sẽ thu về được nhiều tiền nhất.

Hướng dẫn giải: Phương pháp tham lam. Cách tốt nhất để bán hết xe và nhận về lợi nhuận cao nhất chính là sắp xếp xe theo giá giảm dần rồi bán từ từ, chú ý trường hợp giá xe tụt xuống < 0 thì sẽ tính là = 0.

Chú ý: với các phép toán có sử dụng modulo:

Phép cộng: (a + b) mod c = ((a mod c) + (b mod c)) mod c

Phép trừ: (a - b) mod c = ((a mod c) - (b mod c)) mod c

Phép nhân: (a * b) mod c = ((a mod c) * (b mod c)) mod c

Code mẫu (C++)

Happy coding!

UCV2013I - Tambourine

Link đề bài 
Link hướng dẫn giải + code mẫu

Happy coding!

UCV2013J - Valences

Một bài toán có Hóa nhưng không phải về Hóa, có Cây nhưng không phải về Cây :)

Link đề bài
Link hướng dẫn giải + code mẫu

Happy coding!

SWPDGT - Codechef March Lunchtime 2020 - Division 2

Mình vẫn nợ 1 bài code Lunchtime tháng 3 chưa viết editorial, cũng là bài duy nhất mình giải được trong contest này :(

Link đề bài trên Codechef - bản dịch tiếng Việt

Hướng dẫn giải:

Xét một số nguyên trong đoạn [1, 99]. Số đó có thể được biểu diễn dưới dạng 10*A + B, với A và B lần lượt là các số nguyên. VD: 28 = 10*2 + 8 (A = 2, B = 8), 56 = 10 * 5 + 6 (A = 5, B = 6).

Nếu lấy 28 + 56, ta có các khả năng swap vị trí như sau: 28 + 56, 68 + 52, 25 + 86. Chúng ta không xét tới các khả năng 58 + 26 hay 26 + 58, vì 2 khả năng này cho kết quả như nhau (và cùng bằng 28 + 56), lý do là vì tính chất giao hoán của phép cộng đều cho kết quả như nhau.

Đối với trường hợp phép cộng giữa một số có 2 chữ số với một số chỉ có 1 chữ số (VD: 12 + 9), ta vẫn swap vị trí như trên, nhưng lúc này chỉ còn 1 vị trí có thể swap (91 + 2). Trường hợp còn lại là phép cộng giữa 2 số có 1 chữ số thì tổng lớn nhất là tổng của 2 số đó, không cần swap.

Code mẫu (C++)

Happy coding!

Shitpost đêm khuya #8

Hôm nay là 1/4 (April's Fool Day). Mọi người còn online ngoài kia đua nhau đi tỏ tình, trêu đùa với bạn bè, người thân của mình. Riêng chỉ có mình ngồi 1 mình trong phòng khách, bên cạnh là ca cafe đã tan hết đá, cùng với chiếc laptop hơi bám bụi, lụi cụi gõ ít dòng tâm sự.

Giữa lựa chọn được đi nước ngoài và ở lại Việt Nam, mình chọn đi nước ngoài. Dạo gần đây có một vài quan điểm cho rằng những du học sinh ra nước ngoài là những cậu ấm, cô chiêu, những "xã hội Đỏ, thái tử Đảng" được cử ra nước ngoài tìm vé định cư và một sân bay an toàn để sau này quý thân sinh có đường băng hạ cánh an toàn. Mình có một người bạn cấp 2, đã sang Australia học tập từ cuối tháng 9. Trong một comment, khi được hỏi "Sao không về Việt Nam tránh dịch?", cậu ấy đã bảo là "Có gan đi thì dám ở".

Và thật sự là như vậy, một khi đã chọn con đường ra đi tìm kiếm sự nghiệp, vươn tới một chân trời mới thì phải có bản lĩnh, gan dạ mà chịu trách nhiệm cho những hành động của mình. Đã gần 20 tuổi, mình thật sự chưa hình dung được cuộc sống của mình ở nước ngoài (nếu giả sử mình được ra nước ngoài sinh sống / học tập) như thế nào. Và nếu có được cơ hội đó, liệu mình có đủ bản lĩnh bám trụ lại như cậu bạn bên trên không?

Xoay đi quay lại, cũng có vài lý do khác để mình cảm thấy rằng bản thân mình chẳng có chút bản lĩnh nào. Mình đã nói dối về ngành học tương lai gần 2 năm. Ngày ấy mình bảo mình chọn Vật lý hạt nhân, khiến cho gia đình phải khuyên đi khuyên lại hết lời, nhưng cơ bản trong thâm tâm mình vẫn chọn IT vì mình đã gắn bó từ cấp 2, chỉ dương Đông kích Tây để khỏi bị soi mói thôi. Chẳng qua là mình không đủ bản lĩnh để đối mặt với thực tại, đối mặt với mọi người. Nhưng sau khi đỗ, may sao, mọi người vẫn hiểu cho mình.

Rồi mình không chọn trở thành một người lập trình làm việc tại các công ty, viết những phần mềm giúp ích cho xã hội. Mình lại chọn CS, vì đơn giản mình không muốn phí những gì mình đã được học - một lời bao biện cho sự thiếu tự tin. Mình không tự tin vào kỹ năng lập trình, không tự tin vào khả năng tư duy hay khả năng giải quyết vấn đề dưới áp lực. Thế là mình lại chọn CS.

Và cuối cũng, mình viết bài post này vì lý do chính là mới xem được tốc độ gõ phím của SGO48 Ashley là 111WPM trong khi của mình chỉ có 50WPM. Mình viết post này chỉ nhằm mục đích luyện gõ phím, nhưng cũng là tâm sự đôi chút. Thật lòng đấy ạ, không đùa đâu.

Codechef March Lunchtime 2020 - Khi COVID-19 lan rộng đến đấu trường CP

Trước cơn bão COVID-19 đang quay cuồng trên toàn thế giới, nhiều người đã chọn lựa ở yên trong nhà xem Netflix, lưới Facebook hay nghe Spotify để bảo toàn tính mạng cho người thân, gia đình và xã hội. Không gian mạng từ lâu đã là chốn đi về lý tưởng cho các geek khi cái xã hội đau thương bi ai ngoài kia quá khắc nghiệt đối với họ. Họ cho rắng khi đã lên mạng, tham gia các contest CP, nộp những bài code và giành vài điểm rating là một cái thú vui tao nhã không thể nào bị suy chuyển bởi kinh tế thế giới, biến động chính trị hay thiên tai dịch bệnh.

Mình đã tham gia các cuộc thi CP trên Codechef từ tháng 10/2019. Tối nay đúng lịch sẽ diễn ra Codechef Lunchtime tháng 3, mình đã chuẩn bị sẵn template code, đồ ăn thức uống, mọi thứ đều đã sẵn sàng để xin ít rating và nhảy lên cao thêm chút.

Thế mà, contest này diễn ra theo chiều hướng tệ hơn mình tưởng. Website contest sập 15 phút, lúc 20h15 IST các nhà tổ chức thông báo sẽ thêm 15 phút bù giờ cho khoảng thời gian contest bị delay. Vấn đề là sau 15 phút, đề bài vẫn chưa thể mở, lỗi 500 vẫn diễn ra thường xuyên, downfor.io nhận định Codechef đã down.

Và đến khi Codechef trở lại, mọi thứ còn tệ hơn gấp nhiều lần.

Các submission không thể được chấm đúng giờ vì có quá nhiều submission. Nhiều đến nỗi mình sub 2 sub đầu thì mất hơn 15 phút mỗi sub mới cho ra WA verdict, đến 4 sub sau thì mỗi sub tốn gần 30 phút mới cho ra WA. Tình thế khiến mỗi competitor phải chờ mòn mỏi verdict là một, phải đau đầu vì không mở được đề mới là hai. Họ bắt đầu lập các topics trên discuss forum để khiếu nại.

Đến cuối cùng, admin đã quyết định đóng contest tháng 3. Tất nhiên là các submissions không được tính vào rating, cũng như một lời xin lỗi chân thành của đội ngũ admin đã làm cho cộng đồng dịu lại. Nhưng hơn cả, mình biết nguyên nhân của sự cố này không đến từ admin, kỹ thuật hay cộng đồng. Contest này thu hút quá đông người tham gia, và tất nhiên họ tham gia vì không thể tìm được một thú tiêu khiển nào khác.

Vâng, COVID-19 đã ảnh hưởng đến một đấu trường online, nơi được xem như là bất khả xâm phạm đối với vi trùng / virus. COVID không đánh trực tiếp bằng cách làm server bệnh rồi ngã lăn đùng ra chết; nó hạn chế con người ta ra ngoài đường, hạn chế tụ tập, khiến họ phải tập trung vào những giải đấu online vốn rất ít người tham gia. 

Nếu nhắc đến COVID-19, đây chắc chắn sẽ là kỷ niệm khó quên nhất đối với mình.

Nhưng vẫn có solution cho problem 1 của contest này nhé, đợi mình viết xong editorial rồi sẽ post sau. 

Codechef March Cookoff 2020 - Division 2

Contest này solve được có 1 bài :( Rating tụt thê thảm nhưng vẫn ở rate xanh.

GIFTSRC - Find Your Gift - Link bản tiếng Việt

Tóm tắt đề: bạn đang đứng ở tọa độ (0, 0). Mỗi lần bạn chỉ được di chuyển theo 1 trục khác với lần di chuyển trước. Ví dụ, bạn đang đứng ở (0, 0), bạn bước sang trái đến ô (-1, 0). Bước tiếp theo bạn chỉ có thể bước lên ô (-1, 1) hoặc bước xuống ô (-1, -1), vì nếu tiếp tục bước sang trái hay bước sang phải vẫn sẽ trùng với trục của bước di chuyển trước. Tương tự với việc bước lên / bước xuống.

Hướng dẫn giải: Chỉ cần xác định những bước đi không cùng trục với nhau, rồi tính toán tọa độ dựa trên những bước đi đó là ta có kết quả.

Link hướng dẫn giải + code mẫu

Happy coding!

EDIT - Edit Distance Again

Ngoài lề:

Rất lâu rồi mình mới quay lại SPOJ, một phần vì contest của Codechef cuốn quá, một phần vì Codechef có ban Việt ngữ nên những problem Codechef mình ít phải tự dịch. Nay cái problem này là cái problem mình tự dịch tay sau một thời gian dài bỏ bê dịch diếc, nên có sai sót cũng thông cảm giúp mình ạ :(

Đọc đề bài trên SPOJ

Hướng dẫn giải + code mẫu

Happy coding!