Technocup 2017 — Elimination Round 1 (Unofficially Open for Everyone, Rated for Div. 2)

8 years ago, # ^ |

+13

They will be in Russian and in English.

→ Reply

Adel_SaadEddin

8 years ago, # ^ |

Ok,Thanks

→ Reply

zscoder

8 years ago, # |

+93

3 Div.2 only Contests in 3 Days O_O

→ Reply

shahidul_brur

8 years ago, # |

Bad luck for Bangladeshi contestants ! We will miss it, because we have ACM-ICPC Preliminary Contest starting at the same time (3:00 PM UTC+6) today! Missing a CF round is very painful to me. But wish to participate in this round virtually, as there is no alternative.

→ Reply

AlexandruValeanu

8 years ago, # ^ |

+16

I'm sure you will survive! ;)

→ Reply

FizzyDavicl

8 years ago, # |

+13

What will be the difficulty of the problems like?

→ Reply

Tiny

8 years ago, # |

Almost missed this round since there was no notification yesterday. hope I won't do so bad at this very unusual time.

→ Reply

8 years ago, # |

-21

unusual round with unusual time

→ Reply

khaledzag

8 years ago, # |

-16

Rated ?

→ Reply

8 years ago, # ^ |

only for div2

→ Reply

bzh

8 years ago, # |

I am new here.How much rating is div1/div2?

→ Reply

8 years ago, # ^ |

div2 ]-INF,1900[

div1 [1900,+INF[

→ Reply

bzh

8 years ago, # ^ |

Thanks.

→ Reply

Ninjo

8 years ago, # |

Thanks

→ Reply

zscoder

8 years ago, # |

-17

Looks like there'll be no trivial problems : 1000-1000-1500-1500-2500-3000

→ Reply

allllekssssa

8 years ago, # |

-22

I am really happy because we have so many rounds in few days. Thanks !

But when I saw in description of the task that is interactive + looked at inputs in the second and fourth problem, my wish for doing round dissapeared :(

→ Reply

LoveYayoi

8 years ago, # |

I've got my D running on pretest 3 for about ten minutes

Can anybody tell me what's wrong with this?

→ Reply

King

8 years ago, # |

What was pretest 4 on problem B?

→ Reply

C137

8 years ago, # ^ |

I think something like:

a0.50a0.50

answer is just 1, you shouldn't print 1.00

→ Reply

King

8 years ago, # ^ |

I am sure this is not the pretest since my code accounts for this

→ Reply

MKopchev

8 years ago, # ^ |

Maybe a999.999b0.01c0.99?

→ Reply

King

8 years ago, # ^ |

This is not it either

→ Reply

8 years ago, # ^ |

for me , a case when answer is 1 not 1.00 worked for getting past test case 4 .

→ Reply

C137

8 years ago, # ^ |

+13

well, in this kind of problems you never know where the WA comes from :(

→ Reply

arnold518

8 years ago, # ^ |

how about a13.523.532.01b0.98c0.01

→ Reply

8 years ago, # ^ |

← Rev. 2 →

I got this pretest working after I changed int to long long. This stupid mistake took so much time and score from me...

→ Reply

Rudy1444

8 years ago, # ^ |

I did the same mistake and I didn't get blue because of that :C Well better luck next time :D

→ Reply

Sophie

8 years ago, # |

← Rev. 3 →

+25

Problem B was unusually horrible ;[

Even #passed C is greater than #passed B...

→ Reply

8 years ago, # ^ |

+12

I Agree, but for some reason I thought it was easier than A and thus tried to solve it first.

→ Reply

szawinis

8 years ago, # |

Is D completely greedy?

→ Reply

areke

8 years ago, # ^ |

Yep!

→ Reply

Daniar

8 years ago, # ^ |

← Rev. 2 →

matching problem but can be solved greedy

N=1e5 so greedy is safer to code

→ Reply

gongy

8 years ago, # ^ |

← Rev. 2 →

<_< I stupidly forgot about the bound that preference will be adjacent sizes so I actually did max flow. You only need ~50 nodes for your max flow though, because you can group together people with the same preference specification.

→ Reply

Tiny

8 years ago, # ^ |

I struggled for quite a time but still couldn't understand the greedy algorithm. I am more stupid as I didn't notice the "neighboring" constraint until reading you comment T_T

→ Reply

pimenta

8 years ago, # ^ |

How do we construct a network small enough for a flow algorithm to pass the time limit?

→ Reply

foundLoveOfMyLife

8 years ago, # |

Problem E Pretest 5:Anti Hash?

→ Reply

creatnx

8 years ago, # ^ |

← Rev. 2 →

Do you pass this test:

3 1
aba
4
a
b
c
d

→ Reply

foundLoveOfMyLife

8 years ago, # ^ |

Seems like i have tendency to miss the statement given in bolds.

→ Reply

arnold518

8 years ago, # |

I dont know the answer to problem D. please tell me the approach. I thought it like putting shirts which are sure over and over again.

And after the contest I read prob F, and is it greedy???

→ Reply

green_frog

8 years ago, # ^ |

← Rev. 2 →

i used dp but did not code it

→ Reply

8 years ago, # ^ |

-21

Sort the people by their tshirt choices sizes . Say you want to assign x "S" tshirts , you greedily assign them to people with only one choice . If you cant the answer is NO . Next assign tshirts to people with one of the choices as "S" . After that remove "S" from the choices of people who havent been assigned any tshirt yet . Similarly for other tshirt sizes .

→ Reply

8 years ago, # ^ |

Problem D: assign T-shirts for participants with only one size first. Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise. If any of the counts for remaining T-shirts in negative, print "NO".

→ Reply

arnold518

8 years ago, # ^ |

a sample code please?

&& and also is F greedy?

→ Reply

8 years ago, # ^ |

Sorry, I couldn't solve F.

My C# Code for D (as submitted, added some comments):

Code

using System;
using System.Linq;
using System.Collections.Generic;

class Solution
{
	static void Main(string[] args)
	{
		int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
		int n = int.Parse (Console.ReadLine ());
		List<string> shirts = new List<string>(new string[] { "S", "M", "L", "XL", "XXL", "XXXL" });
		string[] take = new string[n];
		Dictionary<int, int> allow = new Dictionary<int, int> (); //participant number, index of smaller allowed t-shirt
		for (int i = 0; i < n; i++) {
			string str = Console.ReadLine ();
			if (!str.Contains (",")) { //only one t-shirt fits
				take [i] = str;
				nums [shirts.IndexOf (str)]--;
			} else { //two fitting t-shirts
				str = str.Substring (0, str.IndexOf (","));
				allow [i] = shirts.IndexOf (str);
			}
		}
		List<KeyValuePair<int, int>> myList = allow.ToList(); //sort participants by t-shirt size
		myList.Sort(
			delegate(KeyValuePair<int, int> pair1,
				KeyValuePair<int, int> pair2)
			{
				return pair1.Value.CompareTo(pair2.Value);
			}
		);

		foreach (KeyValuePair<int, int> pair in myList) { //for each participant with two sizes
			if (nums [pair.Value] > 0) { //try to assign smaller one
				nums [pair.Value]--;
				take [pair.Key] = shirts [pair.Value];
			} else { //assign bigger one
				if (pair.Value == 5) { //well, that should actually never happen
					Console.WriteLine ("NO");
					return;
				}
				nums [pair.Value + 1]--;//assign bigger one
				take [pair.Key] = shirts [pair.Value + 1];
			}
		}
		if (nums.Any (num => num < 0)) { //did I assign a t-shirt size more often than allowed?
			Console.WriteLine ("NO");
			return;
		}
		Console.WriteLine ("YES");
		foreach (string s in take)
			Console.WriteLine (s);
	}
}

→ Reply

pimenta

8 years ago, # ^ |

Why is this correct?

→ Reply

8 years ago, # ^ |

assign T-shirts for participants with only one size first

You can't do anything wrong in this step, so it should be obvious, that this is correct.

Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise.

I should clarify, that I start with the contestants having the smallest size. So, if I have T-shirt S and M (one each), participants S/M and M/L, then I assign the S T-shirt to the S/M participant. If I would not do that, noone else would have use for the T-shirt. So, if I assign it in this step, I can't break anything. There might be some more participants with the same size, but not enough T-shirts of the lower size, so these get a larger one (if they wouldn't, there would be no way to give them any T-shirt). Now we have handled all participants with the smallest size. We can go one with the next bigger size, that works in the same way as the previous one.

If any of the counts for remaining T-shirts is negative, print "NO".

That means, that I assigned more T-shirts of a size than possible. That obvoisly doesn't work.

One could solve that problem with a max-flow algorithm too, but it would be quite overkill.

→ Reply

pimenta

8 years ago, # ^ |

Well, that's good enough to me... Thanks!

One more question: how do we construct a flow network small enough to Edmonds-Karp fit the time limit?

→ Reply

8 years ago, # ^ |

← Rev. 3 →

The graph is actually quite small: you have vertices for each T-shirt size as well as each participant type (2*sizes-1 types here). Two more vertices (source and sink), that's all. The edges are the capacities (from source to participant: count of participants of that type, from t-shirt to sink: count of t-shirts). Numbers are random, change them depending on the testcase:

→ Reply

8 years ago, # |

+21

I hate tasks like B . C and D were way easier . I wish I'd read D before B :(

→ Reply

abhishek_saini

8 years ago, # ^ |

-8

B took lot of time. F was not that hard either. I needed some more time for F.

→ Reply

gfn

8 years ago, # |

How to solve E ?? without hashing

→ Reply

step_by_step

8 years ago, # ^ |

+21

Aho–Corasick algorithm

→ Reply

gfn

8 years ago, # ^ |

can you please explain your approach ?

→ Reply

haleyk100198

8 years ago, # ^ |

← Rev. 3 →

I haven't coded it yet, but it should be something like this.

Build the aho-corasick tree.
Build an array, mark the possible "jumps" for each position. This can be done by searching the CD through the aho-corasick tree. (You can handle the name that goes cyclic by extending the string) Also check if it is possible to reach that position. For position i<k we will assume it is always possible, for others check if s[i-k] is possible.
Finally check if it is possible to reach s n*k+d . If yes, print the combination.

This should be O(n*k + g*k), which is guaranteed to be about O(1e6 to 1e7) and fits into the 4s TL easily.

UPD: My implementation: http://codeforces.net/contest/727/submission/21471422, remember to handle repated usage of a certain name.

→ Reply

Merln

8 years ago, # ^ |

← Rev. 2 →

Maybe Suffix-Array. Use Binary-Search to match all the names of the game to the string on the CD. Then find some positions which can make the string on the CD filled by these names.

→ Reply

vsp4

8 years ago, # |

-6

I did that stupid mistake str.size() — 3 and leading to integer underflow issue.

But can anyone explain why this happens? is integer underflow also compiler dependent? o.O This code http://ideone.com/QU5GRm doesn't work as on ideone on my system?

→ Reply

I_will_win_a_div1_round

8 years ago, # ^ |

This is unsigned integer (not unsigned int though) overflow, meaning that it is defined. The thing is that string::size() is of type size_t which depends on the platform. On your computer it is stored in 64 bits, on ideone it is stored in 32 bits — http://stackoverflow.com/questions/1119370/where-do-i-find-the-definition-of-size-t.

→ Reply

vsp4

8 years ago, # ^ |

Thanks i get it now. The value 184467440.. also overflows when assigned to (signed) long leading to negative value -1 in my system.

→ Reply

rhezo

8 years ago, # ^ |

str.size() returns an unsigned integer. Always use (int)str.size().

→ Reply

dush1729

8 years ago, # ^ |

← Rev. 2 →

This might help

Funny Bug

→ Reply

shubhamgoyal__

8 years ago, # |

Approach for problem D?

→ Reply

http://codeforces.net/blog/entry/47759?#comment-320501

8 years ago, # ^ |

-8

→ Reply

radoslav11

8 years ago, # |

← Rev. 2 →

F hack test:

3 1 
-6 -3 -3 
6

Answer: 1

→ Reply

radoslav11

8 years ago, # |

Any ideas why one could get WA50 on E?

→ Reply

masonsbro

8 years ago, # ^ |

Assuming you're using a hash-based solution, I think that test case makes a bunch of games' hashes collide, so that if you try to keep a map "hash -> game", it won't work: this would have to be a multimap, since several games can hash to the same value. To solve this problem, I used two different hash functions.

→ Reply

zscoder

8 years ago, # |

What's the intended complexity for F?

→ Reply

8 years ago, # ^ |

We have proven complexity $\text{[math]}$ and unproven O(m + n²).

→ Reply

anta

8 years ago, # ^ |

← Rev. 2 →

+24

Isn't my O(n² + m) DP trivial (and trivial to prove correctness)?

Maybe I'm missing something?

Edit: I have missed $\text{[math]}$ factor so the correct complexity of my implementation is $\text{[math]}$ . (integer sorting can be used to get O(n² + m) (under reasonable bounds of values and on a reasonable model), though).

→ Reply

8 years ago, # ^ |

+11

It is great. Please write it!

→ Reply

satyaki3794

8 years ago, # ^ |

← Rev. 2 →

+16

dp(i, r) is the minimum possible non-negative value you can start with at position i and go till position n, removing at most r elements, such that the value never drops below 0. Complexity of this step is O(n^2).

For a given query b, you can use binary search on the number of elements r you need to remove, using dp(1, r). I have used 1-indexing. Complexity of this step is O(m*logn).

Total complexity is O(n^2 + m*logn).
Code

→ Reply

King_George

8 years ago, # ^ |

Using a greedy algorithm, the complexity will be O(n^2 * log n * log m), which also gets accepted. 21472657

→ Reply

8 years ago, # |

+96

Rating changes for unofficial Div2 participants ?

→ Reply

Vinay_Goel_

8 years ago, # |

Problem D: http://codeforces.net/contest/727/submission/21454057 when i run same code on my system i am getting correct output :(

→ Reply

an2609

8 years ago, # ^ |

check ur ans on online ide. here

→ Reply

flk

8 years ago, # |

+12

Anyone else cannot find their name in the standings although they participated?

→ Reply

deathsurgeon

8 years ago, # ^ |

Are you sure you are checking the unofficial standings?

→ Reply

8 years ago, # ^ |

Mark the checkbox "Show unofficial".

→ Reply

8 years ago, # |

WTF !!!

This is bullshit , where's the rating change for div2 !!!!!

→ Reply

8 years ago, # |

That feel when you fail the round but still improve your rating and become blue. https://www.youtube.com/watch?v=BinWA0EenDY

→ Reply

AmericanPsycho

8 years ago, # |

← Rev. 2 →

+17

→ Reply

hmrockstar

8 years ago, # |

Waiting for div. 2 rating changes!

→ Reply

orb

8 years ago, # |

Is the rating updated? I'm from div.2 and was not rated.

→ Reply

c4big2

8 years ago, # ^ |

Me too...

→ Reply

TooObvious

8 years ago, # ^ |

is the round gonna be rated for Unofficial Div.2

→ Reply

duckladydinh

8 years ago, # |

I am an unofficial div 2 participant and my rating stays the same after rating change. Can someone explain?

→ Reply

Amiri

8 years ago, # ^ |

← Rev. 2 →

for all unofficial div.2 participants still doesn't change.

I think rating change in this round will be in two part for us and for officially participants separately.

→ Reply

Kareem_Mohamed

8 years ago, # ^ |

That's a common problem for DIV2 unofficial participants

→ Reply

8 years ago, # ^ |

+40

It will be updated soon.

→ Reply

ankeshgupta007

8 years ago, # |

← Rev. 2 →

thanks for clearing!

→ Reply

PaneerPakora

8 years ago, # |

Hi. Could someone please clarify who will have ratings changes for this round? It appears that all those who were official participants have had ratings changes, unlike what was said — that it will be rated for div 2 and official participants are Russian school students. If it is clarified, it will be great!

→ Reply

8 years ago, # |

-17

This is the best comment I read :D

→ Reply

EbraM96

8 years ago, # |

What about the editorials ? there will be editorials like regular CF rounds ?

→ Reply

8 years ago, # ^ |

Of course, there were editorials for the previous Technocup.

→ Reply

8 years ago, # |

Rating changes are weird for unofficial participants . In usual rounds any rank < 300 fetched me a positive rating change , today even a rank of 177 fetched me negative change o.O

→ Reply

abhishek_saini

8 years ago, # ^ |

That's because number of users were much lesser today.

→ Reply

daga

8 years ago, # |

In problem D, flow worked. Constraints were not tight.

→ Reply

Nams

8 years ago, # ^ |

← Rev. 2 →

Do you mean to say that the test cases are weak. Or your algorithm worked in linear time? As far as I know max flow works in O(E*V^2).

→ Reply

ooOOOOoooOOOOo

8 years ago, # |

Why didn't I get any rating changes? (I registered during the contest)

→ Reply

AnasAbbas

8 years ago, # ^ |

the same here

→ Reply

ooOOOOoooOOOOo

8 years ago, # ^ |

Do you registered during the contest as well?

→ Reply

Ice_Cream

8 years ago, # ^ |

-6

My rating hasn't changed 1 hour ago, but now it has changed . Sorry for my sorry English.

→ Reply

ooOOOOoooOOOOo

8 years ago, # ^ |

Still didn't get any rating update.

→ Reply

AnasAbbas

8 years ago, # ^ |

yes

→ Reply

I_will_win_a_div1_round

8 years ago, # |

+48

Achievement unlocked! Gotta change my handle now!

→ Reply

wspolbiezneRlz

8 years ago, # ^ |

I was so close to rain on your parade :D

→ Reply

I_will_win_a_div1_round

8 years ago, # ^ |

The same way you were so close not to be so close "to rain on my parade" :D

→ Reply

Nams

8 years ago, # |

I see that some div2 participants have their rating changed after the contest. But still no change for me :( ?

→ Reply

alex_bucevschi

8 years ago, # ^ |

same here.

→ Reply