I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.
Thank you in advance.
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.
Thank you in advance.
I was hoping that there's a greedy for the full solution since constraints seemed too big for dp. But looking at submissions from oj.uz there seems to be a dp solution. On greedy, i tried to always use the shop with highest money and failed.
Jack and Jill play a game called Hotter, Colder. Jill has a number between 1 and N, and Jack makes repeated attempts to guess it.
Each of Jack's guesses is a number between 1 and N. In response to each guess, Jill answers hotter, colder or same. For Jack's first guess, Jill answers same. For the remaining guesses Jill answers:
hotter if this guess is closer to Jill's number than his previous guess colder if this guess is farther from Jill's number than his previous guess same if this guess is neither closer to nor further from Jill's number than his previous guess. You are to implement a procedure HC(N) that plays Jack's role. This implementation may repeatedly call Guess(G), with G a number between 1 and N. Guess(G) will return 1 to indicate hotter, -1 to indicate colder or 0 to indicate same. HC(N) must return Jill's number.
Today I wrote a solution for IOI 2010 Traffic
But It exceeds the memory limit.
#include <bits/stdc++.h>
#include "traffic.h"
#define pb push_back
using namespace std;
vector<vector<int>> adj(1000000,vector<int>());
map<pair<int,int>,int> m;
int dp(int p,int c,int* P){
if(m.find((pair<int,int>){p,c})!=m.end())return m[(pair<int,int>){p,c}];
int ans = P[c];
for(int v:adj[c]){
if(v==p)continue;
ans += dp(c,v,P);
}
m.insert({{p,c},ans});
return ans;
}
int LocateCentre(int n,int p[],int s[],int d[]){
for(int i=0;i<n-1;i++){
adj.at(s[i]).pb(d[i]);
adj.at(d[i]).pb(s[i]);
}
int ans = INT_MAX,index = -1;
for(int i=0;i<n;i++){
int local = INT_MIN;
for(int v:adj[i])local = max(local,dp(i,v,p));
if(local<ans){
ans = local;
index = i;
}
}
return index;
}
Graph is a tree and has $$$n$$$ $$$(<1e6)$$$ nodes. Therefore i think the total memory will be
$$$n$$$ for array p
$$$n$$$ each for s
and d
arrays
$$$2*(n-1)$$$ for adjacency vector
$$$2*(n-1)$$$ for map m
Complexity is $$$O(n)$$$
But how does this exceeds 250MB? Can someone point me to my mistake.
Thank you.
Here's the list of IOI problems from 2006 sorted by their difficulty (average score)
2010 Memory 93.19
2010 Cluedo 92.69
2009 Garage 91.55
2009 Poi 90.05
2006 Deciphering the Mayan Writing 80.62
2020 Connecting Supertrees 77.93
2010 Traffic Congestion 75.91
2019 Arranging Shoes 74.47
2018 Combo 74.12
2009 Raisins 70.55
2007 Miners 68.31
2016 Detecting Molecules 66.02
2013 Cave 64.39
2014 Gondola 64.26
2016 Paint by Number 63.6
2011 Parrots 59.9
2011 Ricehub 56.88
2010 Hotter Colder 55.23
2011 Crocodile 55.15
2017 The Big Prize 54.27
2008 Type Printer 53.78
2019 Vision Program 53.44
2012 Crayfish Scrivener 51.7
2010 Quality of Living 51.3
2020 Stations 51.27
2015 Horses 50.57
2020 Counting Mushrooms 49.65
2008 Linear Garden 47.6
2015 Sorting 47.07
2009 Mecho 46.09
2006 Pyramid 45.93
2007 Aliens 45.92
2015 Boxes with Souvenirs 44.32
2013 Robots 43.53
2010 Maze 42.75
2007 Pairs 42.26
2016 Unscrambling a Messy Bug 42.16
2013 Dreaming 41.15
2019 Broken Line 41.05
2011 Tropical Garden 40.62
2010 Languages 40.08
2014 Wall 39.76
2006 The Valley of Mexico 39.26
2015 Scales 37.51
2019 Rectangles 36.92
2014 Game 36.57
2017 Nowruz 34.51
2014 Friend 33.36
2010 Saveit 33.22
2014 Rail 32.71
2013 Art Class 32.48
2018 Mechanical Doll 31.54
2012 Ideal City 31.39
2018 Werewolf 30.6
2020 Carnival Tickets 29.6
2012 Pebbling Odometer 29.52
2013 Wombats 29.42
2009 Hiring 28.86
2013 Game 28
2019 Split the Attractions 26.63
2011 Elephants 26.54
2017 Wiring 26.4
2017 Ancient Books 26.21
2006 Forbidden Subgraph 26.15
2012 Jousting Tournament 26.1
2011 Race 25.85
2016 Roller Coaster Railroad 25.53
2020 Packing Biscuits 22.85
2014 Holiday 22.7
2015 Teams 22.62
2009 Salesman 22.42
2018 Meetings 21.71
2007 Flood 20.65
2007 Sails 19.73
2006 A Black Box Game 19.11
2012 Parachute Rings 18.47
2017 Simurgh 18.4
2016 Shortcut 18.35
2016 Aliens 17.86
2008 Islands 17.11
2018 Highway Tolls 15.66
2009 Regions 15.06
2020 Comparing Plants 14.54
2008 Teleporters 14.53
2018 Seats 14.33
2015 Towns 13.42
2019 Sky Walking 12.69
2012 Last Supper 12.5
2009 Archery 11.37
2017 Toy Train 10.43
2008 Pyramid Base 9.82
2006 Joining Points 8
2007 Training 5.31
2008 Fish 3.02
Here's the average score for a single problem per year
Another useful thing will be to classify problems by tags. But i don't think i'm qualified enough to tag problems. So i prepared a google forms so others can contribute. If it doesn't becomes successful i'll try to do it myself and share :D .
Note: Form is only for a single problem. You can submit another responses again. Please don't spam or provide fake tags.
This is my code to solve 229B - Планеты
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline void io(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int MAX_SIZE = 1e5+1;
vector<vector<pair<int,int>>> adjList(MAX_SIZE,vector<pair<int,int>>());
vector<map<int,int>> trav(MAX_SIZE,map<int,int>());
ll d[MAX_SIZE];
long long dijsktra(int n){
int src = 1,dest = n;
for(int i=0;i<=n;i++)d[i] = INT_MAX;
d[src] = 0;
priority_queue<pair<int,int>> q;
q.push({0,src});
while(!q.empty()){
int v = q.top().second;
int dis = q.top().first*-1;
q.pop();
if(v==n)return dis;
if(d[v]<dis)continue;
for(auto e : adjList[v]){
int to = e.first;
int len = e.second;
int t = d[v];
while(trav[v].find(t)!=trav[v].end())t++;
t+=len;
if(t < d[to]){
// q.erase({d[to],to});
d[to] = t;
q.push({-d[to],to});
}
}
}
if(d[n]==INT_MAX)d[n]=-1;
return d[n];
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
adjList.at(a).push_back({b,c});
adjList.at(b).push_back({a,c});
}
for(int i=0;i<n;i++){
int k;
scanf("%d",&k);
while(k--){
int t;
scanf("%d",&t);
trav.at(i+1).insert({t,1});
}
}
printf("%d\n",dijsktra(n));
}
But it get TLE on test 66. It's just a dijsktra with a simple modification. I can't figure out a way to make this any more faster.
Here's another code i found from top of the standings. It's almost the same as mine but passes in a very small time. I've been comparing two codes but have no idea for a reason for TLE.
Can someone help me figure out the problem?
Thank you.
I've been trying to solve this problem for few days now but can't think of a solution.
Here's the statement,
In case you need to read the full statement: Problem Link
What I observed so far:
worst case is in the form of $$$a^{1} , a^{2} , a^{3} , ... $$$ for some integer $$$a > 1$$$
in the worst case $$$i$$$ th element has $$$i-1$$$ in degree and $$$n-i$$$ out degree (1 based indexing)
That's all :(
I can't even prove that there's a solution for the worst case. Can someone help me solve this?
Thank you in advance
Name |
---|