| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336545 | aanastasov | Counting Mushrooms (IOI20_mushrooms) | C++17 | 10 ms | 468 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mushrooms.h"
#include <array>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iostream>
#define DEBUG(x) std::cerr << #x << ": " << x << std::endl
/**
* Let's say that we want to identify K zeroes or ones in the first phase,
* which are subsequently to be used in the second phase,
* and let's say that we have B bits of efficiency per small query.
*
* Then we are going to need (2K - 1) / B + (N - 2K) / K queries in total.
* Note that we have N = 20000, so the expression is: (2K - 1) / B + (20000 - 2K) / K.
* As per wolframalpha.com, the optimal choice for K is 100 * sqrt(B),
* which shows that the optimal K is a function of B,
* which does make sense: as we can identify more bits per small query,
* it makes sense to identify a larger number of them
* so that we need fewer queries in the second phase.
*
* Finally sqrt(2) = 1.41, sqrt(2.5) = 1.58, and sqrt(3) = 1.73.
* With a particular efficiency, we would need
* (200 * sqrt(B) - 1) / B + (20000 - 200 * sqrt(B)) / (100 * sqrt(B)).
* With 2 bits of effiency, this evaluates to
* 281 / 2 + (20000 - 282) / 141 = 280.
*
* Moreover, if we can get to 3 bits of efficiency per small query,
* then we would need (2 * 173) / 3 + (20000 - 2 * 173) / 173 queries = 229 queries,
* which is pretty close to what we want.
*/
const int PHASE_ONE_COUNT = 142;
template<typename T> void debugVector(std::vector<T> v) {
std::cerr << "{";
for (int i = 0; i < v.size(); ++i) {
if (i > 0) std::cerr << ", ";
std::cerr << v[i];
}
std::cerr << "}" << std::endl;
}
inline int random(int a, int b) {
return a + rand() % (b - a + 1);
}
struct Machine {
int n;
std::vector<int> order;
Machine(int n) {
this->n = n;
order = std::vector<int>(n - 1);
for (int i = 0; i < order.size(); ++i) {
order[i] = i + 1;
if (i > 0) {
int j = random(0, i - 1);
std::swap(order[i], order[j]);
}
}
}
int use(std::vector<int> seq) {
auto modifiedSeq = std::vector<int>(seq.size(), -1);
for (int i = 0; i < seq.size(); ++i) {
if (seq[i] == 0) {
modifiedSeq[i] = 0;
} else {
modifiedSeq[i] = order[seq[i] - 1];
}
}
return use_machine(modifiedSeq);
}
};
/*
int use_my_machine(std::vector<int> seq) {
// debugVector(seq);
return use_machine(seq);
}*/
std::pair<std::vector<int>, std::vector<int>> runPhaseOneTwoAndHalf(int n, int phaseOneCount,
Machine &machine) {
assert(n >= 1000);
// TODO(aanastasov): For this particular algorithm for phase one,
// we might need to permute the input to reduce the chances of adversarial input.
// We should be able to do this inside use_my_machine,
// which will be completely transparent to this implementation, which is pretty nice.
auto zeroes = std::vector<int>();
auto ones = std::vector<int>();
zeroes.push_back(0);
// Step 1: Identify sufficiently many items to have 3 zeroes or 3 ones.
// We spend too many queries here, it's better to utilize the 2-bit efficiency query here.
while (zeroes.size() < 3 && ones.size() < 3 && zeroes.size() + ones.size() < n) {
int next = zeroes.size() + ones.size();
auto seq = std::vector<int>{0, next};
int count = machine.use(seq);
assert(count >= 0 && count <= 1);
if (count == 0)
zeroes.push_back(next);
else
ones.push_back(next);
}
assert(n <= 4 || zeroes.size() == 3 || ones.size() == 3);
// Step 2: Utilize a 2.5-bit efficiency query from now on.
// The structure is the following:
// count = use_machine(known[0], unknown[0], known[1], unknown[1], known[2], unknown[2]),
// where known[0] = known[1] = known[2] are all 0s or all 1s, as identified from above.
// Now, unknown[2] is completely determined by the parity of count.
//
// However, there are two cases for unknown[0] and unknown[1]:
// Case 1: if unknown[0] = unknown[1], then we know them entirely, so we've identified 3 bits.
// Case 2: if unknown[0] /= unknown[1], then we know the are different, but we don't know
// which one is which; thus, we attempt to identify unknown[0] with a subsequent query by
// designating it as unknown[2], after which we would be able to deduce both.
// Therefore, with 50% we identify 3 bits, and with 50% we identify 1 bit + whether
// unknown[0] and unknown[1] are same or different, which is 1 more bit, for a total of 2.
// In expectation, we have 50% * 3 bits + 50% * 2 bits = 2.5 bits on average.
auto prevUnknown = std::vector<int>();
while (zeroes.size() < phaseOneCount
&& ones.size() < phaseOneCount
&& zeroes.size() + ones.size() < n) {
assert(prevUnknown.empty()
|| (prevUnknown.size() == 2 && std::min(prevUnknown[0], prevUnknown[1]) > 0));
int next = zeroes.size() + ones.size() + prevUnknown.size();
auto unknown = std::vector<int>{next, next + 1, next + 2};
if (!prevUnknown.empty()) {
unknown[2] = prevUnknown[0];
}
for (auto x : unknown) if (x >= n) {
assert(false); // This shouldn't happen because n >= 1000.
}
auto known = std::vector<int>();
assert(zeroes.size() >= 3 || ones.size() >= 3);
const bool usingZeroes = (zeroes.size() >= 3);
if (usingZeroes) {
known = std::vector<int>{zeroes[0], zeroes[1], zeroes[2]};
} else {
known = std::vector<int>{ones[0], ones[1], ones[2]};
}
auto seq = std::vector<int>{known[0], unknown[0], known[1], unknown[1],
known[2], unknown[2]};
const int count = machine.use(seq);
// Step 2.1: Need to handle the case where prevUnknown.empty() is false,
// so that we can identify those two old bits completely;
// as of now, we just know that they are not the same.
// Step 2.2: If prevUnknown.empty() is true, then we can identify one more item: unknown[2].
if (!prevUnknown.empty()) {
if (usingZeroes) {
if (count % 2 == 0) {
zeroes.push_back(prevUnknown[0]); ones.push_back(prevUnknown[1]);
} else {
zeroes.push_back(prevUnknown[1]); ones.push_back(prevUnknown[0]);
}
} else {
if (count % 2 == 0) {
zeroes.push_back(prevUnknown[1]); ones.push_back(prevUnknown[0]);
} else {
zeroes.push_back(prevUnknown[0]); ones.push_back(prevUnknown[1]);
}
}
prevUnknown.clear();
} else {
if (usingZeroes) {
if (count % 2 == 0) zeroes.push_back(unknown[2]); else ones.push_back(unknown[2]);
} else {
if (count % 2 == 0) ones.push_back(unknown[2]); else zeroes.push_back(unknown[2]);
}
}
assert(prevUnknown.empty());
// Step 2.3: Need to check if unknown[0] and unknown[1] are the same,
// in which we case we know them entirely,
// or if they are different, in which case, we need to push them to prevUnknown.
const int count2 = count % 2 != 0 ? count - 1 : count;
assert(count2 == 0 || count2 == 2 || count2 == 4);
if (count2 == 0 || count2 == 4) { // same
if (usingZeroes) {
if (count2 == 0) { zeroes.push_back(unknown[0]); zeroes.push_back(unknown[1]); }
else { ones.push_back(unknown[0]); ones.push_back(unknown[1]); }
} else {
if (count2 == 4) { zeroes.push_back(unknown[0]); zeroes.push_back(unknown[1]); }
else { ones.push_back(unknown[0]); ones.push_back(unknown[1]); }
}
} else { // different
prevUnknown.push_back(unknown[0]);
prevUnknown.push_back(unknown[1]);
}
}
if (!prevUnknown.empty()) {
// Need to handle this case correctly.
auto seq = std::vector<int>{0, prevUnknown[0]};
int count = machine.use(seq);
if (count == 0) {
zeroes.push_back(prevUnknown[0]);
ones.push_back(prevUnknown[1]);
} else if (count == 1) {
zeroes.push_back(prevUnknown[1]);
ones.push_back(prevUnknown[0]);
} else {
assert(false);
}
}
return {zeroes, ones};
}
std::pair<std::vector<int>, std::vector<int>> runPhaseOne(int n, int phaseOneCount,
Machine &machine) {
auto zeroes = std::vector<int>();
auto ones = std::vector<int>();
zeroes.push_back(0);
while (zeroes.size() < 2 && ones.size() < 2 && zeroes.size() + ones.size() < n) {
int next = zeroes.size() + ones.size();
auto seq = std::vector<int>{0, next};
int count = machine.use(seq);
assert(count >= 0 && count <= 1);
if (count == 0)
zeroes.push_back(next);
else
ones.push_back(next);
}
assert(n <= 2 || zeroes.size() == 2 || ones.size() == 2);
while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount && zeroes.size() + ones.size() < n) {
int next0 = zeroes.size() + ones.size();
int next1 = next0 + 1;
if (next1 >= n) break;
bool useKnownZeroes = zeroes.size() >= 2;
auto seq = std::vector<int>();
if (useKnownZeroes)
seq = std::vector<int>{zeroes[0], next0, zeroes[1], next1};
else
seq = std::vector<int>{ones[0], next0, ones[1], next1};
int count = machine.use(seq);
assert(count >= 0 && count <= 3);
if (useKnownZeroes) {
if (count >= 2) ones.push_back(next0); else zeroes.push_back(next0);
if (count % 2 != 0) ones.push_back(next1); else zeroes.push_back(next1);
} else {
if (count < 2) ones.push_back(next0); else zeroes.push_back(next0);
if (count % 2 != 1) ones.push_back(next1); else zeroes.push_back(next1);
}
}
return {zeroes, ones};
}
int count_mushrooms(int n) {
int phaseOneCount = std::min(n / 2, PHASE_ONE_COUNT);
// NOTE(aanastasov): This is purely to reduce the number of edge cases
// that needs to be consider with the more efficient phase one algorithm.
Machine machine(n);
auto response = (n <= 1000)
? runPhaseOne(n, phaseOneCount, machine)
: runPhaseOneTwoAndHalf(n, phaseOneCount, machine);
auto zeroesLocs = response.first;
auto onesLocs = response.second;
int zeroesCount = 0;
int onesCount = 0;
int next = zeroesLocs.size() + onesLocs.size();
while (next < n) {
int len = std::min(n - next, (int)std::max(zeroesLocs.size(), onesLocs.size()));
auto seq = std::vector<int>(2 * len);
auto known = zeroesLocs.size() > onesLocs.size() ? zeroesLocs : onesLocs;
for (int i = 0; i < len; ++i) seq[i * 2] = known[i];
for (int i = 0; i < len; ++i) seq[i * 2 + 1] = next++;
int count = (machine.use(seq) + 1) / 2;
if (known == onesLocs) {
zeroesCount += count;
onesCount += len - count;
} else {
onesCount += count;
zeroesCount += len - count;
}
}
return zeroesCount + zeroesLocs.size();
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||