Invitation to April Easy '16 on HackerEarth

11 лет назад, скрыть # ^ |

;_;

→ Ответить

belowthebelt

11 лет назад, скрыть # |

+35

I read the tags! :P

→ Ответить

belltolls

11 лет назад, скрыть # ^ |

+44

then you're a whore :P

→ Ответить

Errichto

11 лет назад, скрыть # ^ |

+21

He didn't add tags though (and he didn't "ad" them).

→ Ответить

11 лет назад, скрыть # |

Reminder: Contest starts in a couple of minutes. Do take part.

→ Ответить

pakalupapito

11 лет назад, скрыть # |

+11

Great Problems,thanks for your effort, problems could had been less ambiguous

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 2 →

I agree, nice problems! In linear recurrences though, TL may be is too tight.

EDIT: as Pranet showed to me, my problem was in slow IO. The TL is fine!

→ Ответить

pranet

11 лет назад, скрыть # ^ |

Just going to put this here... http://codeforces.me/blog/entry/44126?#comment-287712

→ Ответить

abisheka

11 лет назад, скрыть # |

How to solve linear recurrences?Mine was O(6^3*logn) which obviously din't pass.

→ Ответить

11 лет назад, скрыть # ^ |

I had 5x5 matrix M which mapped (F[n - 2], F[n - 1], G[n - 2], G[n - 1], T[n - 1]) to (F[n - 1], F[n], G[n - 1], G[n], T[n]) where T[n] = H[0] + H[1] + .... Also precomputed all powers of the matrix M^e for e = 0, ..., 2¹⁵ - 1 and for e = 2¹⁵, 2 * 2¹⁵, 3 * 2¹⁵, ...2¹⁵ * 2¹⁵. Then each query can be done with multiplication of two matrices (one from the first set and one from the second). But still I had to optimize to fit in 2 seconds TL.

→ Ответить

11 лет назад, скрыть # ^ |

If you pre-compute M¹, M², M⁴, ... , M^2³⁰, then you can compute the answer to each query in approximately 5^2*log(n) operations. To achieve this reduction perform the multiplication from right to left. Refer to the editorial for more details.

→ Ответить

11 лет назад, скрыть # ^ |

speaking about editorials, where are they actually?

→ Ответить

11 лет назад, скрыть # ^ |

If you are looking at the problem page then there are 3 options, "Problem", "editorial", and "my submissions".

→ Ответить

11 лет назад, скрыть # ^ |

I have there only Problem and My submissions, but no Editorial :(

→ Ответить

11 лет назад, скрыть # ^ |

Editorial.

Also, if you are getting the option to go to practice area, do that and then see if you get any editorial option. If even that does not work then contact HackerEarth admins for help.

→ Ответить

11 лет назад, скрыть # ^ |

I precomputed M¹, M², M³, ..., M^2¹⁵ and M^2¹⁵, M^2·2¹⁵, M^3·2¹⁵, ..., M^{2¹⁵·2¹⁵}. So that I can compute M^e = M^{a + 2¹⁵·b} = M^a·M^b·2¹⁵ in only one matrix multiplication.

So I wonder what was so unoptimal in my solution, such that even log(n) multiplications from your solution may pass.

→ Ответить

pranet

11 лет назад, скрыть # ^ |

← Rev. 2 →

~~You seem to be answering each query in O(m^3) (Please correct me if I'm wrong). Intended is O(m^2*log(m)) per query.~~

My bad. Yours is indeed faster in theory( 5 vs log2(1000000000) ). ~~However, your solution does seem to be suffering from cache misses(just changing the order of the loops in matrix mul achieves a small speedup).~~

Dude! Use scanf and printf!. Your solution gets AC well within time limit(0.9s)

http://ideone.com/anJgcj

→ Ответить

11 лет назад, скрыть # ^ |

Ahh right, thank you very much for the investigation! My PR() macro confused me.

→ Ответить

ivanilos

11 лет назад, скрыть # ^ |

← Rev. 2 →

Is it too much to ask you what was your matrix M? I tried the same thing but I couldn't even pass the sample tests.

PS: Just found editorial is available, sorry for comment

→ Ответить

11 лет назад, скрыть # ^ |

+10

Sure, here it is:

    int step[5][5] = {
    //  F-2 F-1 G-2 G-1 T-1
       {0,  1,  0,  0,  0}, // F-1
       {0,  A,  B,  0,  0}, // F-0
       {0,  0,  0,  1,  0}, // G-1
       {D,  0,  0,  C,  0}, // G-0
      {FD, EA, EB, FC,  1}, // T-0
    };

→ Ответить

11 лет назад, скрыть # |

+13

How to solve A?

→ Ответить

11 лет назад, скрыть # ^ |

int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  SORT(a);
  ll ans = 0;
  for (int i = 0, v = 1; i < n; ++v) {
    ll c = v * 1ll * v;
    if (c >= a[i]) {
      ans += c - a[i];
      ++i;
    } else {
      ans += c;
    }
  }

  cout << ans << endl;

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 2 →

+20

It doesnt work, actually.. Test:

2
4 10

UPD: But is gets 100 on Oj...

→ Ответить

11 лет назад, скрыть # ^ |

-8

You did not read statement carefully:

"You quickly gather the balls and try to reconstruct a square pyramid(maybe of a different height) by using ALL the recovered balls"

You have to use all found balls. E.g. in your example the optimal solution is to buy 1, for first colour, then 0 for second (you have 4 already), 9 for third (you have 10 balls, but according to statement we have to use ALL balls, so we can't throw one extra ball away), and we heed to buy 6 balls for the last color (16 — 10 that we have = 6). so, all together we need to buy 1 + 9 + 6 = 16 balls.

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 4 →

Im using all the recovered balls, man:

Lets split 10 into 1 + 9 and now we can build a square pyramid with height = 3.

→ Ответить

vsp4

11 лет назад, скрыть # ^ |

← Rev. 2 →

You cannot split them as each layer has to be coloured differently. The 10 balls are of the same color

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 3 →

you can't split balls into two or more groups, because then you will have at least two layers of same colour which is prohibited.

→ Ответить

11 лет назад, скрыть # ^ |

You are right, thanks for explanations.

→ Ответить