I GOT ONLY 10 MARKS !
IS THERE ANY WAY FOR ME TO BE SELECTED!
i thought about same but failed to carry out implmentation.GOT 0. 
I got 40 in ZCO 2019, 0 in INOI 2019 and and 110 in ZCO 2020. For me the questions this year were easier to think of within the time limit (or was it pure luck that got me the solution?). Anyways, I think the cutoff will lie in the 30-100 range. Any other cutoff would mean too many/too less students in INOI 2020.
Same here bro
What I did was I was able to come up with a recursive solution. If we have
f(p, ind) // Return value of this function is our required answer
then the base cases are:
if p == 1:
return ind // ind will be either 0 or 1
else you can do:
else:
if ind % 2 == 0:
return f(p-1, ind // 2)
else:
return f(p-1, ind // 2) + pow(2, p-1)
You can get this relation by looking at the patterns of numbers corresponding to each p.
1 Like
What’s the difference between the Pre-Test score and the actual score ??
New cases are added after ZCO and your scores are re-evaluated
If you have seen the rounds of Codeforces, ZCO is just like that. They test you on some cases, and after the contest, they test it against more test cases.
1 Like
are there any chances of the actual score being different from the pre-test score?
Its actually quite nice. Thanks for sharing this. I am actually feeling quite embarassed for not figuring out something so easy.
1 Like
Yes, its possible
this cutoff is out of 100 or out of 200?
Any idea when the results will be out ??
They said by next week, when I emailed them.
Can anyone give a detailed pseudo code / algorithm / complete solution for P2? I am still quite lost as to the parameters for the so called 3d dp. Thanks.
Anyone got any idea about when the results will be out ?
Here’s how I would do it:
#include "bits/stdc++.h"
using namespace std;
int n, m, k;
int dp[105][105][205][2];
vector<int> arra, arrb;
int MOD = 100 * 100 * 100 * 100 + 7;
int ways(int ai, int bi, int blocks_made, int last) {
/*
This function returns the number of possible ways to make an array of exactly k blocks, if:
* I have already taken the first 'ai' values from array A, and
* I have already taken the first 'bi' values from array B, and
* I have made 'blocks_made' blocks so far, and
* last is 0 if the last value I took was from array A, and 1 if the last value was from array B
*/
// if this state has already been calculated, then just return the calculated value
if (dp[ai][bi][blocks_made][last] != -1) {
return dp[ai][bi][blocks_made][last];
}
// if n numbers from array A have been taken and m numbers from array B have been taken, then all the numbers have been taken!
// so if, having taken all the numbers, I have made exactly k blocks, then there is one way to my answer
// if i have not made k blocks, then there are 0 ways ending like this
if (ai == n && bi == m) {
return dp[ai][bi][blocks_made][last] = (blocks_made == k);
}
// otherwise, make a result variable to store my answer
int res = 0;
// if last is 0, then the last number I took was from array A, and if it is 1, then the last number I took was from array B.
// this code recovers the last number I took, and stores it in 'las'
int las;
if (last == 0) las = arra[ai-1];
else las = arrb[bi-1];
// if I have taken less than n values from array A, I can still take at least another value from array A
if (ai < n) {
// if the next value from array A is the same as the last value I took
if (arra[ai] == las) {
// then, add the number of ways to get exactly k blocks made having:
// * taken 1 more value from array A, (so ai+1),
// * no more values from array B, (so bi),
// * the same number of blocks made (as the last number is the same as the next number, an additional block is not created), (so blocks_made)
// * now, the last number I took was from array A, (so 0)
res += ways(ai+1, bi, blocks_made, 0);
}
// but if the next value from array A is not the same as the last value I took
else {
// then, add the number of ways to get exactly k blocks made having:
// * taken 1 more value from array A, (so ai+1),
// * no more values from array B, (so bi),
// * one more block is made (as the last number is the not the same as the next number, another block is created), (so blocks_made+1)
// * now, the last number I took was from array A, (so 0)
res += ways(ai+1, bi, blocks_made+1, 0);
}
res = res % MOD;
}
// if I have taken less than m values from array B, I can still take at least another value from array B
if (bi < m) {
// if the next value from array B is the same as the last value I took
if (arrb[bi] == las) {
// then, add the number of ways to get exactly k blocks made having:
// * no more values from array A, (so ai),
// * taken 1 more value from array B, (so bi+1),
// * the same number of blocks made (as the last number is the same as the next number, an additional block is not created), (so blocks_made)
// * now, the last number I took was from array B, (so 1)
res += ways(ai, bi+1, blocks_made, 1);
}
// but if the next value from array B is not the same as the last value I took
else {
// then, add the number of ways to get exactly k blocks made having:
// * no more values from array A, (so ai),
// * taken 1 more value from array B, (so bi+1),
// * one more block is made (as the last number is the not the same as the next number, another block is created), (so blocks_made+1)
// * now, the last number I took was from array B, (so 1)
res += ways(ai, bi+1, blocks_made+1, 1);
}
res = res % MOD;
}
// now, I store my result in the dp table so I don't recalculate it again later, and return from the function
return dp[ai][bi][blocks_made][last] = res % MOD;
}
void solve() {
// first clear the two vectors, in case there are numbers from a previous testcase
arra.clear();
arrb.clear();
// here, reset the entire dp-table for future reuse as needed
for (int i=0; i<105; i++) {
for (int j=0; j<105; j++) {
for (int k=0; k<205; k++) {
dp[i][j][k][0] = -1;
dp[i][j][k][1] = -1;
}
}
}
// input the values for n, m, k
cin >> n >> m >> k;
// input the arrays themselves
for (int i=0; i<n; i++) {
int x;
cin >> x;
arra.push_back(x);
}
for (int i=0; i<m; i++) {
int x;
cin >> x;
arrb.push_back(x);
}
// the first value taken must be either the first value in array A or the first value in array B:
cout << (ways(1, 0, 1, 0) + ways(0, 1, 1, 1)) % MOD << endl;
}
int main() {
// to solve each test case
int t;
cin >> t;
while (t--) solve();
}
Please let me know if you find anything incorrect, or have any questions!
2 Likes
Thanks a lot. Very helpful, specially with the comments 
. I have a question, is the last block part really necessary for the dp?
I’m not sure about if there exists a 3D dp for this, (since I solved it using the 4th “last” dimension).
The reason why the last exists, is to check if the next value I’m going to add will create another block, or not.
Consider the arrays A = [3, 2, 4] and B = [1, 2, 4]
Let’s say I’ve already taken 2 values from A and 1 value from B (so my call to ways is currently with ai=2, bi=1). Here are the possible arrays I could have constructed so far to get here:
- [A, A, B] which is [3, 2, 1]
- [A, B, A] which is [3, 1, 2]
- [B, A, A] which is [1, 3, 2]
If the next value I’m going to add to the currently constructed array is from B, then the next value I will add is 2. Notice that I do not create a new block if my currently constructed array was either of option 2 or option 3 above, but if my currently constructed array was option 1, then I do create a new block. If I had the last value, I would be able to determine exactly when I create a new block, because last = 0 when 2 is at the end (the last item chosen was from array A), and last = 1 when 1 is at the end (the last item chosen was from array B).
In particular, without knowing the last value, I have no way of finding out whether the next element to add will create a new block, or not create a new block. This is why I use the last value.
Thanks for that. Just one more suggestion - wouldn’t keeping a check for blocks_made > k be another optimisation? Or am I missing something?