सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

Sparse Grid (विरल ग्रिड)

ज़्यादातर खाली grid को सिर्फ़ उसके non-zero cells की list के रूप में रखिए और get, count, पंक्ति का योग और कॉलम हटाने वाले operations के जवाब दीजिए।

आप क्या सीखेंगे

  • सिर्फ़ non-zero cells को store करना
  • कॉलम खिसकने पर store की गई keys अपडेट करना
  • पूरा grid बनाए बिना सवालों के जवाब देना

समस्या

एक बहुत बड़े स्टेडियम का बैठने का चार्ट ज़्यादातर खाली है, इसलिए हर cell को store करना memory की बर्बादी है। SparseGrid सिर्फ़ उन cells को store करता है जिनमें non-zero मान है; बाकी हर cell 0 है। Grid की शुरुआत rows पंक्तियों, cols कॉलमों और बिना किसी store किए cell के होती है। इन operations को क्रम से process कीजिए:

  • set r c v: cell (r, c) का मान v हो जाता है। 0 set करने पर cell storage से हट जाता है।
  • get r c: cell (r, c) का मान आउटपुट कीजिए।
  • count: कितने cells non-zero हैं, यह आउटपुट कीजिए।
  • row_sum r: पंक्ति r के मानों का योग आउटपुट कीजिए।
  • width: कॉलमों की मौजूदा संख्या आउटपुट कीजिए।
  • remove_col c: कॉलम c हटा दीजिए। उसके cells गायब हो जाते हैं, उसके दाईं ओर का हर cell एक कॉलम बाईं ओर खिसक जाता है, और grid में एक कॉलम कम हो जाता है।

पंक्तियाँ और कॉलम 0 से गिने जाते हैं, और operation के समय हर index grid के अंदर होता है।

sparse_grid(rows, cols, operations) लिखिए।

इनपुट

rows: पंक्तियों की संख्या।

cols: कॉलमों की शुरुआती संख्या।

operations: operations, जिन्हें क्रम से process करना है।

आउटपुट

get, count, row_sum और width के आउटपुट उसी क्रम में लौटाइए जिसमें वे होते हैं।

सीमाएँ

1 ≤ rows ≤ 1,000,000

1 ≤ cols ≤ 1,000,000

0 ≤ operations की संख्या ≤ 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 है; तीन cells store हैं; (1, 1) कभी set नहीं हुआ, इसलिए वह 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 है, width 2 है और एक cell बचता है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

(पंक्ति, कॉलम) से मान वाला map अच्छा काम करता है; key न होने का मतलब 0 है।

संकेत 2

किसी cell को 0 set करने पर उसे हटा दीजिए ताकि `count` सही रहे।

संकेत 3

कॉलम हटाने पर map दोबारा बनाइए: उस कॉलम को हटाइए और उससे बड़े कॉलम नंबरों को एक कम कर दीजिए।

अपेक्षित जटिलता

समय O(q × s), अतिरिक्त स्थान O(s), s = store किए गए cells

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।