CSS2 - Editorial

easy
editorial
hash-map
ltime17

#1

PROBLEM LINK:

Practice
Contest

Author: Piyush Kumar
Tester: Minako Kojima
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

Ad hoc, Hash table

PROBLEM:

You are given N command in the following form: id, attr, val, priority. A single command C means that you have to assign the value val to attribute attr of the object with the identifier id if and only if there is no other command assigning to the same attribute of the same object with higher priority than C or with the same priority as C but listed after C in the list of commands.

After that, there are M queries of form: id, attr. Your task is to print for each of these queries the value of attribute attr of object with the identifier id.

QUICK EXPLANATION:

You can store values of attributes of objects in an array of hash tables and iterate over the list of command to build and update these hash tables. After that, you can iterate over the list of queries and answer them based on data in the array.

EXPLANATION:

You can use an array of hash tables h, where h[id] is a hash table representing attributes of the object with identifier id. Since 1 <= id <= 10^6 you can allocate the whole array at first. A single record in the hash table of object with identifier id h[id][attr] is a pair (val, priority) representing the value of attribute attr of the object and the priority of command which assigned the value.

You can read more about hash tables here

You can iterate over the list of all commands and update the hash tables.

for(i = 0; i < n; ++i)
    read id, attr, val, priority
    if(!h[id][attr] or h[id][attr].priority <= priority)
        h[id][attr].value = val
        h[id][attr].priority = priority

After that you can just iterate over all queries and print answers based on data stored in the hash table.

for(i = 0; i < m; ++i)
    read id, attr
    print h[id][attr]

Complexity

If you use a hash table, then the time complexity is O(n), because we do only O(n) lookups and writes in it. You can also use a tree-base structure like a map in c++, for which the total complexity will be O(n log n) because a single lookup or insert into map consts O(log n). Most languages have their own implementation of a hash table. Not everyone knows that c++ also has it and it is called unordered_map.

Alternative Solution:

For a partial credit, you can use a simple two dimmensional array h[id][attr] and follow the same algorithm. It can be used to solve the problem with lower constraints.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:


#2

We can also do this with C++ map and pair … Here is the link : http://www.codechef.com/viewsolution/5223210


#3

This question can be very easily solved by using the map data structure in c++. Where we combine the object and the attributes to form a string Say s.

Then we create 2 maps mv ( map for value ) & mp ( map for priority ) which will map a string to an integer value.

mv[s]=v (value)
mp[s]=p (priority)

Then applying the algo:

Take the inputs

String s=object+"-"+attributes

if mv[s] doest not exist

 mv[s]=v
 mp[s]=p

else

 if p>=mp[s]

      mp[s]=p
      mv[s]=v

then for each of the m queries we create their string and find the value in the map.


#4

Nested Struct

Anyone can tell a alternative logic (without STL) ?

ideone


#5

Can anyone please tell me the logic of this problem in c in order to obtain full score without using structure ? ?


#6

i used the following logic with the help of maps… but got a WA though it gives correct answwer with given test cases…

what is it that i am missing ?

#include<bits/stdc++.h>
using namespace std;
long long int a[1005]={0};
long long int b[1005][1005]={0,0};
int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 // a- priority list
 // b- value list for an id and attribute
 map <int,int> a;
 map <pair<int,int>,int > b;
 long long int n,m,id,at,val,pr,i;
 cin>>n>>m;
 for(i=0;i<n;i++)
 {
  cin>>id>>at>>val>>pr;
  if(a.find(id)==a.end())
  {
   a[id]=pr;
   b.insert(make_pair(make_pair(id,at),val));
  }
  else
  {
   if(pr>=a[id])
   {
    a.erase(id);
    a[id]=pr;
    b.erase(make_pair(id,at));
    b.insert(make_pair(make_pair(id,at),val));
   }
  }
 }
 for(i=0;i<m;i++)
 {
  cin>>id>>at;
  cout<<b[make_pair(id,at)]<<"

";
}
a.clear();
b.clear();
return 0;
}


#7

This is somewhat trivial if you are aware of C++ Multimap.

spoiler


#8

I just used a structure with id, att, val, priority and count as its members, and used a simple sorting comparator to sort it according to need, and finally using binary search to retrieve val. The problem is it gives me full marks for 30 pts. and 50 pts. but 0 for 20 pts., which is the easiest bound of 10^3.
Here is my solution : http://www.codechef.com/viewsolution/5229098

I can’t figure out, how it leads to correct submission for the tougher bounds and wrong for the easier ones.


#9

here is my simple c program which fetch me full marks
I used just a simple structure and sorted it according to the demand using quick sort which is inbuilt function in stdlib
just I played with sort_fun to accomplish the demand of the question
here u can can see my solution

www.codechef.com/viewsolution/5260080


#10
  1. using structure, using stable_sort and binary search
    [my solution][1]
  2. using map and pair
    [my solution][2]
  3. using unordered_map and pair (slower)
    [my solution][3]

if there is any other solution … ping me …
[1]: http://www.codechef.com/viewsolution/5975298
[2]: http://www.codechef.com/viewsolution/5975502
[3]: http://www.codechef.com/viewsolution/5975549


#12

strings will tle for the larger subtask use pair instead


#13

Weak Testcases for 30 points as it was having same id with different attributes which passed the cases for me though i did not link it with ID.


#14

I also used vectors and pair STLs to do this…

link : http://www.codechef.com/viewsolution/5224283


#15

its not possible to store array of size 106x106, its too large, its around 3.2x1013 bits that is around 32 Terabyte… i never heard of system that has 32 TB RAM :stuck_out_tongue: . But for CSS2 problem such a big array is not required. You can use hashing technique as explained in editorials above


#16

In the structure definition you are equivalently declaring an array similar to A[size][size] where size=1000001 which is not possible and gives segmentation fault.


#17

you have an array of size 10^6 in your struct and you are making an array of that struct of size 10^6. total space = 10^12 will not work.


#18

Yeah i am aware about it i want alternative logic as i am not known to STL


#19

you can do it using sorting and binary search.
Here’s my solution:
http://www.codechef.com/viewsolution/5225187


#20

you can do it using sorting and binary search. Here’s solution: http://www.codechef.com/viewsolution/5225187

-@thechamp103