Square Root Decomposition approach for a CodeChef question - Subsegment Sum(SEGSM) gives WA
up vote
-1
down vote
favorite
Can anyone please go through my code and provide any insight on what my mistake is? You can see the question on https://www.codechef.com/problems/SEGSM and my solution is https://www.ideone.com/nJap4V.
Basic pseudo code of the solution is as follows:
applyCompression()
buildBlocks()
calculateFreq()
for (int i = 1; i <= q; ++i)
if (queries[i].type == 1)
reduceFrequency(elements[queries[i].idx])
elements[queries[i].idx] = queries[i].v
increaseFrequency(queries[i].v)
else print freq_sum
I've named the functions meaningfully so understanding the flow should be quite easy as well. In brief, I've employed value compression to bring the range of numbers to a manageable state and used square root decomposition to calculate the frequency sum. Any help would be much appreciated.
c++ compression square-root
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
add a comment |
up vote
-1
down vote
favorite
Can anyone please go through my code and provide any insight on what my mistake is? You can see the question on https://www.codechef.com/problems/SEGSM and my solution is https://www.ideone.com/nJap4V.
Basic pseudo code of the solution is as follows:
applyCompression()
buildBlocks()
calculateFreq()
for (int i = 1; i <= q; ++i)
if (queries[i].type == 1)
reduceFrequency(elements[queries[i].idx])
elements[queries[i].idx] = queries[i].v
increaseFrequency(queries[i].v)
else print freq_sum
I've named the functions meaningfully so understanding the flow should be quite easy as well. In brief, I've employed value compression to bring the range of numbers to a manageable state and used square root decomposition to calculate the frequency sum. Any help would be much appreciated.
c++ compression square-root
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Can anyone please go through my code and provide any insight on what my mistake is? You can see the question on https://www.codechef.com/problems/SEGSM and my solution is https://www.ideone.com/nJap4V.
Basic pseudo code of the solution is as follows:
applyCompression()
buildBlocks()
calculateFreq()
for (int i = 1; i <= q; ++i)
if (queries[i].type == 1)
reduceFrequency(elements[queries[i].idx])
elements[queries[i].idx] = queries[i].v
increaseFrequency(queries[i].v)
else print freq_sum
I've named the functions meaningfully so understanding the flow should be quite easy as well. In brief, I've employed value compression to bring the range of numbers to a manageable state and used square root decomposition to calculate the frequency sum. Any help would be much appreciated.
c++ compression square-root
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
Can anyone please go through my code and provide any insight on what my mistake is? You can see the question on https://www.codechef.com/problems/SEGSM and my solution is https://www.ideone.com/nJap4V.
Basic pseudo code of the solution is as follows:
applyCompression()
buildBlocks()
calculateFreq()
for (int i = 1; i <= q; ++i)
if (queries[i].type == 1)
reduceFrequency(elements[queries[i].idx])
elements[queries[i].idx] = queries[i].v
increaseFrequency(queries[i].v)
else print freq_sum
I've named the functions meaningfully so understanding the flow should be quite easy as well. In brief, I've employed value compression to bring the range of numbers to a manageable state and used square root decomposition to calculate the frequency sum. Any help would be much appreciated.
c++ compression square-root
c++ compression square-root
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
edited Nov 10 at 21:54
Roman Pokrovskij
4,17654178
4,17654178
asked Nov 10 at 21:07
Surya Kumar
42
asked Nov 10 at 21:07
Surya Kumar
42
asked Nov 10 at 21:07
Surya Kumar
42
42
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53243411%2fsquare-root-decomposition-approach-for-a-codechef-question-subsegment-sumsegs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
