Your machine is incredibly fast.
I switched to another workstation.
Ubuntu 14.04
Intel Xeon E5-1650 3.5GHz
32GB Memory
compiled by g++ 4.8.4
Still finished in 96 seconds.
> True. Today I've compiled again with no apparent changes, but the timers are
> normal.
>
> Release: 16 secs.
> Debug: 90 secs.
>
> Appears that something went wrong on my computer that day. Very strange
> because cache locality issues appears unable to explain the problem. And even
> a reboot didn't help at that time.
>
> BTW, your timer of 90 sec appears to be bad too. Compiled in 32-bit instead
> of 64-bit?
>
> Regards,
> WC Leung.
>
> On Monday, April 17, 2017 at 1:01:32 AM UTC, Xiongqi ZHANG wrote:
> > I just run your code and get the correct result for the practice input in
> > 90 seconds.
> >
> > I am running on Windows 10, Core-i5 4690 (3.5GHz), 16 GB Memory
> >
> > Compiled by Microsoft Visual Studio Community 2015 C++, Release Mode
> >
> >
> >
> > > First, congrats for those who manage to solve the question. I didn't
> > > manage that with literally every single formula derived wrongly.
> > >
> > > BTW, after fixing those formulas and applying the ideas from the
> > > analysis, I have the file at the bottom of the message.
> > >
> > > What confuse me is the time to run the solution. It takes about 6 minutes
> > > in my i7-4790, and most of the time of course goes to the debuff
> > > simulation which is O(n) where n = knight_attack / debuff. I've double
> > > checked that my binary is compiled with -O2.
> > >
> > > It means: if I am to run the code in a slower computer (e.g. an AMD
> > > E-350), the code will fail the time limit.
> > >
> > > I've also timed Eryx's solution in my computer. It's a bit faster than my
> > > solution here, but only faster for less than a minute, so the big picture
> > > is still the same. Didn't try the other six solutions, but they all
> > > appear to do the same simulation as Eryx, so the time needed to run
> > > shouldn't be very surprising.
> > >
> > > So I'll put my questions here:
> > > (1) is there a better algorithm to do this?
> > > (2) did anyone tried using multiple threads? (This should run 4 times
> > > faster in the i7-4790, but note that my E-350 is 20 times slower than the
> > > i7-4790, so threading likely won't help.)
> > > (3) DID ANYONE HAVE THE TIMER EXPIRED ONLY BECAUSE YOU'RE USING A SLOWER
> > > CPU? If yes please post up here.
> > >
> > > Regards,
> > > WC Leung.
> > >
> > > (p.s. I still managed to get to round 2. So see you there!)
> > >
> > >
> > > // Compile with MinGW-64 (6.3.0) in MSYS2
> > > // Compile switches: -std=c++11 -Wall -Wconversion -Werror
> > >
> > > #include <stdint.h>
> > > #include <algorithm>
> > > #include <cmath>
> > > #include <iomanip>
> > > #include <iostream>
> > > #include <map>
> > > #include <string>
> > > #include <queue>
> > > #include <vector>
> > >
> > > using namespace std;
> > >
> > > const int64_t maxint = 20000000000ll;
> > >
> > > int64_t DivCeiling(int64_t n, int64_t d) {
> > > return (n-1) / d + 1;
> > > }
> > >
> > > int64_t GetTurnsWithBuff(int64_t hit, int64_t attack, int64_t buff,
> > > int64_t buff_turns) {
> > > return buff_turns + DivCeiling(hit, attack + buff * buff_turns);
> > > }
> > >
> > > struct DataAfterDebuff {
> > > int64_t hit;
> > > int64_t attack;
> > > int64_t turns;
> > > };
> > >
> > > DataAfterDebuff GetDataAfterDeBuff(DataAfterDebuff original_data, int64_t
> > > hit, int64_t debuff, int64_t debuff_turns) {
> > > DataAfterDebuff data = original_data;
> > > for (int64_t i = 0; i < debuff_turns; ++i) {
> > > data.turns ++;
> > > data.attack -= debuff;
> > > if (data.attack < 0) {
> > > data.attack = 0;
> > > return data; // unable to kill
> > > }
> > > data.hit -= data.attack;
> > > if (data.hit <= 0) {
> > > data.turns++;
> > > data.hit = hit - data.attack - data.attack - debuff;
> > > }
> > > }
> > > return data;
> > > }
> > >
> > > void solve(int caseNo) {
> > > std::cout << "Case #" << caseNo << ": ";
> > > int64_t d_hit, d_attack, k_hit, k_attack, buff, debuff;
> > > cin >> d_hit >> d_attack >> k_hit >> k_attack >> buff >> debuff;
> > >
> > > int64_t attack_turns = maxint;
> > > for (int64_t i = 0; i+1 < attack_turns; ++i) {
> > > int64_t new_attack_turns = GetTurnsWithBuff(k_hit, d_attack,
> > > buff, i);
> > > if (new_attack_turns > attack_turns)
> > > break;
> > > attack_turns = std::min(attack_turns, new_attack_turns);
> > > }
> > >
> > > if ((attack_turns > 1 && (k_attack - debuff) >= d_hit) ||
> > > (attack_turns > 2 && (k_attack * 2 - debuff * 3) >= d_hit)) {
> > > cout << "IMPOSSIBLE" << "\n";
> > > return;
> > > }
> > >
> > > int64_t debuff_turns = 0;
> > > int64_t real_turns = maxint;
> > > int64_t endurance = 0;
> > > DataAfterDebuff data = {d_hit, k_attack, 0};
> > >
> > > for ( ; ; ) {
> > > // if debuff_turns > 0, get the turns needed for the next
> > > endurance.
> > > int64_t max_attack = endurance > 0 ? DivCeiling(d_hit, endurance)
> > > - 1
> > > : maxint;
> > > debuff_turns = debuff > 0 ? std::max(0ll, DivCeiling(k_attack -
> > > max_attack, debuff))
> > > : 0;
> > >
> > >
> > > data = GetDataAfterDeBuff(data, d_hit, debuff,
> > > debuff_turns > 0 ? debuff_turns -
> > > (k_attack - data.attack) / debuff : 0);
> > > //cout << data.hit << ' ' << data.attack << ' ' << data.turns <<
> > > '\n';
> > > int64_t current_turns;
> > > if (data.attack <= 0 || DivCeiling(data.hit, data.attack) >=
> > > attack_turns) {
> > > current_turns = data.turns + attack_turns;
> > > endurance = data.attack <= 0 ? maxint : DivCeiling(d_hit,
> > > data.attack);
> > > }
> > > else {
> > > int64_t first_attack_turns = DivCeiling(data.hit,
> > > data.attack) - 1;
> > > int64_t remaining_attack_turns = attack_turns -
> > > first_attack_turns;
> > >
> > > endurance = DivCeiling(d_hit, data.attack);
> > > if (endurance < 3)
> > > continue;
> > > int64_t heal_turns =
> > > remaining_attack_turns < 2
> > > ? 1
> > > : (remaining_attack_turns - 2) / (endurance - 2) + 1;
> > > current_turns = data.turns + attack_turns + heal_turns;
> > > }
> > >
> > > real_turns = std::min(real_turns, current_turns);
> > >
> > > if (data.attack <= 0 || debuff == 0)
> > > break;
> > > }
> > >
> > > cout << real_turns << "\n";
> > > }
> > >
> > > int main(int argc, char** argv) {
> > > int N;
> > > std::cin >> N;
> > > std::string str;
> > > std::getline(std::cin, str);
> > >
> > > for (int i = 0; i < N; ++i) {
> > > solve(i + 1);
> > > }
> > >
> > > return 0;
> > > }
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/bb3f08a0-991d-4055-b6f1-a66a93febf20%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
