Shayan's blog

Codeforces Educational Round 169 (Rated for Div. 2) — Video Tutorial
By Shayan, 4 months ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, and not as a substitute for the text editorial.

2004A — Closest Point

Video

2004B — Game with Doors

Video

2004C — Splitting Items

Video

2004D — Colored Portals

Video

2004E — Not a Nim Problem

Video

2004F — Make a Palindrome

Video
  • Vote: I like it
  • +21
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

BRUUUUHHHHHHH I didn't notice the change in B until after the contest :( such BS

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

Will a tutorial on problem G appear?

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

Are there written solutions for the problems? My English listening is poor.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When is the text editorial?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WHERE D hacked ? anyone have test case ?

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

    Yes, many people were hacked, including me on tl. I think many people had a problem because of the slow map<string,vector> structure

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

      I have looked at your code, and the problem is you are doing :

      for(auto z : mapic){
    //do something                    
}

      In this code, z will copy each vector in the map once, so that is why your code is $$$O(nq)$$$, but if you change it to :

      for(auto &z : mapic){
    //do something                    
}

      Then the vector will not be copied as you are only taking a reference to where does it exist.

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

        Wow, thank you so much!!

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

        can you tell me why this code is giving TLE[submission:276903797]

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

          You have the same issue, you are doing

          for (auto &itr : mpp) {
	set<int> temp = itr.ss;
	//do something
}

          change it to

          for (auto &itr : mpp) {
	set<int> &temp = itr.ss;
	//do something
}

          it should pass after this

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

Is it a tendency, that now we have video editorials instead text one? I don't know, right now, is it better or worse, but definetly text editorials provides faster acsess to solution idea, because reading is faster than watching video. On another hand video edits can be easier to understand, so I personally prefer there both would be

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

    also text editorials often have hints that are really valuable when you're almost solving the problem

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve D using DSU? If not why

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

    same doubt:(

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    If you ONLY want to use DSU, it would have worked if the problem asked to tell whether it is possible to move from some city to other. However the problem asks to find the minimum cost of moving from one city to other, which is not possible to solve ONLY using DSU.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The sub-array of f problem is continuous, so you shouldn't use that much n*(n+1)*(n+2)/6

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

    No, this equation is exactly right

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

      can you tell me why?

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

        you can just do a brute force on n=(some number you like) and you'll find that, i do not know how to prove that though.

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

i prefer text editorials

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

where G

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any text tutorial? :(

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yoo everyone, I was trying to upsolve the problems and I submitted the code for problem D and decided to take a break and now when I came back, it's been over 15 mins but my code is still in the queue, idk wht to do

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

    As of writing this comment, it is processing submissions from 7 hours ago, so I think it's gonna take a while. :)

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why the first code is getting AC but the second one got hacked and now is showing TLE? Same logic. But in first one im passing from left to right and in second one im passing from right to left.

Thanks!

Code 1

	public static void solve() {
		int n = ii(), k = ii();
		List<Integer> A = new ArrayList<>();
		for(int i = 0; i < n; ++i) {
			A.add(ii());
		}
		Collections.sort(A, (a , b) -> Integer.compare(b, a));
		for(int i = 0; i < n - 1; i += 2) {
			int d = A.get(i) - A.get(i + 1);
			int min = Math.min(k, d);
			A.set(i + 1, A.get(i + 1) + min);
			k -= min;
		}
		long alice = 0, bob = 0;
		for(int i = 0; i < n; ++i) {
			if(i % 2 == 0) alice += A.get(i);
			if(i % 2 != 0) bob += A.get(i);
		}
		System.out.println(alice - bob);
	}

Code 2

	public static void solve() {
		int n = ii(), k = ii();
		int [] A = iir(n);
		Arrays.sort(A);
		for(int i = n - 2; i >= 0; i -= 2) {
			int d = A[i + 1] - A[i];
			int min = Math.min(k, d);
			A[i] += min;
			k -= min;
		}
		long x = 0, alice = 0, bob = 0;
		for(int i = n - 1; i >= 0; --i) {
			if(x % 2 == 0) alice += A[i];
			if(x++ % 2 != 0) bob += A[i];
		}
		System.out.println(alice - bob);
	}
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There was a test case targeting Java Arrays.Sort which doesn't guarantee worst case O(n log n) time when used on primitive data types. Arrays.Sort uses a different algorithm on objects such as Lists or Integer[].

    It got me too QQ.

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

      Does not make any sense. Collections.sort() is fine but Arrays.sort() isn't?

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

        I don't know about Collections.sort, it might always use merge sort. But for Arrays.sort, if the input is an array of primitive type like int or long, Arrays.sort uses a form of quicksort with worst case time complexity of O(n^2). So if a test case uses input designed to be the worst case, Arrays.sort on an int[] may cause TLE.

        → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will ratings get updated??

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Is there any good video about the game of Nim? I still can't quite get it through reading only.
→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey can somebody help me out to find the error in this implementation of Question — D

277083966

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Question D

Hello, Can anybody tell me why the code is resulting in a TLE ?

https://codeforces.net/contest/2004/submission/277699509

→ Reply