Блог пользователя flamestorm

Автор flamestorm, 21 месяц назад, По-английски

We hope you enjoyed the contest!

1791A - Codeforces Checking

Idea: flamestorm

Tutorial
Solution

1791B - Following Directions

Idea: flamestorm

Tutorial
Solution

1791C - Prepend and Append

Idea: flamestorm

Tutorial
Solution

1791D - Distinct Split

Idea: SlavicG

Tutorial
Solution

1791E - Negatives and Positives

Idea: SlavicG

Tutorial
Solution

1791F - Range Update Point Query

Idea: flamestorm

Tutorial
Solution

1791G1 - Teleporters (Easy Version)

Idea: flamestorm

Tutorial
Solution

1791G2 - Teleporters (Hard Version)

Idea: flamestorm

Tutorial
Solution
Разбор задач Codeforces Round 849 (Div. 4)
  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

wow tutorial comes out so fast!

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Kudos for the fun round and the near instantaneous posting of the tutorial.

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For problem F we can also use a segment tree where the nodes have the max value in the subtree. If the maximum value in any subtree is less than 10 then we shouldn't update that subtree and can skip it. Complexity wise it should be the same as the editorial solution. Implementation 192043154

»
21 месяц назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Perfect div 4 round IMO. Every problem was solvable by div 4 people, with 1 problem that would push most div 4 people and another problem that would really push most div 4 people but still was solvable

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I solved problem F with segment tree (lazy propagation), where I keep track of each update range [l, r] to know the number of times a certain index i [l <= i <= r] also ensuring when the number x <= 9 to break the loop (:)committed 2 WAs initially because of this).

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    unfortunately i solved it using lazy propagation segtree too. I had a feeling it's not needed since it's a div 4 round, and the solution without it is nice. Segtrees sure are powerful though

»
21 месяц назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

A great problemset.

btw
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wow, the tutorial came out so fast. Searched for useful data structures online for problem F and found that using binary indexed tree works.

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solved E with DP. Also for the first time I have used segment tree lazy propagation in a live contest (problem F) :)

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you show me your code for E? i spend an hour to find that a O(n) solution.And i just know if i use dp to solve E i will be TLE.

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      sure
»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Everywhere i go i see "In queue"

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For those who solved F with segment tree/fenwick tree, etc., Um_nik's 2nd and 3rd bullet point from this comment is highly relevant 😁

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yeah true, but gotta do what you gotta do if it's the only solution you came up with

»
21 месяц назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone hack my G2? I think it is not correct even I passed the pretest. 192031288

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone help me understand why my code for problem F gives tle? https://codeforces.net/contest/1791/submission/191999834

»
21 месяц назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

»
21 месяц назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

This is my first contest on this platform and it's really great.

For G2, Editorial solves in O(nlogn) after sort but I solve in O(n) + O(logn) after sort.

https://codeforces.net/contest/1791/submission/192046876

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

My screencast with explanations. The problems were very interesting. Thanks for the contest.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems that the problem writers like binary indexed tree. Both F and G2 can be solved by binary indexed tree.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There's a sqrt decomposition solution for F, for a range of size sqrt(n) save the number of updates on this rsnge‌ as cnt of that range, and then for the queries which they want you to print the value of an index, add cnt of that index + cnt of the range which it belongs to (let sum of these be $$$K$$$) and find the $$$K$$$'s digit sum for that index's number, here's the code :. 192059676

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain this part in problem F to me on example: 1 l r — search for the smallest active index at least l (since the list is sorted, we can do it in O(logn)). Afterwards, update that index (replace ai with S(ai)), remove it if it's no longer active, and binary search for the next largest active index in the sorted list, until we pass r.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it possible to solve the problem F using Segment tree algorithm concept?? Can anyone help me with this solution using Segment tree...

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem E, "if the count of negative numbers is odd, we must have one negative number at the end How can i prove this?

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    here u can shift negative sign to any elements like if i have -2 3 -1 4 -6 5 then it can be easily changed to 2 -3 -1 4 -6 5 then 2 3 1 4 -6 5 still u have one negative now shift that negative sign to 3 index (1 based)

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I understand that negative signs can be shifted anywhere.

      What im asking is how do we know that there is no sequence of operations such that no negative numbers remain (in the odd case)?

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        in one operations either u remove two negative sign or no negative signs see there are three cases when both are negative :- make both positive, 2 neg signs removed when both are postive : no needed , 0 neg signs removed when one is neg and one is positve : still no neg sign removed so every time numbers of neg sign removed is multiple of 2 hence it count is odd one sign always remains

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is the proof of greedy for G1. I thought of it like knapsack but constraints were big so i did greedy but I dont know why greedy is working. shouldn't it fail for the same reason where greedy doesnt work for knapsack ?

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Knapsack has a value and weight. If there is only a value your can use greedy.

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Thought that each number could only have 3 states for F. This is so sad

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Guys, pls, explain F

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I used sweep line on F, I haven’t seen anyone talk about it yet. Store the queries and the index they appear and start the sweep line on the array from left to right. Add active elements(index of the query) when it reaches l in an order set and remove them after it reaches r+1. The first 3 values indicate the minimum index to achieve that state. Can be optimized to o(n)

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Used the same Alg and got HACKED. Possibly TLE.

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You have to process all the queries beforehand

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I actually realized what you did here (Checked your solution). At first, it was uneasy to comprehend because of Java, but you did a mixed sweep line with the ordered set.

        That was a great one and to check them 0,1,2,3 for later is great.

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        But if consider a problem with 10 states, it will consume memory. [Though Imma PY coder XD]

        • »
          »
          »
          »
          »
          21 месяц назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Hack

          Was able to hack my solution to about over half the memory and time available with Java. So it does consume a lot of memory but it is possible to reduce the amount of memory and time used by not storing the states the numbers can transition. So about n+4q memory.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nvm about o(n) still o(nlog(q)+q)

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

192071106 I'm stuck wondering why this code is not working. Not sure if I misunderstood the problem.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Got my precious 2 solution Hacked due to Arrays.sort(JAVA) so much pain this days :-(

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem G2, why is it wrong to take the first portal as portal having minimum overall cost? Can you give a failing test case?-

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If I understood your question, it's because that minimum could be taken with an even lower cost.

    For example for $$$n=3$$$, $$$a = [17, 8, 2]$$$ and $$$c = 13$$$ we can get use second and third teleporter but not if I go to the third one first.

»
21 месяц назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

On problem D I stumbled upon a very weird thing:

When I test my code on my computer, all the test input returns correct answers. However, when I submit this code, I get an error on string "paiumoment". I have no idea how to debug this, because on my machine the answers are all correct. Does anybody know what is the issue?

My g++ version is 12.2.0. I stried both versions 17... and 14.6.4.0 when I submitted the code.

Here's the link to my code: https://codeforces.net/contest/1791/submission/192076794

P.S. I have a feeling that it does something to do with g++ versions, because on different versions the incorrect answers are different values. But how exactly does it work? I never came across such a problem before

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't figure out what is wrong with my code for problem 1791D — Distinct Split. Can anyone help me out? #192086640

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved the F with a segment tree over a difference array

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't know where is wrong about my D code ?

I need help !!!


#include<bits/stdc++.h> using namespace std; void solve() { int n; string s; cin>>n>>s; map<char,int>p; int x = 0; for(int i = 0;i < n;i ++ ) { p[s[i]]++; if(p[s[i]]==2) { x = i; break; } } string ss; for(int i = x;i < s.size();i++) ss+=s[i]; int sum = 0; sort(ss.begin(),ss.end()); for(int i = 0;i < ss.size();i ++ ) { if(ss[i]!=ss[i+1]) sum++; } cout<<x+sum<<endl; } int main() { int t; cin>>t; while(t--) solve(); return 0; }
»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I know some people used a seg tree over a difference array, but did anyone else have the same idea but do it with a fenwick tree? https://codeforces.net/contest/1791/submission/192095662

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In G1, what I understand, there is no port in point 0. So, according to the problem, I cannot teleport back to 0 from 0. But if I consider there is no port at point 0, I get WA. To get AC, I had to consider that there could be port at 0. Why? Also the explanation for testcase 1 is given considering the array is 0 indexed. But while explaining testcase 2, we are considering the array is 1 indexed. I am having confusion. Please help me!

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Array is 1 indexed every where , maybe you're misreading the sample tests. And also ,there is no port at 0

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain why set solution is working in F while map solution giving TLE;

Here is my map Solution giving TLE; https://codeforces.net/contest/1791/submission/191980859

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E solution using DP in O(n). Refer here

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem F can also be solved by binary indexed tree, which is much easier to implement than segment tree if you didn't come up with the tutorial solution.

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n,q,arr[MAXN],diff[MAXN],opera;

int lowbit(int x)
{
	return x&(-x);
}

void add(int x,int v)
{
	for (int i=x;i<=n;i+=lowbit(i)) diff[i]+=v;
	return;
}

int ask(int x)
{
	int ans=0;
	for (int i=x;i>=1;i-=lowbit(i)) ans+=diff[i];
	return ans;
}

int main ()
{
	int T;
	cin>>T;
	while (T--)
	{
		cin>>n>>q;
		for (int i=1;i<=n;i++) 
		{
			cin>>arr[i];
			diff[i]=0;
		}
		
		for (int i=1;i<=q;i++)
		{
			cin>>opera;
			if (opera==1)
			{
				int x,y;
				cin>>x>>y;
				add(x,1);
				add(y+1,-1);
			}
			else if (opera==2)
			{
				int x,y;
				cin>>x;
				y=min(ask(x),3);
				
				int ans=arr[x],temp;
				for (int j=1;j<=y;j++)
				{
					temp=0;
					while (ans)
					{
						temp+=ans%10;
						ans/=10;
					}
					ans=temp;
				}
				
				cout<<ans<<'\n';
			}
		}
	} 
	return 0;
}
»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Great contest! I love it! Hope I can get specialist this time.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a strong data for problem F, but I forget to try it when open hacking,but it can successfully hack one of my friends's code,I left it here but I'm so sorry for that it's a chinese website,but I have tried my best to explain how to use it,you can just download data at the bottom of the website. here: https://www.luogu.com.cn/problem/U279041

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain why i am getting tle one test case 3 on problem F-

Spoiler
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me why this code get TLE in F mySubmission

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You using SegmentTree, so when you update range [l, r], you update from [l, r]. If we have 1E5 query (1 1 n), your code has time complexity is O(n * 1E5 * log(n)) => TLE. This is my opinion about your code.

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I think as i know, in the segment tree the one query takes log(n), and hence the queries over all test cases won't exceed 2e5 so the total complexity will be the number of queries multiplied by the time per query plus the construction of the tree (build function) so we can say: O(2e5 * log(2e5) + 2e5) = O(C * 1e6) where C is a constant so why TLE?

      • »
        »
        »
        »
        21 месяц назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Segment Tree update 1 element in log(n), but you update the range from l to r, so it takes O(log(n) * (r — l + 1)) in 1 query, not log(n)

        • »
          »
          »
          »
          »
          21 месяц назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          So you want to say that we can't solve it using segment tree, can we?

          • »
            »
            »
            »
            »
            »
            21 месяц назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            In my opinion, I think it can't.

          • »
            »
            »
            »
            »
            »
            21 месяц назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I think you don't totally understand how segtree works.

            Segtree is for optimizing "range" operation, and if you see your code again, you will find it only updates in the leaves, which means the segtree doesn't kick in.

            Maybe you can change it to record every element's updation count to make segtree functional.

            Sorry, my English is not good.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a doubt about my submission for F. My code is similar to the one provided in the editorial, the only difference being that I simply moved the iterator to the next element in the set after first setting the iterator to the lower bound of l. But it gives TLE on test case 18. To my knowledge, wouldn't it be better to just move the iterator to the next element in the set as it is already sorted rather than using a binary search to get the next valid index at every iteration? Here's my code -> https://codeforces.net/contest/1791/submission/192143264

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Subject: Need Help for G2 In tutorial it is said we will need to do BS over all the values by taking it as our first problem. While solving I thought that if we took min out of all the starting costs it would be enough. In case of equality between 2 such values I took the one with greater cost from back. It is showing WA at test case 828 expected 2 output 1; what is wrong in my reasoning ?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help in finding the test case in which my algorithm is failing in problem F. Range Update Point Query . submission Link

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Problem G2

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the problem G2, I am not getting how are they handling the case when the portal we are considering is included both times as the initial portal and in the minimum cost prefix. And in the tutorial's code what this piece of code is doing? int now = mid+1; if(mid > i) { price-=a[i].fr; now--; } can anyone help me out?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my code get TLE on test 18 for problem G1? I used qsort to sort the array. https://codeforces.net/contest/1791/submission/192238361

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain why this code is failing this test case?

https://codeforces.net/contest/1791/submission/192817422

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to write the dp of the E question?

  • »
    »
    20 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    https://codeforces.net/blog/entry/112282?#comment-1000597

    Code
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can Someone help for which case i am getting the Wrong Answer in Problem 1791G2.

Here is my code link https://codeforces.net/contest/1791/submission/194376164

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me understand E. My approach in trying to solve it was based on that the order of the numbers is crucial.. and I still don’t see why it’s not.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can somebody help me , I'm getting tle in 1791D here is my source code: https://codeforces.net/contest/1791/submission/232348177

»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

243611436

I cant seem to understand whats wrong with my code. I even looked at the editor, both answers look same but can't seem to find any difference except the while loop which I think shouldn't cause any problem. Can anyone help me debug it. I linked my code above. ///////////////////// solved: I accidently used else if instead of if

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can somebody explain problem 1791D : what is logic for cnt and p vector .why are we doing cur += min(1, cnt[i]) + min(1, p[i]); ....is there any other way to do it ?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i have solution for D using "dp", i think it is very interesting way to solve it) 255889366

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ca

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain to me why i got tle on test 3 ? 271089554