โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ตารางแบบเบาบาง (Sparse Grid)

เก็บตารางที่ส่วนใหญ่ว่างเปล่าไว้เป็นรายการของช่องที่ไม่เป็นศูนย์ แล้วตอบคำสั่ง get, count, ผลรวมแถว และการลบคอลัมน์

สิ่งที่คุณจะได้เรียนรู้

  • เก็บเฉพาะช่องที่ไม่เป็นศูนย์
  • อัปเดตคีย์ที่เก็บไว้เมื่อคอลัมน์เลื่อน
  • ตอบคำถามโดยไม่ต้องสร้างตารางเต็ม

โจทย์

ผังที่นั่งของสนามกีฬาขนาดใหญ่มากส่วนใหญ่ว่างเปล่า การเก็บทุกช่องจึงเปลืองหน่วยความจำ SparseGrid เก็บเฉพาะช่องที่มีค่าไม่เป็นศูนย์ ส่วนช่องอื่นทั้งหมดมีค่าเป็น 0 ตารางเริ่มต้นด้วย rows แถว cols คอลัมน์ และยังไม่มีช่องใดถูกเก็บไว้ ให้ประมวลผลคำสั่งต่อไปนี้ตามลำดับ

  • set r c v: ช่อง (r, c) มีค่าเป็น v การตั้งค่าเป็น 0 จะลบช่องนั้นออกจากที่เก็บ
  • get r c: แสดงค่าของช่อง (r, c)
  • count: แสดงจำนวนช่องที่ไม่เป็นศูนย์
  • row_sum r: แสดงผลรวมของค่าในแถว r
  • width: แสดงจำนวนคอลัมน์ในปัจจุบัน
  • remove_col c: ลบคอลัมน์ c ช่องในคอลัมน์นั้นหายไป ทุกช่องทางขวาของมันเลื่อนไปทางซ้ายหนึ่งคอลัมน์ และตารางมีคอลัมน์ลดลงหนึ่งคอลัมน์

แถวและคอลัมน์นับเริ่มจาก 0 และทุกดัชนีอยู่ภายในตาราง ณ เวลาที่ทำคำสั่งนั้น

จงเขียน sparse_grid(rows, cols, operations)

อินพุต

rows: จำนวนแถว

cols: จำนวนคอลัมน์เริ่มต้น

operations: คำสั่งต่าง ๆ ซึ่งประมวลผลตามลำดับ

เอาต์พุต

คืนค่าผลลัพธ์ของ get, count, row_sum และ width ตามลำดับที่เกิดขึ้น

เงื่อนไข

1 ≤ rows ≤ 1,000,000

1 ≤ cols ≤ 1,000,000

0 ≤ จำนวนคำสั่ง ≤ 1,000

−1,000,000 ≤ v ≤ 1,000,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]

ผลลัพธ์ที่คาดหวัง:
expected = [7, 3, 0]
อินพุต:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {7, 3, 0};
อินพุต:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {7, 3, 0};

คำอธิบาย

แถว 0 มี 5 และ 2 ผลรวมจึงเป็น 7 มีช่องที่เก็บไว้สามช่อง และ (1, 1) ไม่เคยถูกตั้งค่า จึงเป็น 0

ตัวอย่างที่ 2
อินพุต:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]

ผลลัพธ์ที่คาดหวัง:
expected = [9, 2, 1]
อินพุต:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {9, 2, 1};
อินพุต:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {9, 2, 1};

คำอธิบาย

การลบคอลัมน์ 0 ทำให้ 4 หายไป และ 9 จากคอลัมน์ 2 เลื่อนมาอยู่คอลัมน์ 1 ดังนั้น get 1 1 ได้ 9 ความกว้างเป็น 2 และเหลือหนึ่งช่อง

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ใช้ map ที่จับคู่ (แถว, คอลัมน์) กับค่าได้ดี ถ้าไม่มีคีย์นั้นแปลว่าเป็น 0

คำใบ้ 2

การตั้งค่าช่องเป็น 0 ควรลบช่องนั้นทิ้ง เพื่อให้ `count` ถูกต้อง

คำใบ้ 3

เมื่อลบคอลัมน์ ให้สร้าง map ใหม่ โดยทิ้งคอลัมน์นั้นและลดหมายเลขคอลัมน์ที่มากกว่าลงหนึ่ง

ความซับซ้อนที่คาดหวัง

เวลา O(q × s), หน่วยความจำเพิ่ม O(s) โดย s คือจำนวนช่องที่เก็บไว้

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก