naivedyam's blog

Why WA at test 8?
By naivedyam, history, 4 hours 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
  • -17
  • Vote: I do not like it

»
4 hours 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
  • »
    »
    4 hours 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
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why WA at test 8?

Bcz its wrong

→ Reply
  • »
    »
    3 hours 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 hours 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
»
111 minutes 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
»
101 minute(s) ago, # |
← Rev. 2   Vote: I like it +2 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
»
77 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Check my submission for correction.

→ Reply