Zadatak: Stringsobits

[ stf @ 29.08.2005. 12:22 ] @

Ovaj zadatak nikako neće da mi prođe na USACO-u kroz sve test primere. Zna li neko optimalno rešenje?

Stringsobits

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.
This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.
Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)
5 3 19

OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)
10011

[ RooTeR @ 29.08.2005. 15:21 ] @

Kreiras sve reci u kojima se pojavljuje tacno L jedinica i sve ostalo su nule. Potom svaku tu rec prebacis u decimalni broj, pa ih sve lepo sortiras, i onda na kraju I-ti broj ispises u binarnom sistemu (dodas vodece nule ako je potrebno). Meni se cini da sam tako radio taj zadatak ...

[ stf @ 29.08.2005. 17:29 ] @

Ja sam sad nesto kreno preko binomnog koeficijenta, gde vrednost matrice m(a,b) prestavlja broj pojavljivanja jedinica (ukupno a) u stringu duzine b. Ako ni ovako ne bude radilo pokusacu i to tvoje resenje..

[ stf @ 29.08.2005. 17:50 ] @

Ne verujem da tvoje resenje moze da prodje kroz sve test primere. Mozda gresim, al evo primer iz zadatka:
Sve reci koje imaju 3 jedinice u sortiranom poretku su:
00111=7
01011=11
01101=13
01110=14
10011=19
10101=21
10110=22
11001=25
11010=26
11100=28
Ovde se trazi I-ti broj sa 3 ili MANJE jedinica, ne samo tacno toliko.
Ukupno reci sa nula, jedan, dve ili tri jedinice ima 26 (u sortiranom poretku, decimalni sistem):
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,24,25,26,28.
Ovde je 19. broj 19, i sad ga ispisem kao binaran.
Ali sta naprimer ako se trazi 123456789. broj u nizu. Tada quicksort (n log n) ne moze da prodje.

Imao sam staro resenje slicno tvome, al ne moze da prodje! Mozda moze nesto da se uradi sa ovim binomnim koeficijentom (generisem pomocu njega vrednost m(a,b)) ili neko drugo resenje?

[ RooTeR @ 29.08.2005. 18:09 ] @

Sad sam bas poslao moje staro resenje da vidim da li prolazi ... i kao sto se ocekivalo, ne prolazi :) (meni je onda proslo; mislim da su od tada pomerili malo vremenske granice ...)

Na USACO-u me malkice nervira sto imaju tako mali time limit ... zna posteno da smori :)

Posto me mrzelo da ga ponovo resavam, pogledao sam analysis :)
Problem se reshava dinamichkim programiranjem ...

[ stf @ 29.08.2005. 18:33 ] @

Aj postuj ono objasnjenje iznad koda u Analysis

[ stf @ 29.08.2005. 22:51 ] @

Nasao sam u medjuvremenu resenje preko binomnog koeficijenta.

Slozenost je veoma mala: O(31*31*vreme za trazenje bin. koef.)

Takodje, algoritam nije tezak toliko za implementaciju

Thanks anyway :)

_{[Ovu poruku je menjao stf dana 29.08.2005. u 23:51 GMT+1]}

[ Mihajlo Cvetanović @ 30.08.2005. 09:39 ] @

Niz koji je ovde potreban je A000120, za objašnjenje videti link http://www.research.att.com/projects/OEIS?Anum=A000120. Sve što treba uraditi je proći kroz niz, ignorišući one vrednosti koje su veće od L, sve dok ne nađemo I-ti takav broj. Problem se sada svodi na računanje elemenata tog niza.