Unacademy Hiring challenge [Debugging - Cpp - Q2]

help
, ,
44

In the last loop we should iterate over rev_graph instead of graph which was also mistake

45

congrachulashunz

2 Likes
46

I did it using Segment Tree.First I made a query for the max quality index first and then an update operation for that index if it is valid.


pair<pii, int>  v[4 * N];
pii val[N];
int len, x, y, w, z, qt, th, ans, pass;

void build(int id, int cx, int cy)
{
  if (cx == cy)
  {
    v[id] = {val[cx], cx};
    return;
  }

  int mid = (cx + cy) / 2;

  build(2 * id, cx, mid);
  build(2 * id + 1, mid + 1, cy);

  x = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);

  if (x == v[2 * id].ff.ff) v[id] = v[2 * id];
  else v[id] = v[2 * id + 1];
}

void update(int id, int cx, int cy)
{
  if (x < cx or x > cy) return;

  if (cx == cy and x == cx)
  {
    val[cx].ss += w;
    v[id] = {val[cx], cx};
    return;
  }

  int mid = (cx + cy) / 2;

  update(2 * id, cx, mid);
  update(2 * id + 1, mid + 1, cy);

  z = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);

  if (z == v[2 * id].ff.ff) v[id] = v[2 * id];
  else v[id] = v[2 * id + 1];
}

int query_id(int id, int cx, int cy)
{
  if (y < cx or x > cy) return -1;

  if (x <= cx and cy <= y) return v[id].ss;

  int mid = (cx + cy) / 2;

  int left = -1, right = -1;

  left = query_id(2 * id, cx, mid);
  right = query_id(2 * id + 1, mid + 1, cy);

  int ans = -1;

  if (left != -1) ans = left;
  if (right != -1)
  {
    if (left == -1) ans = right;
    else if (val[left].ff < val[right].ff) ans = right;
  }

  return ans;
}

// remember to decrease the quantity

void query_update(int id, int cx, int cy)
{
  if (x < cx or x > cy) return;

  if (cx == cy and x == cx)
  {
    val[cx].ss -= qt;
    v[id] = {val[cx], cx};
    return;
  }

  int mid = (cx + cy) / 2;

  query_update(2 * id, cx, mid);
  query_update(2 * id + 1, mid + 1, cy);

  z = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);

  if (z == v[2 * id].ff.ff) v[id] = v[2 * id];
  else v[id] = v[2 * id + 1];
}



void solve()
{
  fo(i, 0, 4 * N - 1) v[i] = {{0, 0}, -1};

  int n, q;
  cin >> n >> q;

  fo(i, 0, n - 1) cin >> val[i].ff;
  fo(i, 0, n - 1) cin >> val[i].ss;

  build(1, 0, n - 1);

  while (q--)
  {
    cin >> z;

    if (z == 1)
    {
      cin >> x >> y >> w;
      x--, y--;

      x = query_id(1, 0, n - 1);
      update(1, 0, n - 1);
    }
    else
    {
      cin >> len >> z >> qt >> th;
      z--;
      x = max(0LL,   z - len);
      y = min(n - 1, z + len);


      x = query_id(1, 0, n - 1);

      if (val[x].ff < th or val[x].ss < qt) cout << "No purchase\n";
      else
      {
        query_update(1, 0, n - 1);
        x++;
        cout << x << endl;
      }
    }
  }
}
48

:sob: ā€œSubmission #87803103 - Codeforcesā€ solved in one go in CF and here I m unable to solve :frowning:

49

Hereā€™s the problem. I just solved this problem yesterday. Copy pasted my code with minor changes and got 92%. Didnā€™t bother to debug for 100. :stuck_out_tongue:

50

Initially I write the code in Python and I got 82% and then I wrote the same code in cpp, it gave me 100%

51

they invited me too!!

52

Can anyone say when will the results be published?Also anyone did 700 score???

53

Since your highest rating is >= 1800

54

ohhhhhhhhhhā€¦sad. my highest is 3 star :confused:

55

Basically we store a map < quality, index> and any data structure to answer range max query.
Now for query 1
Find max in given range
Use map to get its index
Update the quantity at that index

For query 2
Find max in range
Find its index using map
Now if the quality is not less than threshold and quantity is also not less than required
Make purchase, reduce quantity at this index
Else say, No purchase.

56

Yup, I scored 700 :slight_smile:

3 Likes
57

Congratulationsā€¦Actually I have just started learning java so i wasnā€™t able to do thatā€¦

58

I got left by 2 pointsā€¦AHHH
should have given Lunchtime. :ā€™(

59

anyone has done debugging java ? what was the problem in that code? is it Multiplication overflow ?

60

Exchange min and max, and change N to long to prevent overflow.

import java.util.*;
import java.io.*;
class Solution{
	static long find_cost(long N, int hcost, int vcost){
		long res = N*(N-1);
		res *= Math.min(hcost,vcost);
		long temp = (N-1)*(Math.max(hcost,vcost));
		return res + temp;
	}
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		while(T-- > 0){
			int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			int N = arr[0];
			int Ch = arr[1];
			int Cv = arr[2];
			System.out.println(find_cost(N, Ch, Cv));
		}
	}
}
61

algorithm for minimum removal of edges so that no cycle ?

62

i got only 40 pts by doing this
how many pts did you got??

63

and i thought 486 is a good score :frowning:

64

Same happened with me,I got the verdict before contest was finished but my score didnā€™t update.