naivedyam's blog

Why WA at test 8?
By naivedyam, history, 2 weeks ago, In English

My submission 290383236 for the problem 1234D - Distinct Characters Queries is giving a WA at test case 8. However the numbers differ at case 303 so I cant view that particular test case. I don't get what am I doing wrong as the logic seems fine to me (Segment trees are some real pain while debugging). Can someone help me out here?

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why would you use segtree for div3 D? :). I guess you know the approach but simply the idea should be to store the indices of occurence of characters (since there are only 26 of them). And then use binary search to check for all characters if character occurs between [l,r]

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I wasn't upsolving it as a contest I am currently learning and solving problems of segment tree that's why preferring to use it as much as possible (for learning purposes only) and I can't solve those 2000 rated ones yet so 1600 ones are comfortable to start from.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why WA at test 8?

Bcz its wrong

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's what I am asking what part of it is giving WA. Even knowing the particular test case where it gets WA would help a lot (I can't stress test yet)

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why on earth would you pass update(1,0,n-1,pos-1,c) when you already did take care of pos as 0-indexed in update function.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Test Case :

rfkqyuqf 10 1 6 y 1 4 n 2 1 2 1 8 r 2 1 6 2 4 7 1 8 v 1 1 l 1 2 p 2 4 6

Expected output : 2 5 3 2

Your output : 2 6 5 5

My submission for reference, even I used segment tree

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

in update function change pos — 1 to pos

(remove -1 from these line)

char original = arr[pos -1];

arr[pos -1] = val;

290406472 (updated code)

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! That helped a lot!

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This might be too silly of a question again but I made another submission implementing the same logic differently in 290449046. In the AC code we keep the pos as it is in update function and do call pos — 1 in main function. However here we are calling pos in main function and taking care of the indexing in the update function. Aren't both equivalent? Then why is the other one giving wa?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, Both are different because ur segment tree is 0 based indexed so every decision should be based on Zero based indexing and u are doing the same in ur updated submission while in ur first submission from main function u r sending a zero based indexing index so u should access it like main index in ur segment tree but ur first(WA) code will treat it as one based indexing when it is reaching at its base condition in update function. which is wrong. Just think that if u have to update index 0 then in ur first code (Which is giving WA) when it reaches to the base case then it will try to access index pos — 1 => 0 — 1 -> -1 Which will produce RE(Runtime Error).

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check my submission for correction.

→ Reply