100 câu hỏi được giải quyết nhiều nhất trên spoj năm 2022

Sau một thời gian quá ức chế khi giải bài trên SPOJ mà không xem được test case để biết mình sai chỗ nào ( không giống như codeforces ), mình quyết định viết một tool nho nhỏ để bớt đau đầu về việc mò test thủ công bằng tay.

Ngen là một tool tự động tạo input và so sánh output file thuật toán của bạn, với output file thuật toán đúng. Và điều kiện là bạn phải tự viết file tạo input, và có file thuật toán đã AC. ( code bằng C++ )

Mình đã test và thấy nó khá là tiện + hiệu quả khi giúp mình AC một số bài trước đó mình chưa AC.

Platform: based Unix
GitHub: https://goo.gl/Rw84QM , kèm hướng dẫn

Happy coding 😀

Nguồn bài: Nhạc sĩ Tuấn Khanh

Đầu năm 2016 này, tập đoàn bán lẻ Walmart của Mỹ công bố cho biết họ đóng cửa đến 154 điểm buôn bán trên toàn nước Mỹ. Nếu tính luôn từ năm 2010 đến này, đã có 269 cửa hàng Walmart đóng cửa trong tổng số 11.000 cửa hàng của tập đoàn này trên toàn thế giới. Con số nhìn vào thì không lớn, nhưng các chuyên gia kinh tế đánh giá đó là bước khởi đầu sự sa sút quan trọng của tập đoàn Walmart.

Việc đóng cửa hàng loạt của tập đoàn Walmart có nhiều nguyên nhân, nhưng một trong những lý do luôn được người dân Mỹ quan tâm, đó là làn sóng chỉ trích các hệ thống bán lẻ của Walmart đã tận dụng nguồn hàng giá rẻ làm từ Trung Quốc, gây thương tổn cho nền kinh tế nước nhà, cũng như gây thiệt hại cho quyền lợi của hàng trăm ngàn người lao động Mỹ.

Việc nhập siêu hàng từ Trung Quốc trong chiến lược tạo giá cạnh tranh tuyệt đối của Walmart thoạt đầu có vẻ như được người tiêu dùng ủng hộ, thế nhưng dần dần người ta nhận ra rằng, việc bán hàng giá rẻ đó cũng là một cách hủy diệt quốc gia.

Amy Traub, nhà phân tích chính sách kinh tế hàng đầu của Mỹ, đã từng tố cáo việc ích kỷ tạo lợi nhuận của các công ty thích nhập hàng rẻ từ Trung Quốc đang tàn phá ngành công nghiệp Mỹ. Riêng với Walmart, bà Amy từng nêu bảng phân tích 10 điểm vô cùng nguy hại. Trong đó, đáng lo ngại nhất là im lặng đẩy mạnh nạn thất nghiệp ở nước Mỹ, lên đến 400,000 người (số liệu 2015), đổi bằng con số 20.000 công nhân Trung Quốc bị bóc lột bằng giá lao động rẻ mạt. Không chỉ riêng Ưalmart, mà tất cả các công ty, hãng xưởng đang có khuynh hướng đặt mua hàng giá rẻ từ Trung Quốc đều phải đối diện với lời chỉ trích nặng nề rằng đã đã khiến một lớp công nhân Mỹ chỉ có thể sống bằng lương tối thiểu, đói nghèo, và các nhà máy nội địa phải đóng cửa.

Trong những ngày ở Mỹ vào năm ngoái, tôi chứng kiến những nhóm xã hội dân sự đấu tranh quyết liệt cho quyền lợi lao động và kinh tế của nước Mỹ. Các nhân viên của các hệ thống bán hàng này được lệnh đi tìm và gỡ bỏ các miếng dán trên các kệ hàng, do các nhà hoạt động xã hội chia nhau đi gắn vào, hoặc đứng trước cửa các cửa hàng đó, với nội dung rất mạnh mẽ “Hãy tẩy chay Walmart”, “Đây không phải là nơi có hàng được sản xuất từ nước Mỹ”, “Hàng Trung Quốc từ Walmart đang hủy diệt nước Mỹ”… Trong làn sóng ấy, các món hàng được sản xuất từ Mỹ, lúc này được in nhãn “made in USA” thật to và kiêu hãnh trên sản phẩm, được mọi người chọn mua như một cách chống lại sự xâm lăng hàng hóa từ Trung Quốc hoặc như mọt động thái ái quốc. Rõ ràng là ở một nơi có ý thức, ngay cả việc được hưởng thụ hàng hoá giá rẻ, người ta cũng phải giật mình và hỏi rằng “rồi công nhân mình sẽ sống ra sao?”.

Người của mình rồi sẽ sống ra sao? Đó là câu hỏi như đang bị lãng quên.

Những mùa hoa trái, nuôi giữ của Việt Nam hàng năm cứ luôn bị hụt hẩng do thương lái Trung Quốc hứa hẹn rồi biến mất trong một chuỗi kế hoạch độc ác. Nông dân ngồi khóc ròng trên vệ đường, người trồng trọt đổ bỏ và cho heo, bò ăn để đỡ xót của vẫn diễn ra hàng năm. Vẫn chưa thấy một quan chức nào đủ dũng khí đập bàn và quát lên rằng “rồi nông dân mình sẽ sống ra sao?”.

Sự lệ thuộc vào nền kinh tế Trung Quốc bởi lòng tham và dốt nát về nội lực quốc gia đang giết mòn đất nước. Cứ nhìn vào số nhập siêu của Việt Nam đối với hàng Trung Quốc mà kinh sợ: Phó giám đốc Trung tâm Thông tin Công nghiệp và Thương mại – tiến sĩ Lê Quốc Phương cho hay con số nhập siêu không ngừng tăng qua các năm, từ khoảng 200 triệu USD năm 2001 lên đến 28,9 tỉ USD vào năm 2014, tức tăng 144 lần. Năm 2015, con số còn cao hơn nữa.

Hiện tại ở Việt Nam, các công ty lớn, vỗ ngực tự xưng là thành đạt là “made in Việt” như Tôn Hoa Sen, Number One (Tân Hiệp Phát)… rồi mới đây là Trà Ô long Tea + Plus của Pepsi cũng đều lệ thuộc nặng nề vào nguồn hàng của Trung Quốc. Tiến sĩ Lê Quốc Phương cho biết trong 94 ngành nghề của Việt Nam, đã có tới 40 ngành chết dính với nguồn từ Trung Quốc. Đó là chưa nói đến độ kém chất lượng của thương phẩm, các sản phẩm độc hại của Trung Quốc đang bủa vây người Việt như một cuộc hủy diệt im lặng, cũng không thấy ai có đủ một trái tim Việt Nam thương giống nòi mà kêu gọi “rồi người Việt mình sẽ sống ra sao?”.

Nhưng bên cạnh đó, mọi người dân Việt Nam cũng cần phải tự hỏi: Hàng Trung Quốc dễ dàng nhập vậy, đem lại nhiều vấn nạn như vậy, mà nhiều năm, sao lắm cơ quan hải quan, kiểm tra tốn kém tiền thuế dân, vẫn “ra vẻ” bất lực. Hơn 300 tấn hoa quả độc hại của Trung Quốc mà từ năm 2014, Cục Quản lý chất lượng nông lâm sản và thủy sản của Việt Nam gửi công văn sang Bắc Kinh, đòi Cục An toàn thực phẩm xuất nhập khẩu Trung Quốc trả lời vì sao cố ý nhập vào Việt Nam, đến 2016 vẫn không thấy hồi âm. Vì sao? Vì cơ quan đồng cấp của Bắc Kinh coi thường Việt Nam, hay vì có quá nhiều uẩn khúc ở cửa khẩu khiến mọi thứ phải im lặng? Loại im lặng mà tiến sĩ Nguyễn Ngọc Hiếu của trường Đại học Việt Đức từng nói rằng loại hàng nhập khẩu từ Trung Quốc chỉ có giá 1 đồng, nhưng nhờ đút lót 3 đồng nên cái gì cũng trôi.

Cái gì cũng trôi, số phận con người, nội lực của một quốc gia cũng trôi đi.

Đã từng có các bài báo, các lời kêu gọi người Việt hãy mua hàng giúp nhau, cứu nhau và những lúc xốn xang, khốn khó. Giữa những lúc thương lái Trung Quốc cười gằn và biến mất, để lại một thị trường của những nong dân Việt nghèo và cả tin đầy những hoảng loạn. Nhưng người Việt tự mình khong thể gồng gánh nhau, níu nhau sống mà thiếu một chính sách quyết liệt với anh “bạn vàng”, mà vốn lâu nay các quan chức có trách nhiệm vẫn vẫn hô hoán với màu sắc sân khấu.

Tết Bính Thân này, hàng trung Quốc lại ngập các cửa khẩu Việt Nam. Những tiếng lo lắng lại bật lên ở nhiều nơi. Những trái dưa hấu, những quà bánh, những cành hoa đẫm mồ hôi người nông dân nghèo Việt Nam lại phải gồng gánh trận đấu không cân sức: hàng giá rẻ và sự tiếp tay của trục ác hám lợi, quên cả đất nước mình. Những mùa Tết mà nông dân buồn thiu chở đầy thuyền hoa Tết ế ẩm trở lại quê, những hàng trái cây bán thảo bán đổ để lấy chút tiền vốn… có thể sẽ tái hiện lại ở năm nay. Thật xót xa. Tôi bỗng lại nhớ những tấm băng-rôn mà những người lao động Mỹ căng trên các ngã đường vào Walmart: “Bring our America Back” (Hãy trả lại nước Mỹ của chúng tôi). Mùa xuân này, tôi cũng muốn giăng một biểu ngữ như vậy, “Hãy trả lại một Việt Nam!”, một Việt Nam của tôi!

Đặt vấn đề

Mình có đọc qua một bài hay về Deque và ứng dụng của nó ở blog của bạn Yên Vũ ở đây
Bạn Vũ đã đặt vấn đề và chứng minh đầy đủ, để hiểu hơn bản chất của việc sử dụng Deque, cũng như thuật toán tìm Min/Max cho đoạn (i, j) bất kì của dãy số A; mình quyết định viết thêm bài này.

Kiến thức cần chuẩn bị

Đọc bài viết của của bạn Vũ được trích dẫn ở trên
Tìm hiểu về Deque ? Các bạn có thể search google, nó là một stack 2 đầu, cũng rất dễ hiểu. Để bài viết được sáng sủa, tránh các đoạn code lằng nhằng thì mình sẽ sử dụng deque trong stl của C++.

Tìm Min/Max trong đoạn bất kì của dãy số

Xét dãy A sau đây: 1 3 5 4 2 8 ( mình mượn luôn ví dụ của blog trên ).
Chúng ta sẽ xây dựng 2 Deque, tạm gọi là dmax và dmin, được xây dựng như sau:
+ dmin: đưa chỉ số i vào cuối dmin, nhưng trước khi đưa thì lấy ra hết những chỉ số j đang có trong dmin mà a[j] > a[i]. ( > hay >= đều đúng về mặt bản chất, tuỳ từng bài toán mà ta xem xét nên sử dụng cho phù hợp ), tuy nhiên nên loại a[j] > a[i].
+ dmax: ngược lại với dmin, trước khi đưa i vào thì lấy ra tất cả những chỉ số j đang có trong dmax mà a[j] < a[i].

Cuối cùng chúng ta sẽ có kết quả như sau:

Tại bước thứ i, phần tử đầu tiên của dmin và dmax là chỉ số của 2 giá trị min và max trong đoạn [1,i]. Để tìm được 2 giá trị min/max cho đoạn [j,i] bất kì, chúng ta phân tích tiếp như sau:

Với dmin, tất cả chỉ số j : dmin[i] < j < dmin[i+1] đều thoả a[j] > a[dmin[i+1]] > a[dmin[i]].
( Tương tự cho dmax, tất cả j : dmax[i] < j < dmax[i+1] đều thoả a[j] < a[dmax[i+1]] < a[dmax[i]] ).
Như vậy, dmin[i] sẽ là phần tử nhỏ nhất của đoạn [j,i] với dmin[i-1] < j <= dmin[i], dmin[0] = 0.
( Tương tự cho dmax )
Để thuận lợi, chúng ta sẽ thiết kế thuật toán sao cho dmin.front() và dmax.front() luôn là min/max của đoạn [j,i] đang xét.

Vậy chúng ta có giải thuật tìm min/max của đoạn [j,i] bất kì như sau:
B1: Duyệt từ 1 đến i để xây dựng 2 deque dmin và dmax
B2: Duyệt k từ 1 đến j-1, nếu dmin.front() = k hoặc dmax.front() = k thì pop_front() chỉ số đó ra.
Như vậy đến bước thứ k, dmin.front() và dmax.front() chính là min/max của đoạn [j,i]

Ta có thể xét ví dụ tìm min/max của dãy A đã cho ở trên trong đoạn [2,4].
B1: Trạng thái của 2 deque dmin và dmax đã có ở trong bảng
B2: Với k = 1, ta sẽ lấy phần tử đầu tiên của dmin ra, như vậy a[dmin.front()] = a[2] = 3 lúc này là phần tử nhỏ nhất của đoạn [x,4] với dmin[0] = 1 < x <= dmin[1] = 2. a[dmax.front()] = a[3] = 5 là phẩn tử lớn nhất của đoạn [x,4] với dmax[-1] = 0 < x <= dmax[0] = 3.

Code tham khảo:

Đây cũng là kỹ thuật để làm bài KDIFF trên SPOJ: http://vn.spoj.com/problems/KDIFF/

Happy coding 😀