You are not logged in. Please login at www.codechef.com to post your questions!

×

Same Solutions but different results

Hello Everyone, I came across the problem named CHOCPAIR. I tried to solve it but failed. I look at @tciitb's solution. My idea is the same as his. Still, my solution wasn't accepted. So I followed his code. But still, my code produces the wrong answer. Someone, Please help.

Problem Link : https://www.codechef.com/problems/CHOCPAIR

My solution : https://www.codechef.com/viewsolution/19853908

@tciitb's solution: https://www.codechef.com/viewsolution/19844048

asked 25 Aug '18, 18:32

ankush_953's gravatar image

4★ankush_953
657
accept rate: 8%


When you are accessing m[b] when b doesn't exist in the unordered map, it inserts that key with a value of 0. This insertion could cause iterator invalidation, and hence your loop goes for a toss.

Have a look at the "Iterator invalidation" section of https://en.cppreference.com/w/cpp/container/unordered_map

"insert, emplace, emplace_hint, operator[] - Only if causes rehash"

This is probably the issue.

link

answered 30 Aug '18, 20:36

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

I don't have much knowledge about C++, but you didn't check if the value 'b' is present in the set.
Checking it yields TLE (which can be removed by using 'printf' and 'scanf'). Most probably, 'getitem' returns a dump value if the key is not present in the set.

ACed solution: https://www.codechef.com/viewsolution/19854328
WA solution: https://www.codechef.com/viewsolution/19854334 (same code without the 'contains' check)

link

answered 25 Aug '18, 19:17

sarthakmanna's gravatar image

6★sarthakmanna
1.0k115
accept rate: 38%

edited 25 Aug '18, 19:17

Thank you for help :) but whenever an element is not present in the map, it returns zero so answer shouldn't have been affected by checking the presence of element at all.

(25 Aug '18, 21:44) ankush_9534★

You are not using reserve() function which is giving you wrong answer. Don't know much about performance of unordered map. But this might help
http://codeforces.com/blog/entry/21853
https://en.cppreference.com/w/cpp/container/unordered_map/reserve
your solution gives A/C with reserve()-
https://www.codechef.com/viewsolution/19854409

link

answered 25 Aug '18, 19:26

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

Thank you for help :) but the use of reserve and max_load_factor seems just optimization. Can you tell me What part did they play here?

(25 Aug '18, 21:40) ankush_9534★

@vijju123 please help with this issue...really confused about working of unordered_map in STL.

link

answered 27 Aug '18, 17:53

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

Okay, looking at it.

(27 Aug '18, 18:17) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×856
×303

question asked: 25 Aug '18, 18:32

question was seen: 203 times

last updated: 30 Aug '18, 20:36