1

I tried the following code but i am not able to find the error. The error is in the loop section but I can not figure out that how to correctly use the iterator in order to avoid the errors. Please help and please clarify my concepts. The problem statement is https://codeforces.com/contest/268/problem/A. I have solved it via vector

    int main()
    {
        std::ios::sync_with_stdio(false);
        int n,x,y,count=0; cin>>n;
        std::vector<pair<int,int>> v;
        for (int i = 0; i < n; ++i)
        {
            cin>>x>>y;
            v.push_back(make_pair(x,y));
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j=i+1; j < n; ++j)
            {
                if(v[i].f==v[j].s){
                    count++;
                }
                if(v[i].s==v[j].f){
                    count++;
                }
            }
        }
        cout<<count;


        return 0;
    }

but having problem via map. It gives SIGTSTP error when using map.

#include <iostream>
#include <map>

using std::cin;
using std::cout;
using std::make_pair;

int main() {
  std::ios::sync_with_stdio(false);
  int n, x, y, count = 0;
  cin >> n;
  std::map<int, int> m;
  for (int i = 0; i < n; ++i) {
    cin >> x >> y;
    m.insert(make_pair(x, y));
  }

  for (auto i = m.begin(); i != m.end(); ++i) {
    for (auto j = ++i; j != m.end(); ++j) {
      if (i->first == j->second) {
        count++;
      }
      if (i->second == j->first) {
        count++;
      }
    }
  }
  cout << count;
  return 0;
}
tempmail 102
  • 23
  • 3
  • 4
    What is the error? Please add any error message or unexpected output (with corresponding input) to your question. Click [edit] to do so. – walnut Dec 26 '19 at 13:09
  • 4
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/a/25385174/5910058) – Jesper Juhl Dec 26 '19 at 13:12
  • What's the purpose of the program? – tigertang Dec 26 '19 at 13:13
  • 3
    You're double-incrementing `i`. I mean, `++i` will always execute after each *outer* loop iteration, *and* on each inner loop initial setup.That means you can eventually land `i` on `m.end()` with the inner-loop init, *then* attempt to bump it further on the increment step of the next outer-loop iteration (which happens *before* the comparison test), That bump-past-end invokes UB. I *suspect* changing the inner-loop init setup to `auto j = std::next(i)` will do what you seek, but without explaining the overall purpose of your code, that's a complete crystal-ball guess. – WhozCraig Dec 26 '19 at 13:13
  • I have added the relevant information, please check and help. – tempmail 102 Dec 26 '19 at 13:21
  • The edit section has become so weird now. ;P – tigertang Dec 26 '19 at 13:25

2 Answers2

2

You cannot use map data structure for this problem because map store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have same key values.
But according to the question, the key values can be same, so thats why you cannot use map here.
For more details you can see http://www.cplusplus.com/reference/map/map/

shubhgkr
  • 471
  • 2
  • 7
  • Using multimap and std::next(i,1) in the loop solved the problem. Can anyone tell that when solving these type of problems, what should we be using vector> or map/multimap? – tempmail 102 Dec 26 '19 at 14:50
  • If it is guaranteed that the key of the map is unique then use map otherwise vector. – shubhgkr Dec 26 '19 at 14:54
0

Here's my answer:

#include <iostream>
#include <map>

const int N = 50;

int h[N], a[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", h + i, a + i);
  }

  int ans = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j) {
        if (h[i] == a[j]) ans++;
      }
  printf("%d\n", ans);
  return 0;
}

The answer to the problem is sigma { h[i] = a[j] } (i != j).

Your code has made these mistakes:

  1. std::map::insert means set certain key to certain value. Plus, std::map is different from std::multimap. The latter allows the existence multiple same keys while the former doesn't.

  2. You shouldn't just make the starting point of j as i + 1 since the iteration range should be [0, i - 1] union [i + 1, n - 1] (edit: your code's logic is right as well).

  3. Iterator cannot be so rashly self incremented because it has side effects as the comment section points out.

tigertang
  • 445
  • 1
  • 6
  • 18
  • When solving these type of problems, what should we be using vector> or map/multimap or something else? – tempmail 102 Dec 26 '19 at 14:56
  • A normal array is sufficient for many cases. Use `std::vector` when you need features like `push_back`. – tigertang Dec 26 '19 at 14:57
  • Algo contest is all about quick and correct answers. So don't use techniques that make no boost to the answer and drag your coding speed (just like the additional log N that `std::map`/`std::multimap` takes). – tigertang Dec 26 '19 at 15:03