awoo's blog

Educational Codeforces Round 174 [Rated for Div. 2]
By awoo, history, 3 days ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Curious? Check out the CSAI curriculum now. Limited scholarships available — don't miss your chance to study in Europe for free!

On Feb/18/2025 17:35 (Moscow time) Educational Codeforces Round 174 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 days ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

As a tester, I will give my 100% with best wishes

→ Reply
»
3 days ago, # |
  Vote: I like it +2 Vote: I do not like it

I wish be expert in this contest

→ Reply
»
3 days ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

As a participant, I can't spell BledDest without $$$\textbf{st}$$$.

→ Reply
»
3 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck everyone! I hope I can climb back to Specialist

→ Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

score distribution?

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Educational rounds don’t have scoring distribution, your score is # solved with sum of times as penalty.

    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Score distributions: all problems have exactly 1 score.

    → Reply
»
3 days ago, # |
  Vote: I like it -9 Vote: I do not like it

Hoping for +1.

→ Reply
»
3 days ago, # |
  Vote: I like it -7 Vote: I do not like it

after a long time i guess.

→ Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Ill reach expert tomorrow

→ Reply
»
3 days ago, # |
  Vote: I like it -30 Vote: I do not like it

I'm not a magician, but u'll get WA at test 2 in problem B tomorrow

→ Reply
»
3 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Hope this will be one of the best contests I've ever participated in!

→ Reply
»
2 days ago, # |
  Vote: I like it -12 Vote: I do not like it

I hope to improve my rating now, I had a bad streak.

→ Reply
»
2 days ago, # |
  Vote: I like it -12 Vote: I do not like it

hi toppers of coding.

→ Reply
»
2 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Hoping for positive delta :D

→ Reply
»
2 days ago, # |
  Vote: I like it -9 Vote: I do not like it

First Edu round in 2025?

Hope to reach 1700!

→ Reply
»
2 days ago, # |
  Vote: I like it +42 Vote: I do not like it

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

and what is the difference between Educational and a simple competition?

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    tap

    it says: "Educational rounds are meant for learning and not exactly practising (normal CF rounds).

    There is a 12 hr hacking phase once the contest gets over in case of Educational rounds. Hence, for rating update u must wait for 12-13 hrs :(

    Standings in Educational rounds are based on number of problems solved and penalties, whereas, in normal CF rounds, its based on total points earned (points for each question decrease with every passing minute)"

    → Reply
»
2 days ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

HOPE the A,B problems are doable and not too difficult like recent rounds. (for newbies like us to even have a chance to solve some problem)

→ Reply
»
2 days ago, # |
  Vote: I like it +4 Vote: I do not like it

all the best for everyone,hoping everyone would increase there ratings

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well "Everyone" simply can't get an increase in rating even if they all perform their best. This is how the rating system works.

    → Reply
»
2 days ago, # |
  Vote: I like it +11 Vote: I do not like it

I wish be master in this round.

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Last time I become Expert,but this time I will return to the pinnacle!

→ Reply
»
43 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Pls no GCD again.

→ Reply
»
43 hours ago, # |
  Vote: I like it -21 Vote: I do not like it

Hope you become grandmaster if you pray for Palestine!

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

SpeedForces scheduled.

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the non GPTable D. Atleast not by just copy pasting the question. I tried it out by participating unrated.

→ Reply
  • »
    »
    37 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, D did feel like it would give chat gpt a hard time visualising it

    → Reply
»
41 hour(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

ShitForces

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem E is close to this problem: 1686D - Linguistics

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

I hated E. D was not the best as well. I guess C was the best one ...

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    41 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simple dp count number of subsequence 1 2 2 .. 2 3

    → Reply
  • »
    »
    41 hour(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Considering every element must be between 1 and 3, we can see that beautiful sequences are in form of 1, 2, ... 2, and 3. So we can do dp on this. Consider following dp[N][3]: dp[i][j] -> number of valid subsequences ending on i with value j.

    → Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can check that the array must be in the form 1...3 where "..." represent one or more 2s.

    Number of subsequences would for that form would be 2^n — 1, as any number of 2s (except 0) work. But checking all 1s and 3s (say using a prefix count array) would be O(N^2).

    O(N) solution would be to count number of 1s so far, i.e. cnt1++. when you encounter 2, double curr and add cnt1. This works similar to the 2^n analysis count above. When encounter 3, you close the subsequence by adding curr to ans.

    Remember to mod for each operation

    → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u plz explain how your doing all this is equivalent to doing operations on all pair a formal proof will be really appreciated

      → Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Tests for E are terrible tbh

→ Reply
»
41 hour(s) ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Why This this code fails for problem B?

→ Reply
  • »
    »
    41 hour(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I made the same mistake when the component size > 1 it is a bipartite graph so you always need 2 colors (instead of the component size).

    → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you elaborate a bit more? Didn't really get what you mean by bipartite here

      → Reply
      • »
        »
        »
        »
        40 hours ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yeah when the component size > 1, we only need to do 2 operations. There is no odd cycle in the grid, so every component is a connected bipartite graph (See the definition of bipartite: https://en.wikipedia.org/wiki/Bipartite_graph ).

        → Reply
        • »
          »
          »
          »
          »
          40 hours ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Oh yeah you're right. Still I think my logic should always separate into two sets (I.E TLE instead of WA) Any clue on why it isn't working? 306733695 WA on 1451st ;-;

          → Reply
      • »
        »
        »
        »
        37 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually you dont need any bipartite graph i just check if any same value element has its neighbours or not .If it has some neightbours then taking that value take two chance else one chance take the n-1 lowest chance elements

        → Reply
  • »
    »
    30 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really like how clean your code is, gonna adapt some of these style for my next contest!!

    → Reply
»
41 hour(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

How did you all do C? I wasn't able to solve it after trying a lot of times, always failing test case 3,4,5 or TLE

I tried checking all the indexes of 1 and 3 in the given array, and for n number of 2's in between the indices, I added $$$2^n-1$$$ to the answer, making sure to use MOD exponentiation. :(

→ Reply
  • »
    »
    41 hour(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Iterating over the pairs of 1 and 3 is O(n^2), which is too slow. So, you have to compute the answer for the leftmost 1, paired with all 3's after it. Then, iterating from left to right in the array, we adjust the answer little by little (if we encounter a 2, ans /= 2; if we encounter a 3, ans--).

    → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! :)

      → Reply
    • »
      »
      »
      39 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you elaborate a bit? I didn't understand

      → Reply
      • »
        »
        »
        »
        17 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        An easier way to do it is with dp. dp[i][j] = number of subsequences in arr[:i] that end with j (and that are valid, ie you can't have sequences with multiple 1s or 3s). dp[i] = dp[i-1], and if arr[i] = 1 add 1 to dp[i][1], if arr[i] = 2 then you can append 2 to any previous subsequence ending with 1 or 2 so it's dp[i-1][2]*2 + dp[i-1][1], and if arr[i] = 3 then you add dp[i-1][2] to it. Return dp[-1][3].

        → Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    40 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Here's my attempt for solving E:

    • You first check all the strings with alternating letters:

    • For odd length ones (e.g.ABABA or BAB), add their (length — 1)/2 to "sum" which stores all the potential parts that you can replace with either AB or BA. This makes sense intuitively because you can always put any combination of ABs and BAs in an odd length alternating string — just take out one letter from it.

    • For even length ones (e.g. BABA), add their (length — 2)/2 to "sum", because you can take any combinations of AB and BA from them but need to exclude two letters (e.g., if you want to take "AB" from "BABA", then you have to treat the "B" at the front and "A" at the end independently). If you want to process the entire one using either AB or BA, store the length/2 to an array — there is an array for "AB" and another one for "BA".

    • Sort the arrays, process them from small to large. For instance, for the "AB" array, first check if the number of ABs left can cover up the currently smallest one needed. If yes, add one to the sum and deduct the covered amount from AB; if not, break.

    • Check for the independent As and Bs by iterating through the entire string. If the number of A/Bs available plus min(AB+BA, sum — ones that can be covered up by AB/BAs) is less than the actual frequency, the answer is "NO", else "YES". I think my explanation might be unclear or abstract. It is definitely helpful to look at some code!

    → Reply
»
41 hour(s) ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

1685B - Linguistics

p.s. i didn't know the problem and didn't solve E this time

positive delta plzzzzzzzzzzzzzzzzzzzz

→ Reply
  • »
    »
    41 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ++ I remembered that while solving E

    → Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why my code is failing on B? Cant figure it out :(

306758770

→ Reply
»
40 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

I did not realize C was just dp lol... I did it in such a different convoluted way 306723210

→ Reply
»
40 hours ago, # |
  Vote: I like it +45 Vote: I do not like it

Tutorial: How to solve E

Firstly, solve this problem

https://codeforces.me/contest/1686/problem/D

Then solve E

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Took 66 minutes and 3 WA for A and B each but solved C in 26 minutes first try lmao. I probably should've reread the problem and not spam solutions.

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Who is discussing today's contest ??

Shayan ? Aryanc403 ?

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

no wonder, how we have so many ac. https://www.youtube.com/watch?v=f2tbS12SLFw this guy leaked the solution :)

→ Reply
»
40 hours ago, # |
  Vote: I like it +20 Vote: I do not like it

problem C already existed hashhas: 105444G - Gig Combinatorics

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

306742121

C. WTF is wrong with this DP solution why am I getting TLE

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my code for B giving MLE? I have following code:

Spoiler

Every one of my variable should be around 5e5 * 4 = 2MB? And I have four of such variables(queue, singleDouble, visited, a). So shouldn't this be 10MB? Very less than 256MB limit?

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    mark visited once you enqueue during a bfs.

    → Reply
    • »
      »
      »
      38 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! It now got accepted! Next time I will keep this in mind

      → Reply
»
40 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

Take a look at my abomination of a solution for D

→ Reply
»
40 hours ago, # |
  Vote: I like it -6 Vote: I do not like it

If you don't want DP for C here is mod inverse(I hope don't get hacked).

Also did anyone felt problem A to be hardest like if the ordering was C D B A then it would be better?

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you explain your code

    → Reply
    • »
      »
      »
      39 hours ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Chain of thought:

      1. Answer has to be 1 2(1 or more occurance) and finally 3
      2. If we fix 1 and 2 and there are $$$k$$$ 2 between them in total we can take either once making 1 2 3 or twice 1 2 2 3 or k times at max
      3. So for every 1 and 3 having k in between we have total of $$$2^k -1$$$ possible answers
      4. On every 3, all the preceeding 1 will contribute some subsequences. We need to calculate for each one.
      5. For say 3 1s behind the current 3, and total number of 2s till 1st 1 is a then b then c and at this 3 it is d then total answer till this 3 as ending is $$$2^{d-a} -1 + 2^{d-b} -1 + 2^{d-c} -1$$$. So on for more
      6. $$$2^{a-b}$$$ is just $$$2^a/2^b$$$ then we have $$$2^d * [Inverse(2^a)+Inverse(2^b)+Inverse(2^c)] - 3$$$ so we can have this formula you can see in $$$solve()$$$ function when I see a 3 I just do this formula and I maintain this inverse sum in $$$curr$$$ and keeps $$$total1$$$ and $$$total2$$$ seen so far. $$$total2$$$ is used for calculating inverse sum at each 1 and $$$total1$$$ is subtracted at each 3 on calculation and is the last term in formula above
      7. It is linear with $$$log$$$ term for inverse and calculating $$$2^a$$$

      Edit: Integer overflow hacked. Use 2LL instead of 2 here

      → Reply
      • »
        »
        »
        »
        22 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was trying the same thing but could not figure out how to count multiple 1s for a fixed 3 faster. Your simplification on step 6 makes so much sense. Thankfully, I was able to figure out the dp soon after and got AC on this. I'll try reimplementing using this approach.

        → Reply
»
40 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why this is giving WA I am just counting for all the colour group with max no. of people who are not stranger and taking the max from all the groups and doing sum of those except the largest no. group which i will make all the other colour to that colour

Here is my submission Link

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro i did the same mistake actually there is greedy in this question maximumm set of strangers for the particular element cannot be more than 2 actually think about it consider the case 2 2 2 1 3 4 5 3 2 1 1 2 3 4 4 according to the logic we can make 2 set of stranger colors for 2 like consider [0][0] and [0][2] as the same set like there can only be maximum 2 sets of strangers for particular color i think

    → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what's the size of row and column for the test case you gave?

      → Reply
      • »
        »
        »
        »
        40 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        3*5

        → Reply
        • »
          »
          »
          »
          »
          40 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am getting correct answer for that test case.

          → Reply
          • »
            »
            »
            »
            »
            »
            39 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i think your's one was failing for 33rd of 2nd test case as well in the contest? it was same for me by the logic of getting the maximum connected component but that way the answer is not minimum

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              39 hours ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes it is failing in 33rd only but why?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                39 hours ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                n=2 m=3 5 5 5 4 4 4 consider this text case 33rd one according to our logic we would have got the maximum connected component i mean consider the sets we would have gotten 3 for 4 and 3 for 5 right? and we would have subtracted 6(which is the sum)-maxi(3) ok so we are getting 3 as a result now try to making two sets of each i mean consider one set of 5 which is stranger as {5,5} which is [0][0] and [0][2](since they don't share the sides) and the second set{5} as [0][1] same for {4} we have two sets alright? now in maximum 2 moves either for 4 or 5 we would have changed the colors of 5 to 4 or vice versa so the answer is 2 for this case not 3

                → Reply
      • »
        »
        »
        »
        40 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        /**
 * author: vanshgambhir
**/
#include<bits/stdc++.h>
#define ll long long
#define vi(n) vector<int> v(n);
#define loop(i, n) for (int i = 0; i < n; ++i)
#define all(v) v.begin(),v.end()
using namespace std;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
bool check(int row,int col,int n,int m){
	if(row>=0 && col>=0 && row<n && col<m) return true;
	return false;
}
void solve(){
		int n,m;
		cin>>n>>m;
		vector<vector<int>> v(n,vector<int> (m));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++) cin>>v[i][j];
		}
		vector<int> freq(n*m+1,0);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++) freq[v[i][j]]=1;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				for(int ind=0;ind<4;ind++){
					int newr=i+dx[ind];
					int newc=j+dy[ind];
					if(check(newr,newc,n,m)){
						if(v[i][j]==v[newr][newc]) freq[v[i][j]]=2;
					}
				}
			}
		}
		ll sum=0;
		for(int i=1;i<=n*m;i++){
			sum+=freq[i];
		}
		int maxi=*max_element(freq.begin(),freq.end());
		cout<<sum-maxi<<endl;
	}
int main() {
	ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	int t;
	cin>>t;
	while(t--){
		solve();
	 }
    return 0;
}

        check this code for reference it is accepted

        → Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For B, what is the result supposed to be for:

1
2 3
2 2 2 
5 4 4
→ Reply
»
40 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

:(

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A took me 30 minutes to debug because the array is not initialized. I finally solved only 2 problems. Goodbye Specialist.

→ Reply
  • »
    »
    36 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Humans are under-performed sometimes. I fumbled on C for no real reason. Better luck next time for all of us

    → Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How D?

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks, I was 1395 but now I will not be a specialist yet :)

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hurts :")

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was a nice challenge! I got a 10x dopamine boost after getting AC. The statement was a bit confusing, but overall, it was a great problem. What should the rating for B be? I think around 1200.

→ Reply
»
38 hours ago, # |
← Rev. 5   Vote: I like it -8 Vote: I do not like it

CAN ANYONE TELL WHY THIS IS FAILING TEST 3

306757323

→ Reply
  • »
    »
    38 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ll possible = (1 << twos); cnt of $$$2s$$$ between $$$1$$$ and $$$3$$$ can be very large, it won't fit in int or evern 64 bit int,
    also you'r code is $$$O(n^2)$$$ it will tle for large test.

    → Reply
»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

moi je suis très satisfait des concours de codeforces , il sont très bonnes + éducatifs + entrainement . bonne chance à tous les participants et les inscrits dans codeforces .

→ Reply
»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What is a successful hack test for B?

→ Reply
»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to become Specialist. Wish me luck. Why the hacking phase is so long. All the best of good ratings to everyone.

→ Reply
»
34 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C is similar to 1955. Count Number of Special Subsequences.

→ Reply
»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Emmm. E may be a little ad-hoc. I thought it could be a non-greedy problem. But when I found the correct greedy strategy, I had spent $$$70$$$ minutes on E. When I found F is a simple use of Segment Tree Divide and Conquer, I feel very upset!

→ Reply
»
33 hours ago, # |
  Vote: I like it -20 Vote: I do not like it

I found D easier than the usual Ds of Div2. Don't know about others. Submissions are also less, but I felt it like mid B-C level.

→ Reply
»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain why my B won't pass? if a color has no strangers, it can be changed to a third color in 1 operation, else it would take 2 operations. So I just count the number of operations required to change all colors to a third color. It would be optimal to change all colors to an existing one. If a 2 operation color exist, it would be optimal to change all colors to that one, else we can change all colors to any arbitrary color. If there is only one color, we don't need any operations. What am I missing?

https://codeforces.me/contest/2069/submission/306732090

→ Reply
  • »
    »
    28 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You used v.size() in both dimensions. The logic itself is sound.

    → Reply
    • »
      »
      »
      27 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is the second contest in which I was not able to solve B due to some stupid mistake :< Thanks for pointing it out!

      → Reply
      • »
        »
        »
        »
        26 hours ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        same lol i have literally the same approach and thought procedure as you, yet mine fails too :( https://codeforces.me/contest/2069/submission/306824298

        i'm not able to figure out at all what edge case i'm missing

        → Reply
        • »
          »
          »
          »
          »
          22 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Initialize the map at the beginning instead of else m[a[p][q]]=0;

          → Reply
          • »
            »
            »
            »
            »
            »
            19 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            alright! system testing is going on right now so i can't submit the code right now but how does initializing earlier help?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              16 hours ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              For the test case:
              1
              2 3
              1 1 2
              2 2 1
              Your code might incorrectly assume that color 1 only needs one operation, but it actually requires two.
              The reason is that there are no other '1' around the '1' in the bottom-right corner,so your code will remark it as requiring only one operation.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                15 hours ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                oh damn, I would've never figured that out in my own, thanks a lot

                → Reply
»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can E be solved by using flow ?

→ Reply
»
28 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

when will system testing start and by what time will the ratings be updated??

→ Reply
»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted my solution for Problem B using Python, but it resulted in a TLE on test 7, even though the same logic implemented in C++ got accepted. The expected time complexity of my approach is O(n * m * log(n * m)), so I’m unsure why the Python version is slower. Additionally, my solution was hacked post-contest, which makes me even more curious about the efficiency issue.

Could someone review my Python code and help identify the reason behind the TLE? Here are my submissions for reference: Python C++

→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe that in Python, dictionaries can get blown up by specific testcases which can make dictionary operations perform in O(n) time instead of O(1) time. With C++, it is the same issue with unordered map, but you used ordered map, so it's fine. You should have used an array to hold the stuff from the dictionary since the keys can only go up to n*m (700 x 700). It is common for dictionary and unordered map users to get hacked post contest unless that is checked for in pretests.

    → Reply
»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I had my TOC(Theory of Computation) paper yesterday. Problem A from the round literally reminded me of it. If you don't know which subject is TOC just know that you have to find a string of symbols which is accepted by the machine(automata) in it.

→ Reply
»
28 hours ago, # |
  Vote: I like it +35 Vote: I do not like it

Please make better pretests. Seriously... negative mod is not a very rare or unexpected problem when its a problem about PIE (the brute force is literally summation of all j > i where a_i = 1 and a_j = 3, 2^(count of 2s between i and j) — 1), so some people would keep the PIE by subtracting by prefix frequency of 1s.

This is a standard issue, and while is a dumb error on the participants' part, is a minor mistake and should be penalised with a WA on tc 4 or something, not a FST/hack. How do you fail to catch this? And this isn't a small issue either, By going from the 3000 place to 3500, I was able to find 8 fsts within an hour without even inspecting every single one... i skipped by 5 or 10 randomly sometimes. Such a common mistake should be penalised.

Please do better. Or maybe???? insane idea... add testers to Edu rounds? Like seriously EVERY other division has testers, and they end up with nicer problems (this is not only my opinion there are many in the community who beleive this), I'm sure some people would be willing to test so why not introduce that... Your three person team appears to be incompetent at problemsetting.

→ Reply
»
27 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Please check why my approach to C gives a MLE

here

I haven't learnt dp, I tried without it

ans should be the summation(2^k_i — 1) where k_i represents no. of 2's between every pair 1,3

→ Reply
»
27 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

Why is carrot not working to predict ratings for this round?

→ Reply
  • »
    »
    27 hours ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    seems carrot doesn't work at all now

    → Reply
    • »
      »
      »
      26 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It does show deltas for previous completed rounds, though it's my first time testing it in a live round and it doesn't work.

      → Reply
»
27 hours ago, # |
  Vote: I like it +29 Vote: I do not like it

So when can the editorial be published?

→ Reply
»
27 hours ago, # |
  Vote: I like it +25 Vote: I do not like it

When will the ratings be updated?

→ Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This a very good contest problems are easy but a bit tricky

→ Reply
»
25 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

Why is it unrated?

→ Reply
»
24 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

I believe this round was rated right? will they update the score or the round became unrated ?

→ Reply
»
24 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

When we will get our rating changes? Is system testing done?

→ Reply
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can tell me why I was unrated in this contest?

→ Reply
»
24 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

The system test doesn't seem to have started yet. Just stay patient—things will happen when they're supposed to.

→ Reply
»
23 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

will they publish the result? and why its too late?

→ Reply
»
22 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

will we get results today??!!

→ Reply
»
17 hours ago, # |
  Vote: I like it +39 Vote: I do not like it

Not me hitting the refresh button every 10 second for rating change.

→ Reply
»
16 hours ago, # |
  Vote: I like it +54 Vote: I do not like it

Gta 6 will come before rating changes

→ Reply
»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did this BFS-based approach in B result in an MLE? The idea was simply to perform a BFS from each unvisited cell to find the size of the connected component of the same color as that of the cell and we would mark all cells in that component as visited. If the size was $$$\geq 2$$$, meaning that to color all these cells, we would need 2 operations. Thus, we update the cost for converting these colored cells into another color to be 2.

simply does in $$$O(m \times n)$$$ memory and space complexity seemed to be safe.

Submission : Submission

→ Reply
»
15 hours ago, # |
  Vote: I like it +8 Vote: I do not like it
  • When we will get our rating points?
  • Yes.
→ Reply
»
15 hours ago, # |
  Vote: I like it +53 Vote: I do not like it

Me waiting rating change

→ Reply
»
13 hours ago, # |
  Vote: I like it +19 Vote: I do not like it

Feels like the next contest will happen before rating changes come for this one

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys no worries Rating changes will be updated soon I have texted Mike

→ Reply