So Mike fixed the problem and found out the cause ?

So many assholes downvoting these days like do you feel important when you downvote ? get a life retards we haven't seen any information about the problem yet

Good luck to everyone!

Educational rounds are usually very good, hopefully this one too. Good luck to all!

Is it rated?

thanhchauns2 go big or go bald...

Thank you for this competition, it gives me a chance to advance.

Tomorrow is China's Mid-Autumn Festival. happy mid-Autumn Festival!

Hidden...

Tomorrow is Mid-Autumn Festival, which is one of the Chinese traditional festlval. I wish all Chinese participants a Happy Mid-Autumn Festival!

i have always got negative delta in edu rounds lol hope to break the streak

I feel dumb reading D from last 45 minutes and not even understanding how the answers for test cases are being constructed

Don't understand why my code of problem C works less than 0.2s on local machine with 2*10^5 & 2*10^5 data while TLE on testcase 6...

Hey!
Is weightage for every question the same in Edu rounds?

Hope I can return to the candidate master.

i don't understand how 4700 people solved C.

damn that ad-hoc B

{deleted]

How the heck we generate the 'M' sequences in D ? given that we have taken the difference between last element and every element for each item and sort it in increasing order ?

The only thing problem C educated me about was that even 1e18 is not enough to keep as infinity in your template

In C, my O((m+n)logn) solution gave TLE on the 6th test case. Any idea why?

How to solve D?. I thought of using max heap but was getting the wrong answer in test case 5.

Meaningless F with the easiest gf knowledge

How to solve B?

nice problems but i'm wondering why my f is wrong answer on test 13 QAQ

In problem D, I was stuck on this approach and was getting WA on test 11. Here is my approach: We can see that $$$4^{10} > m$$$. Initially we can consider the case where we take all the last elements. We define a variable $$$p=1$$$, denoting total number of ways with current elements. Then we can greedily add elements to our set from each row until $$$p \leq m$$$, each time we add element from such row which has largest latest element (from end). Then we can generate all sets and maximize our answer.

But I can't understand why this approach is wrong. :(

How to solve B?

I feel like killing myself , missed AC on D by one simple mistake $$$ if( z >= ans ) $$$

AC Code https://codeforces.me/contest/1574/submission/129416404

Wrong Submission https://codeforces.me/contest/1574/submission/129415307

terrific terrific terrific terrific terrific terrific terrific sample cases

I can't believe I forgot how to do knapsack with items appearing arbitrarily many times and sum of weights a small number >_>

At least I'll remember it now in the future, very educational round :)

How should I improve myself to solve problems like B?

Could someone explain the first sample of F? The way I'm interpreting the problem, the answer should be 0. Since any valid array a needs to have as many [occurrences of $$$A_1= [2, 1, 2]$$$] in it as [occurrences of any non-empty sub-array of $$$A_1$$$], in particular it seems that our array can't contain the number 2. Since $$$A_1$$$ itself has 1 occurrence of $$$A_1$$$ but two occurrences of [2], which is a nonempty sub array of $$$A_1$$$. And then we are banned from using the number 1 as well since it's contained in $$$A_1$$$ and we can't make $$$A_1$$$. And then similarly since $$$A_2=[1,3]$$$ we are banned from using the number 3 and it's impossible. What's the right way to read this?

I really liked the problem C (cool implementation of binary search + some key observations). However I did not like the difference in constraints of attack and defense upper limit ( the attack can be as high as 1e18 and defense up till 1e12).

When I first read the problem , I read only the defense constraints (1e12). I reasoned that since was n was also only till 2*10^5 , the answer can never exceed 1e18. So I took 1e18 as INF. I submitted my solution with INF set as 1e18 only to receive a WA . I reread the problem , couldn't figure out a problem until I saw the constraint on attack. Quickly changing some code I submitted again and got AC.

In hindsight I should have been more careful while reading the problem and there was no fault of the authors , however if possible from the next time this can be avoided.

Hi everyone, any pointers on how we can solve B? wasn't able to come up with any approach for it.

How to solve E?

Can someone explain what does the following line mean in tourist's submission 129351289? I'm literally this line away from solving D :(

if (v[i] < c[i] - 1) {
    break;
}

EDIT: seems this line is not very crucial, my original implementation was not fast enough.

Write lots of weird stuffs on problem D and suddenly realized that I had just "invented" trie again.

Is there any easier approach for problem A than this one? I couldn't come up with idea immediately.

int n;
cin>>n;
char open='(',close=')';
for(int i=0;i<n;i++){
    for(int j=i;j<n;j++) cout<<open;
    for(int j=i;j<n;j++) cout<<close;

    for(int j=0;j<i;j++) cout<<open;
    for(int j=0;j<i;j++) cout<<close;
    cout<<nl;
}

i using cout_cin in contest = TLE 6 https://codeforces.me/contest/1574/submission/129409353 i using printf_scanf after contest = Ac https://codeforces.me/contest/1574/submission/129417724

lol

C tests are bigger than 1e18? :|

B was harder than C

I used MAP , HASH , priority_queue and greedy in Problem D.But I haven't solved it. So I'd like to know whether Problem D has a high point of about 2000? I think it is much more difficult than Problem C.

I want to kill myself . Missed AC on D by a stupid mistake $$$ if(z >= ans)$$$

AC Solution

Wrong Solution

https://codeforces.me/contest/1574/submission/129407156 nice submission from alt to hack by yourself

https://codeforces.me/contest/1574/submission/129419462 Hey Guys, noobie here.I thought I solved c in (m+n)logn but getting TLE on test case 4. Kindly help

nice last time solved B C and couldn't solve A , now i solved A C and couldn't solve B >:(

Just replaced cin and cout in problem C with scanf and printf, and it worked. Just wish I had tried that earlier (>﹏<）

The fact that the last round had an unexpected (unknown) error, and this round just after 2 days went flawless is one of the reasons I love cf. Great work.

B. Combinatorics Homework

Input:

1

1 1 3 2

Judge output: YES

I think the output should be: NO

Because you can't make 2 pairs in the context.

[abccc] How can you make 2 pairs? Can you please specify your string that satisfies?

A brief explaination would be appreciated. Thank you.

if(you think comment should be downvoted) continue; 	//keep thinking but don't downvote :-)

When io issues aren't just affecting python users...

I don't know why my program with same time complexity as others which passed don't work. Can anybody please explain why this is happening. This is the link to the code.

Why did this did not worked for C? https://codeforces.me/contest/1574/submission/129409251 I have seen few submissions which follow the same approach and they got passed. Can anyone plz help?

Can anybody tell me why my solution to D is failing?

I iterate over all the sums I can get with those numbers, but in order from maximum to minimum. As soon as I have a solution which is not 'banned' I print it out. I guess it should work.

In priority queue I keep two values (sum, chosen items).

EDIT: I had a little bug but now after fixing got TLE. But why? I think I should find the solution in $$$m$$$ operations.

Solution

Can Anyone help me find error in my code i'm getting wrong output format Unexpected end of file — int32 expected in Test 6.

My approach is: I'm starting with the vector having the highest build(i.e, all the last elements of all rows say top layer) in the priority queue then for each top element of the priority_queue I'm pushing all the new vectors with a new element in one of the rows that can be formed from the next lower layer with the build value of the vector at the beginning of vector.I'm pushing popping until i get a vector which is not in the our set of bad vectors.(soory for bad explaination >_<)

#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long 
#define pb push_back
#define PI 3.141592653
#define pll pair<ll,ll>
#define V vector
#define F first
#define S second
#define INF LLONG_MAX
using namespace __gnu_pbds;
using namespace std;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll lcm(ll a, ll b){    return (a / __gcd(a, b)) * b;}

void solve(){
    ll n;
    cin >> n;
    V<V<ll>> v(n);
    V<ll> vec(n+1);
    for(int i = 0; i < n; i++){
        ll m;
        cin >> m;
        v[i].resize(m);
        for(int j = 0; j < m; j++)
            cin >> v[i][j];
        vec[i+1] = m-1;
        vec[0] += v[i][m-1];
    }
    ll m;
    cin >> m;
    set<V<ll>> ban;
    for(int i = 0; i < m; i++){
        V<ll> vv(n+1);
        for(int j = 1; j <= n; j++){
            cin >> vv[j];
            vv[j]--;
            vv[0] += v[j-1][vv[j]];
        }
        ban.insert(vv);
    }
    priority_queue<V<ll>> q;
    q.push(vec);
    while(q.size() <= 2e6){
        auto a = q.top();
        q.pop();
        if(ban.find(a) != ban.end()){
            for(int i = 1; i <= n; i++){
                V<ll> vv(a);
                if(a[i] == 0)   continue;
                vv[i]--;
                vv[0] += (v[i-1][vv[i]]-v[i-1][a[i]]);
                q.push(vv);
            }
        }
        else{
            for(int i = 1; i <= n; i++)
                cout << a[i]+1 << " ";
            cout << endl;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    //cin >> T;
    for(int i = 1; i <= T; i++){
        //cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

UPD: I was storing some same vectors multiple times. Accepted Code.

Problem C has taught me that qsort TLEs and std::sort doesn't

Seems like tests for problem F were super weak, I hacked many reds without even knowing the question

My solution to problem D using trie data structure. First of all construct a trie of the banned combinations. Now we will be iterating over each banned prefix(using a dfs on the trie) and take the remaining values the maximum possible. Here is my submission. Hope it helps someone. Submission:- https://codeforces.me/contest/1574/submission/129429122

Great questions.

I think my solution for problem D is kind of different. I passed pre-tests by using the pigeonhole principle， brute force and a trick.

At first, I got a wrong observation: if $$$\prod_{i=1}^n x_i > m$$$, then we can only consider the top $$$x_i$$$ equipments for the $$$i$$$-th slot, because according greedy and the pigeonhole principle, the answer must be already considered. And $$$\max_{i = 1}^n x_i$$$ can be calculated easily by using binary search. Now, we can enumerate all possible builds and get the "answer".

After getting WA on test 13 for a lot of times, I find out a case that the observation did not work. For example:

3
6 1 2 3 4 5 6
6 1 2 3 4 5 100
6 1 2 3 4 5 100
3
4 6 6
5 6 6
6 6 6

And I think out a trick: for a banned build $$$b$$$, for the $$$i$$$-th slot, replace the $$$b_i$$$ with $$$b_{i} - 1$$$, and then take $$$b$$$ in to consider.

The trick appear to cover cases that the observation did not work, and I do pass all pre-tests.

(Hope that I will not get FST

129449581 got accepted But 129414197 didn't

There is difference in only one line of program.

When i used (long long) 9e18, it passed. But when i used LONG_MAX i failed.

Can anyone say me what happened? Thanks in advance!