By Mike_Computer, history, 14 hours ago, In English,

1) These days the "Downvote problem" is heavily discussed :)

2) One solution would be : You can see the number of downvotes / upvotes only after you have voted

3) Why would this solve the problem? "We see downvotes, we give downvotes" :) The people are most likely to pe influenced by the majority

4) Do you think this could solve the problem?

Read more »

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

By Golovanov399, history, 30 hours ago, translation, In English,

We are sorry that you were having troubles with access to Codeforces.

Problem A of elimination/div2
Problem B of elimination/div2
Problem C of elimination/div2
Problem D of elimination/div2 = problem A of div1
Problem E of elimination/div2 = problem B of div1
Problem F of elimination/div2 = problem C of div1
Problem G of elimination/div2 = problem D of div1
Problem E of div1

Read more »

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

By riela, history, 47 hours ago, In English,

Mwa ha ha ha ha I'm the mad sports programmer (sp) Hououin Riela! The organization is acting again, and as consequence the last round was unrated. However I'll break the convergence to change the worlds control structure.

The last cf round was an important one ― it is part of a tournament. However it was unrated because problems with the servers, many people downvoted the announcement post simply because the contest was unrated, however the problems were interesting. It is not the fault of the setter that the round ended unrated, and a decrease in contribution can be demotivating.

I know that contribution is just a number, but I would be affraid that if I set a round and there is a problem with the servers, then my post will be heavily downvoted.

Do you think is a good idea to remove the downvote button for cf round annoucements? what other solutions do you propose?

I think removing the downvote button is good, because there is no sense in downvoting those kind of posts. Also since I have many enemies (not only Mr Duck and teja[some numbers here]) if I set a round, I'm affraid it will get many downvotes!

Read more »

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

By Mike_Computer, history, 15 hours ago, In English,

Who do you think will win Shumen 2018 ?!? :))

I will place my bet on Ildar Gainullin 300iq

Read more »

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

By shnoh, history, 61 minute(s) ago, In English,

On the round #521 (Div.3), I tried to solve the question using the following code but it fails the test on simple example (Wrong answer on test 39). It runs correctly on my computer. Can anybody tell me why this happens? I am working on it but still did not get the answer.

Problem link

Example

2 2

1 1

My output (on the server)

1 5301

Answer (and also my output on my computer)

1 1

Diagnostics

Diagnostics detected issues [cpp.clang++-diagnose]: C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:1802:11: runtime error: pointer index expression with base 0x12c00210 overflowed to 0x9fdfd8b0 SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:1802:11 in

Source code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

void find(int lower, int upper, int k, vector<pair<int, int> > counts);
bool check(int num, int k, vector<pair<int, int> > counts);

int main()
{
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	map<int, int> m;
	for (int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		++m[val];
	}

	vector<pair<int, int> > counts;

	for (map<int, int>::const_iterator iter = m.begin();
		 iter != m.end(); ++iter) {
		pair<int, int> instance;
		instance.first = iter->second;
		instance.second = iter->first;
		counts.push_back(instance);
	}

	sort(counts.begin(), counts.end());
	reverse(counts.begin(), counts.end());

	find(1, n/k+1, k, counts);
	cout << "\n";

	return 0;
}

void find(int lower, int upper, int k, vector<pair<int, int> > counts) {
	if (upper == lower) {
		int i = 0;
		while (k > 0) {
			int repeat = counts[i].first/upper;

			if (k - repeat < 0) 
				for (int j = 0; j < k; ++j) 
					cout << counts[i].second << " ";
			else
				for (int j = 0; j < repeat; ++j) 
					cout << counts[i].second << " ";

			k -= repeat;
			++i;
		}
		return;
	}

	int mid = (upper + lower) / 2 + 1;

	if (check(mid, k, counts))
		find(mid, upper, k, counts);
	else
		find(lower, mid-1, k, counts);
}

bool check(int num, int k, vector<pair<int, int> > counts) {
	int cnt = 0;
	int i;
	while (k > 0) {
		if (counts[i].first < num) break;

		int repeat = counts[i].first/num;
		k -= repeat;
		++i;
	}
	if (k <= 0) return true;
	else return false;
}

I know my answer is not optimal, but still want to figure out what happened on my answer.

Read more »

 
 
 
 

By A.Kaan37, history, 6 hours ago, In English,

If we get the wrong answer in the sample tests, our score decrease? Two days ago in Codeforces Round #522 (Div. 2, based on Technocup 2019 Elimination Round 3) i get wrong answers on sample tests in B question but my point decrease. I got 2 wrong answers on sample tests but my point decrease 100. Why? Please help me.

Read more »

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

By MakeRussiaGreatAgain, history, 2 hours ago, In English,

Google Code Jam 2019 has been announced. You may read the schedule. To register, you'll have to wait until March 5.

Unfortunately, there will be no Distributed Code Jam in 2019. I think that this has something to do with DCJ platform not receiving any substantial updates for the last three years. Maybe people who made it have already left, and no one can keep it working. It will be sad if this year's Distributed Code Jam is going to be the last.

Read more »

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

By Hasan0540, history, 15 hours ago, In English,

Hello everyone!

The problem set of the 2018 ACM Syrian Collegiate Programming Contest will be available in Codeforces Gym on Nov/24/2018 04:00 (Moscow time).

You will have 12 problems and 5 hours to solve them.

The contest was intended for teams, but I believe it is more interesting for yellow and red coders if they participate individually as they will get to try all the problems.

Your solution should read the input from file, and output to the standard output (stdout).

Problem setters are Motarack, Vendetta., 1am, Light, and Hasan0540.

Thanks to TheDealer, Hiasat, Noureldin, Badry, sqr_hussain, Mohammad Asaad, and Majd Akleh for the help in preparing and testing the problems.

I hope that you will find some interesting problems for you. Any feedback is appreciated!

Read more »

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

By lixolas, history, 31 hour(s) ago, In English,

Yup, you read it right ;)

I know this isn't really a big thing, but still is something that might help when you are about to code a DP which has to optimized in memory.

So, take, for instance the Knapsack problem:

Background

You have N items, each with profit Pi and weight Wi. You want to fit the items in a Knapsack with max capacity of B. What is the max profit you can have?

The usual solution for this DP uses 2 dimensions: dp[i][j] stores the max profit using until the i-th item, with total weight j. So we have the following recursion:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Wi] + Pi).

"Ok, but what is this all for anyway?"

So, first notice that we are dealing with 2 dimensions; the first one is just an index for the items, and the second one is the capacity we are dealing with right now. Also, notice that we are only going backwards in the second dimension. Because of this structure, we could replace the classic 2-dimension code by the following:

for(int i=0; i<N; i++) {
    for(int j=B; j>=0; j--) {
        if(j - W[i] >= 0) {
            dp[j] = max(dp[j], dp[j-W[i]] + P[i]);
        }
    }
}

To retrieve the answer, just take max(dp[j]) between all valid j.

This trick only works because we are walking backwards in the weight dimension instead of forwards. So, when we are updating the DP, we won't mess up and risk using the same item twice (which could easily happen if we went forwards with j). This strategy is sometimes useful when you want to use a DP which goes well in time, but not so much in memory =P

This could be used in the recent contest problem 1078B - The Unbearable Lightness of Weights, and this was, actually, my motivation for writing this blog. My AC submission uses this logic: 45977998.

A little down: you can't recover the list of the items by this method, only the rock-solid answer.

That's it, folks! Have a good day/noon/night! ;)

Read more »

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

By algorithms400, 25 hours ago, In English,

Initially, I have given empty list. I have given Q queries, each queries can perform two types of operation on this list as :

1 x y : Insert value x, y times in list.

2 k : Print kth element of sorted list.

Constraints:

1<= Q <= 2*100000

1<= x,y <= 10^9

At any query, k is always less than or equal to list size.

List can have maximum 10^5 different values.

I have tried to solve this using set of pairs, but for each print it takes O(n) time in worst case.

Please, helps in figure out to solve these operation in O(n*log n ) where n stands for maximum size of list.

Read more »

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