For what it's worth next time you compete, a simple way to "multi-thread"
your solution is to chop the input up into N pieces (where N is your number
of cores), run your program in N different shells, and then concatenate the
output of your programs, fixing the case numbers. It's probably best to
write a shell script ahead of time to make that work, or find a threading
library that makes solving cases in parallel straightforward.
On Sun, Apr 16, 2017 at 7:01 PM Xiongqi ZHANG <zhangxion...@gmail.com>
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/8dca5786-f70a-458c-81e8-ba4be828faf2%40googlegroups.com
> .
> For more options, visit https://groups.google.com/d/optout.
>
--
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/CAHaiWHM1dvyrcPjuCEbF__1qG0FPDbvS399%2BpisMGDgAGBr3EQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
