CSS2 - Editorial

pkacprzak · October 26, 2014, 2:18pm

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:

achaitanyasai · October 26, 2014, 2:31pm

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

zeus07 · October 26, 2014, 2:33pm

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.

neo1tech9_7 · October 26, 2014, 2:36pm

strings will tle for the larger subtask use pair instead

tech_boy · October 26, 2014, 2:38pm

Nested Struct

Anyone can tell a alternative logic (without STL) ?

ideone

tech_boy · October 26, 2014, 2:42pm

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.

grayhathacker · October 26, 2014, 2:46pm

I also used vectors and pair STLs to do this…

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

hkbharath · October 26, 2014, 2:48pm

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

sunny210 · October 26, 2014, 2:49pm

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.

neo1tech9_7 · October 26, 2014, 2:50pm

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.

tech_boy · October 26, 2014, 2:52pm

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

rishabhprsd7 · October 26, 2014, 2:57pm

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

thechamp103 · October 26, 2014, 2:59pm

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

tech_boy · October 26, 2014, 3:06pm

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

-@thechamp103

kk_pheonix · October 26, 2014, 8:31pm

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)]<<"\n";
 }
 a.clear();
 b.clear();
 return 0;
}

Debanjan · October 26, 2014, 11:24pm

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

spoiler

abhishek_12 · October 27, 2014, 3:12pm

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.

dhruvi · November 29, 2014, 3:21pm

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

codopediac3 · January 24, 2015, 5:24pm

using structure, using stable_sort and binary search
[my solution][1]
using map and pair
[my solution][2]
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

lapmid258 · November 15, 2018, 2:15am

Someone Please provide a test case which fails my solution,
i have solved this but this solution is also correct according to me
This is Solution Link