Tävlingsprogrammering/Uppgifter/Grodor
Grodor
N stycken grodor står i kö för att se en föreställning. Eftersom det är tråkigt att vänta fördriver de tiden med att göra något av följande:
- Grodan på position A hoppar över B grodor till vänster om sig, eller
- Grodan på position A hoppar över B grodor till höger om sig.
Alla grodor är inte lika långa. När en groda hoppar måste han se till att hoppa tillräckligt högt så att den inte slår i någon av grodorna den hoppar över. Det räcker med att han hoppar precis så högt som längden på den groda som är längst av de han hoppar över.
Givet en sekvens av hopp, skriv ut hur högt varje hopp minst måste vara.
Indata
Första raden innehåller två heltal N och H (2 ≤ N ≤ 100 000, 1 ≤ H ≤ 100 000), antalet grodor och antalet hopp.
Den andra raden innehåller N heltal mindre än 100 000 som motsvarar längden på grodorna så som de är uppradade från början (den första grodan har position 1, osv).
De följande H raderna beskriver ett hopp. Varje rad innehåller ett heltal A (1 ≤ A ≤ N), den aktuella positionen för den groda som ska hoppa, hoppriktningen ('V' för vänster, 'H' för höger), och ett heltal B (1 ≤ B ≤ N), antalet grodor den hoppar över. Alla hopp i indata kommer vara giltiga (dvs, det kommer finnas minst B grodor att hoppa över i den angivna riktningen).
Hoppen är givna i den ordning som grodorna gör dem.
Utdata
Skriv ut H rader med höjden för respektive hopp, i den ordning de utfördes.
Bedömning
I 20% av testfallen är N ≤ 25000 och H ≤ 25000.
Exempel 1: Indata
9 3 5 3 7 4 9 3 8 4 2 2 H 3 8 V 2 5 H 2
Exempel 1: Utdata
9 8 4
Förklaring: I det första hoppet hoppar grodan med längden 3 över de med längd 7, 4 och 9. I det andra hoppet hoppas grodorna med längd 3 och 8 över. I det sista hoppet är längderna 3 och 4.
Exempel 2: Indata
15 14 6 15 17 1 11 15 3 6 19 16 3 13 2 6 4 8 H 7 7 V 5 2 V 1 4 H 4 5 H 10 13 V 5 7 H 6 11 V 1 7 H 2 13 V 10 12 V 11 13 H 2 3 V 2 13 V 9
Exempel 2: Utdata
19 17 6 19 19 16 16 13 16 19 19 11 13 19
Lösning[redigera]
Bra[redigera]
Detta var, i mitt tycke, den klart svåraste uppgiften i KATT-1 att få full poäng på. Eftersom antalet grodor och hopp kan vara väldigt många, så ger en enkel simuleringslösning inte många poäng. Raden över grodor måste hanteras på ett smartare sätt så att vi inte behöver betrakta alla grodor i varje hopp.
Ett sätt att göra det på är att splitta upp raden i K block så att varje block innehåller ungefär N/K grodor. Inom varje block håller vi koll på ordningen med en länkad lista, och lagrar deras längd i en prioritetskö. Med dessa datastrukturer kan vi behandla hoppen snabbare:
- De två block som grodan börjar sitt hopp i och slutar sitt hopp i behandlas med enkel simulering. Komplexiteten för det är O(N/K).
- De block som grodan hoppar över helt behandlas på följande sätt. Vi kollar först vilket värde som ligger först på prioritetskön (den längsta grodan i det blocket). Grodan i ena änden av blocket flyttas till föregående block, och i den andra ändan flyttar vi en groda från nästa block. Prioritetsköerna i de påverkade blocken måste förstås också uppdateras. Komplexiteten för detta steg är O(K log N/K) om vi använder en heap som för att lagra prioritetskön. Den total komplexiteten för ett hopp blir O(N/K + K log N/K). Värdet på K väljer vi på ett sådant sätt att konstantfaktorn i algoritmen blir så liten som möjligt. I den officiella lösningen sattes den till 100.
Bättre[redigera]
Det finns ett annat sätt att dela upp blocken på. Istället för att alla block alltid har samma storlek kan man göra så att det finns "plats" för fler grodor i blocken. Antag t.ex. att man från början har 300 grodor i varje block men det finns plats för 4800. Då kan vi även lagra den groda som har störst längd i var och ett av blocken. På så vis kan vi, vid varje hopp, snabbt hoppa över alla blocken och samtidigt kolla högsta grod-längd-värdet. Det som då tar cpu-tid är att plocka ur grodan ur start-blocket och lägga in den i slut-blocket, och uppdatera värdena där för grodan med störst längd. Vi behöver då inte heller använda en länkad lista utan det fungerar bra med en vanlig array, eller en std::vector om man inte orkar implementera egna insert och erase-funktioner. Om nu ett block blir fullt (kommer inträffa max vart 4500:e hopp), kan vi helt enkelt organisera om allting så att blocken återigen innehåller 300 grodor var. Denna lösning kommer att vara snabbare än den ovan, då vi enbart behöver uppdatera största-grod-längd värdet på två ställen. Eftersom vi också har koll på nuvarande längden för varje block går det relativt snabbt att söka sig fram till en viss position. Så här kan en lösning se ut i C++ med STL, Kattis running time = 1.41 sek.
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
#define bl 300 //Initialstorleken för varje block
#define maxsize (bl*16)
#define setmax(a, b) if((a)<(b)) a = b
//Varje block i vectorn innehåller både alla grodor (first=vector<int>) samt värdet för den längsta grodan (second=int).
vector<pair<vector<int>, int> > grodorna;
static void fixa_minne(int N){
vector<pair<vector<int>, int> > old;
grodorna.swap(old);
int bit = 0;
int bit_pos = 0;
for(int i=0; i<N; i++){
while(old[bit].first.size() == bit_pos){
bit++;
bit_pos = 0;
}
if (i % bl == 0){
pair<vector<int>, int> ny;
ny.second = -1;
grodorna.push_back(ny);
}
grodorna.back().first.push_back(old[bit].first[bit_pos]);
setmax(grodorna.back().second, old[bit].first[bit_pos]);
bit_pos++;
}
}
int main(){
int N, H;
//Indata
scanf("%d %d", &N, &H);
for(int i=0; i<N; i++){
//Skapa ett nytt block vid varje bl:e groda
if (i % bl==0){
pair< vector<int>, int > nytt_block;
nytt_block.second = -1;
grodorna.push_back(nytt_block);
}
int grod_langd;
scanf("%d", &grod_langd);
grodorna.back().first.push_back(grod_langd);
setmax(grodorna.back().second, grod_langd);
}
//Utför alla hopp
for(int i=0; i<H; i++){
int fran, steg, till;
char riktning[2];
scanf("%d %s %d", &fran, riktning, &steg);
fran--, till = fran + (riktning[0]=='H' ? steg : -steg);
int r = riktning[0] == 'H' ? 1 : -1;
//Hitta i vilket block grodan som ska hoppa ligger i
int startpos = 0;
int startblock = 0;
for(startblock = 0; startblock<grodorna.size(); startblock++){
if(startpos + grodorna[startblock].first.size() > fran)
break;
startpos += grodorna[startblock].first.size();
}
//...och ta reda på offset i det blocket
int offset_i_startblock = fran - startpos;
//Grodans längd
int frangroda_langd = grodorna[startblock].first[offset_i_startblock];
//På samma sätt, hitta i vilket block grodan ska landa, och på vilken plats
int endpos = 0;
int endblock = 0;
for(endblock = 0; endblock<grodorna.size(); endblock++){
if(endpos + grodorna[endblock].first.size() > till)
break;
endpos += grodorna[endblock].first.size();
}
int offset_i_endblock = till - endpos;
//Specialfall - grodan hoppar inom ett block
if (startblock == endblock){
int max_langd = -1;
int pos = offset_i_startblock + r;
//Hitta största längden, och flytta efter grodorna
do {
setmax(max_langd, grodorna[startblock].first[pos]);
grodorna[startblock].first[pos-r] = grodorna[startblock].first[pos];
} while ((pos+=r)-r != offset_i_endblock);
//Stoppa in grodan där den ska landa
grodorna[startblock].first[offset_i_endblock] = frangroda_langd;
//Skriv ut längsta grodan den hoppar över
printf("%d\n", max_langd);
} else {
int max_langd = -1;
//Ta först reda på största grodlängden grodan hoppar över i från-blocket
for(int pos = offset_i_startblock+r; pos != -1 && pos != grodorna[startblock].first.size(); pos += r){
setmax(max_langd, grodorna[startblock].first[pos]);
}
//Ta nu bort grodan från från-blocket
grodorna[startblock].first.erase(grodorna[startblock].first.begin()+offset_i_startblock);
//Om det var längsta grodan vi tog bort (i blocket) måste vi hitta den som just nu är längst
if(grodorna[startblock].second == frangroda_langd){
grodorna[startblock].second = -1;
for(int i=0; i<grodorna[startblock].first.size(); i++)
setmax(grodorna[startblock].second, grodorna[startblock].first[i]);
}
//Iterera nu snabbt över blocken grodan hoppar över och hitta längden på längsta grodan hittills
for(int block = startblock + r; block != endblock; block += r){
setmax(max_langd, grodorna[block].second);
}
//Kolla nu i blocket grodan ska landa, fast enbart de grodor den hoppar över, vilken längd den längsta grodan har
for(int pos = offset_i_endblock; pos != -1 && pos != grodorna[endblock].first.size(); pos -= r){
setmax(max_langd, grodorna[endblock].first[pos]);
}
//Stoppa nu in grodan på rätt plats. Om grodan hoppar åt höger vill vi stoppa in den efter den senaste den hoppade över.
grodorna[endblock].first.insert(grodorna[endblock].first.begin()+offset_i_endblock+(r==1), frangroda_langd);
setmax(grodorna[endblock].second, frangroda_langd);
//Skriv ut längsta grodan den hoppar över
printf("%d\n", max_langd);
//Blockstorleken överskriden. Vi omorganiserar minnet så att vi bör får snabbare körningstid framöver.
if (grodorna[endblock].first.size() > maxsize)
fixa_minne(N);
}
}
return 0;
}
Bäst[redigera]
Den bästa lösningen är dock såklart att kombinera ett indexerat balanserat binärt träd med ett segment tree. Med ett indexerat balanserat binärt träd kan man sätta in och ta bort objekt på ett specifikt index i O(log n) tid där n är storleken på trädet. Med ett segment tree kan man få fram det största värdet i ett visst intervall i O(log n) tid. Kombinationen får vi genom att för varje nod i trädet hålla reda på längden för grodan noden svarar mot, största längden för en groda i subträdet som noden är rot i, antalet noder i subträdet noden är rot i, samt pekare till nodens vänstra och högra barn. Noder till vänster anses ha lägre index och noder till höger ha högre index.
Med hjälp av storleken på subträden kan vi enkelt hitta fram till den nod som svarar mot ett visst index. Söker jag efter grodan/noden på index 16 i nuvarande subträd och det vänstra subträdet innehåller 9 noder, då söker jag efter grodan/noden på index 16-9-1=6 i det högra subträdet. Tack vare storleken på subträden kan vi också alltid se till att storleken på det vänstra samt högra subträdet är någorlunda lika stora, genom att göra en sedvanlig trädrotation, d.v.s. hålla trädet balanserat. Tack vare max-värdet för subträdet kan vi snabbt returnera max-värdet så fort vårt sökta intervall innesluter intervallet subträdet svarar mot, och på så sätt snabbt få fram det största värdet (längsta grodan) i O(log n) tid, eftersom godtyckligt intervall kan täckas med O(log n) stycken intervall som subträden/noderna svarar mot.
Varje query på formen "A 'V' B" kan då behandlas på följande sätt (fallet där grodan hoppar åt höger kan behandlas analogt):
- Skriv ut största värdet för en groda i intervallet [A-B,A).
- Låt h = höjden för grodan som ska hoppa, d.v.s. största värdet i intervallet [A,A+1).
- Ta bort grodan/noden på index A.
- Lägg till en ny nod/groda med höjd h på index A-B.
Att ta fram största värdet för godtyckligt intervall tar O(log n) tid. Detsamma gäller för insättning och borttagning av en nod. På så sätt får vi en tid på O(log n) per query.
Om vi bygger trädet i O(N log N) som i lösningen nedan får vi en komplexitet på O(N log N + H log N). Trädet kan dock enkelt byggas i O(N) och således kan vi uppnå komplexiteten O(N + H log N) om vi nu så skulle vilja. I lösningen nedan kör vi med noll-indexering och använder en hemmasnickrad IO-klass IntIO för smidig (och snabb!) inläsning, som dock förlitar sig på att inga extra whitespaces finns i indata filen.
import java.io.*;
public class Frogs
{
private static Node root = null;
public static void main(String[] klein) throws IOException
{
final IntIO in = new IntIO(System.in);
final PrintWriter out = new PrintWriter(System.out);
final int N = in.getInt(), H = in.getInt();
for(int i = 0; i<N; i++) root = insert(root, new Node(in.getInt()), i);
for(int i = 0; i<H; i++)
{
final int A = in.getInt() - 1, dir = in.read();
in.skip(1);
final int B = in.getInt(), h = query(root, A, A+1);
out.println(dir=='V' ? query(root, A-B, A) : query(root, A+1, A+B+1));
root = delete(root, A);
root = insert(root, new Node(h), dir=='V' ? A-B : A+B);
}
out.flush();
}
private static class Node
{
final int h;
int size, max;
Node left, right;
Node(final int hh)
{
max = h = hh; size = 1;
}
Node(final int hh, final Node ll, final Node rr)
{
h = hh; left = ll; right = rr;
update(this);
}
}
private static int query(final Node p, final int left, final int right)
{
if(p.size==right-left) return p.max;
int max = 0;
if(size(p.left)>left) max = Math.max(max, query(p.left, left, Math.min(size(p.left), right)));
if(right>size(p.left) && left<=size(p.left)) max = Math.max(max, p.h);
if(right>size(p.left)+1) max = Math.max(max, query(p.right, Math.max(0,left-size(p.left)-1), right-size(p.left)-1));
return max;
}
private static Node insert(final Node p, final Node nod, final int i)
{
if(p==null) return nod;
++p.size;
if(nod.h>p.max) p.max = nod.h;
if(size(p.left)>=i)
{
p.left = insert(p.left, nod, i);
if(size(p.left)>size(p.right)) return rotateR(p);
}
else
{
p.right = insert(p.right, nod, i-size(p.left)-1);
if(size(p.right)>size(p.left)) return rotateL(p);
}
return p;
}
private static Node delete(final Node p, final int i)
{
if(size(p.left)==i)
{
if(p.left==null && p.right==null) return null;
final int left = size(p.left), right = size(p.right);
if(left>right)
{
final int h = query(p.left, left-1, left);
p.left = delete(p.left, left-1);
return new Node(h, p.left, p.right);
}
else
{
final int h = query(p.right, 0, 1);
p.right = delete(p.right, 0);
return new Node(h, p.left, p.right);
}
}
if(size(p.left)>i)
{
p.left = delete(p.left, i);
update(p);
if(size(p.left)<size(p.right)) return rotateL(p);
}
else
{
p.right = delete(p.right, i-size(p.left)-1);
update(p);
if(size(p.right)<size(p.left)) return rotateR(p);
}
return p;
}
private static Node rotateR(final Node p)
{
final Node tmp = p.left;
p.left = tmp.right;
tmp.right = p;
update(p);
update(tmp);
return tmp;
}
private static Node rotateL(final Node p)
{
final Node tmp = p.right;
p.right = tmp.left;
tmp.left = p;
update(p);
update(tmp);
return tmp;
}
private static void update(final Node p)
{
p.max = Math.max(p.h, Math.max(max(p.left), max(p.right)));
p.size = size(p.left) + size(p.right) + 1;
}
private static int max(final Node p)
{
if(p==null) return 0;
return p.max;
}
private static int size(final Node p)
{
if(p==null) return 0;
return p.size;
}
private static class IntIO extends BufferedInputStream
{
public IntIO(final InputStream in)
{
super(in);
}
public IntIO(final InputStream in, final int buf_size)
{
super(in,buf_size);
}
public int getInt() throws IOException
{
int chr = read(), sum = chr-'0';
while((chr = read())>' ') sum = (sum<<3)+sum+sum + chr-'0';
if(chr==13) skip(1); //Windows
return sum;
}
}
}