Moguce da je ucenik ostecen - Nacin bodovanja zadataka u prvoj etapi za osnovce

Takmičenja
1

O kom takmičenju se radi?

I etapa osnovneskole za sedmi razred

Poruka:

Molim Vas da nam objasnite na koji nacin je bodovan 6. zadatak Pokloni za roditelje? Moj ucenik ima na tom zadatku 40 poena, a pri testiranju dobija odgovor da mu je tacno 11 test primera od 16.

2

Ne verujem da je učenik oštećen, jer zbog datih opsega vrednosti za N1 i N2, algoritam lako ulazi u kvadratnu složenost i zadatak dobija TLE.
Ja sam pokušala da optimizujem na sledeći način:
l1=[]; l2=[]
n1 = int(input())
for i in range (n1):
a, b = map(int, input().split())
l1.append((a, b))

n2 = int(input())
for i in range (n2):
a, b = map(int, input().split())
l2.append((a, b))

l1 = sorted(l1)
l2 = sorted(l2)
m = int(input())
maks = 0
i=0; j=0
while i < n1 and l1[i][0] < m:

while j < n2 and l2[j][0] + l1[i][0] <= m:
maks = max(maks, l1[i][1] + l2[j][1])
j += 1

i += 1
j = 0
print(maks)

Slično razmišljanje je prošlo kod zadatka Blizanci. Međutim, ovde ova optimizacija nije dovoljna, i dalje je TLE.Molim nekoga iz Petlje (@teo ili neko drugi?) da nam da objašnjenje vezano za EFIKASNOST algoritma u ovmo zadatku.

3

@Mira hvala vam što ste se uključili u ovu temu! Nisam autor zadatka te ne mogu lako da pomognem. Petlja vrši tehničku podršku takmičenjima Društva Matematičara Srbije, a forum Algora je mesto gde su okupljeni i članovi komisija za takmičenja, takmičari, nastavnici, roditelji, kao i mi iz Petlje. Ponekad komisije uspevaju da vide na vreme ono što pitate na Algori i da odgovore, uglavnom su to teme koje se tiču većeg broja takmičara. Za specifičnije primedbe na rezultate takmičenja kao što je ova, preporučujem @JelenaAvramovic da se obratite zvanično komisiji za osnovce mejlom na takprog.os@gmail.com

4

Koliko sam video test primeri su podeljeni na 3 podzadatka i ukoliko jedan test primer ne radi u nekom podzadatku ne dobijaju se poeni za taj podzadatak.
Ovaj kod dobija maksimum poena :
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n;
cin>>n;
ll a[n];
ll i;
for(i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
ll m;
cin>>m;
ll b[m];
for(i=0;i<m;i++)
{
cin>>b[i];
}
sort(b,b+m);
ll j=0;
ll ans=2000000000;
for(i=0;i<n;i++)
{
ans=min(abs(a[i]-b[j]),ans);
while(a[i]>=b[j] && j<m)
{
ans=min(ans,(ll)(abs(b[j]-a[i])));
j++;
}
ans=min(ans,max(a[i],b[j])-min(a[i],b[j]));
if(j>=m)
j=m-1;
}
cout<<ans;
}

5

Da, ovaj kod prolazi, ali za zadatak BLIZANCI. Međutim, pitanje je bilo: kako bi se napisao efikasan kod za zadatak POKLONI.
Da li bi neko mogao da postavi rešenje za ovaj zadatak?

6

Sortiraš oba niza po težini i upišeš max cenu za prvih k elemenata. Onda obiđeš jedan niz iz leve a drugi iz desne i gledaš gde je max. Kompleksnost algoritma je O(n logn).

#include
#include

using namespace std;

struct gift {
int w;
int p;
};

bool compare_gifts(const gift &a, const gift &b) {
if(a.w < b.w)
return true;
if(a.w > b.w)
return false;
return a.p < b.p;
}

int main()
{
int n;
cin >> n;
gift a[n];
for(int i = 0; i < n; i++)
cin >> a[i].w >> a[i].p;

int m;
cin >> m;
gift b[m];
for(int i = 0; i < m; i++)
    cin >> b[i].w >> b[i].p;

int maxw;
cin >> maxw;

sort(a, a+n, &compare_gifts);
for(int i = 1; i < n; i++)
    a[i].p = max(a[i-1].p, a[i].p);

sort(b, b+m, &compare_gifts);
for(int i = 1; i < m; i++)
    b[i].p = max(b[i-1].p, b[i].p);

int maxp = 0;
int i = 0;
int j = m-1;

while(true) {
    while(j >= 0 && a[i].w + b[j].w > maxw)
        j--;

    if(i == n || j < 0)
        break;

    maxp = max(maxp, a[i].p + b[j].p);

    i++;
    while(i < n && a[i].p == a[i-1].p)
        i++;
}

cout << maxp << endl;
return 0;

}

7

blizanci mogu recimo sortiranjem i algoritmom tipa merge. kompleksnost O(n logn)

#include
#include
#include

using namespace std;

int main()
{
int m;
cin >> m;
long long a[m];
for(int i = 0; i < m; i++)
cin >> a[i];

int n;
cin >> n;
long long b[n];
for(int i = 0; i < n; i++)
    cin >> b[i];

sort(a, a+m);
sort(b, b+n);
long long r = abs(a[0]-b[0]);

int i = 0;
int j = 0;
while(true) {
    if(a[i] < b[j])
        i++;
    else
    if(a[i] > b[j])
        j++;
    else {
        r = 0;
        break;
    }

    if(i >= m || j >= n)
        break;

    int ri = abs(a[i] - b[j]);
    if(ri < r)
        r = ri;
}
cout << r << endl;
return 0;

}