DPR's blog

Codeforces Educational Round 1519 Problem-C Berland Regional
By DPR, history, 4 years ago, In English

If anyone who was able to solve the problem tell me where my approach could've been optimized.

I took a map and put all scores which belong to university i in an array and stored it in the map against key i.

Then, I sorted the array for every key in the map, and transformed the array into prefix sum array.

My observation was that, say for university i, if the size of array against key i is not entirely divisible by k (k : 1 to n), then we have to ignore first k%n elements (n = size of array against key i in map), this translates to substraction of prefix sum at index k % n — 1 from entire sum of all students.

So basically, after this, I looped over all k (1 to n) and over all map keys, to find sizes which are indivisible by k and performed above operation.

This essentially gave me a TLE on test case 5.

I'd be really grateful for any tips/ help as to where I could further optimize this.

Thanks a lot.

HERE'S MY CODE:

public static void solve(int n, int[] u, long[] s){

Map<Integer,ArrayList<Long>> mp = new HashMap<>();

for(int i = 0 ; i < n ; i++){
  if(mp.containsKey(u[i]-1)){
    mp.get(u[i]-1).add(s[i]);
  }
  else{
    ArrayList<Long> ls = new ArrayList<>();
    ls.add(s[i]);
    mp.put(u[i]-1,ls);
  }
}

for(int i : mp.keySet()){
  Collections.sort(mp.get(i));
}

Long ans = 0l;
for(int i : mp.keySet()){
    for(long k : mp.get(i)){
      ans += k;
    }
}

for(int i : mp.keySet()){
  ArrayList<Long> ls = mp.get(i);
  for(int j = 1 ; j < ls.size() ; j++){
    ls.set(j,ls.get(j) + ls.get(j-1));
  }
}

Map<Integer,ArrayList<Integer>> sizes = new HashMap<>();

for(int k : mp.keySet()){
  if(sizes.containsKey(mp.get(k).size())){
    sizes.get(mp.get(k).size()).add(k);
  }
  else{
    ArrayList<Integer> ls = new ArrayList<>();
    ls.add(k);
    sizes.put(mp.get(k).size(),ls);
  }
}

System.out.print(ans + " ");
for(int i = 2 ; i <= n ; i++){
  long f = ans;
  for(int j : sizes.keySet()){
    if(j % i != 0){
      for(int k : sizes.get(j)){
          f -= mp.get(k).get((j % i)-1);
        }
      }
    }
  System.out.print(f + " ");
}
System.out.println("");

}

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I also used the same approach and got tle on testcase 4

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Instead of creating loop of k from 1 to n, create an array sum[n] which store the answer for index k now loop over all universities, taking k from 1 to the size of its student vector (no of students in university). accordingly adding values to sum array. here k is not from 1 to n hence time complexity is reduced. Thanks

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think that taking k from 1 to size of its students reduces its complexity much, It becomes at most n*root(n). As, if the size of such universities is more than root(n), then their number will be less than root(n), so n*root(n) here and if the size of universities is less than root(n), then O(n) such universities can be there but k:1 to root(n) for such, so again n*root(n). So, overall complexity is n*root(n). The complexity might be less than this, but this was enough.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did the same thing, except I exited out of the loop and printed out all $$$0$$$'s for the rest of the numbers once one of the answers was a $$$0$$$. That passed in 200ms with C++.

→ Reply